Different Objects into Different Boxes

Transcript

0:00Introduction

Hello everyone! Okay, one small puzzle before we start. Five friends get into a lift at the ground floor, and the building has six floors above. In how many ways can they get out? One student says six to the power five. Another says five to the power six. So, who is right? One simple question settles it. Today we put different objects into different boxes, with empty boxes allowed, and with no box empty. Questions like this come up often in JEE papers. So, let's begin.

0:33Each object chooses a box

So, here is our setting. n different objects, k different boxes, and no limit on a box. That means a box can take any number of objects, even none at all. Okay? Now take just one object. How many choices of box does it have? k choices, yes, exactly! And the next object also has k choices, because there is no limit on a box. Right? So we multiply: k times k times k, one k for each of the n objects. The cross sign means times, and the three dots mean and so on. That gives k to the power n, with a small n at the top right. Clear? Now, a classic trap. Many students write n to the power k instead. So which is right: k to the power n, or n to the power k? k to the power n! Correct. Just ask who is choosing. The objects choose, the boxes do not: a box can take many objects, or none. So the choices, k, form the base, and the choosers, n, form the power. Got it? One more way to see it. Sending each object to a box is a function from the set of objects to the set of boxes. So there are k to the power n functions from an n element set to a k element set. With me?

1:54No box empty: onto maps

Now, the harder case: no box may be empty. Every box must get at least one object. As a function, every box is used, and such a function is called onto. Okay? So start with all k to the power n ways, and throw out the ways that leave a box empty. Right? So tell me. In how many ways can box one be left empty? k minus one, to the power n. Yes! Every object now has only k minus one boxes to choose from. And the empty box can be chosen in k C one ways: the capital C, with k at its top left and one at its bottom right. So we subtract k C one, times k minus one in brackets, to the power n. With me? But wait. Take a way that leaves two boxes empty, say box one and box two. It was thrown out twice: once for box one, and once for box two. So we add back k C two, times k minus two, to the power n. Clear? And so on, with the signs taking turns: minus, plus, minus. This is inclusion and exclusion again, the same idea you used for sets. Got it?

3:07Small cases worth remembering

Now put k equal to three. Three to the power n, minus three C one times two to the power n, plus three C two times one to the power n. What is that last term worth? Three! Very good. Three C two is three, and one to the power n is one. So for three boxes: three to the power n, minus three times two to the power n, plus three. The small dot means times. Many students forget this plus three, okay? For two boxes, it is even shorter: two to the power n, minus two. Which two ways are thrown out here? Correct! All the objects in box one, or all of them in box two. Those are the only ways to leave a box empty. Right?

3:52Box sizes fixed

One last case: the question fixes how many objects each box gets. Say box one gets a, box two gets b, and box three gets c. Then use the group formula from earlier in this chapter: n factorial, over a factorial, b factorial, c factorial. The exclamation mark means factorial. Okay? And if only the sizes are given, not which box gets which, multiply by the number of ways to give the sizes to the boxes. Clear?

4:22Example 1: 5 people leaving a lift at 6 floors

Now, example one, and it is our lift puzzle! Five people enter a lift at the ground floor of a building with floors one to six above. In how many ways can they get out, if, part A: there is no restriction; part B: they all get out at different floors; part C: exactly two floors are used? Pause the video, and try it first. Done? Okay, let's check. The people are different, and the floors are different. So, for part A, who chooses here: the people, or the floors? The people, yes! Each person chooses one of six floors. So six to the power five: seven thousand, seven hundred and seventy six. Puzzle solved: six to the power five, not five to the power six. Okay? Part B: all at different floors, so no floor can take two people. The first person has six floors, the next has five, then four, three and two. That is six P five: the capital P, with six at its top left and five at its bottom right. Seven hundred and twenty. Right? Part C: exactly two floors are used. First choose those two floors: six C two, fifteen ways. With me? Now the five people go to these two floors. Each person has two choices, so two to the power five, thirty two ways, right? No, no, careful! Two of those thirty two ways put everyone on one floor, so only one floor is used. Both floors must be used, so it is the onto count for two boxes: two to the power five, minus two, that is thirty. Clear? So fifteen times thirty: four hundred and fifty. Perfect!

6:11Example 2: onto functions from a 6-set to 3 and 4 sets

Now a harder one, with functions. How many functions from a six element set onto a three element set are there? And onto a four element set? Pause and try. Hint: the six elements are the objects, and the other set gives the boxes. Done? Okay, let's check. Onto means no box empty, with three boxes here. So use our small case: three to the power six, minus three times two to the power six, plus three. Seven hundred and twenty nine, minus one hundred and ninety two, plus three: five hundred and forty. Okay? Now four boxes. Our formula runs longer this time. Which terms do we need? Yes, exactly! Four to the power six, minus four C one times three to the power six, plus four C two times two to the power six, minus four C three times one to the power six. All four boxes empty is impossible, so we stop here. With me? Now the numbers. Four thousand and ninety six, minus two thousand nine hundred and sixteen, plus three hundred and eighty four, minus four. One thousand five hundred and sixty. Do not forget that last minus four, okay? It is the easiest mark to lose. Well done!

7:34Quick revision: all ways, no box empty, 2 and 3 boxes

So, quick revision. No limit on a box: each object chooses a box, so k to the power n ways. No box empty: start from k to the power n, then subtract and add back, with signs taking turns. And the small cases: three to the power n, minus three times two to the power n, plus three; and two to the power n, minus two. Now go and try the practice problems on this page. You will find them easy, I promise. All the best!