Identical Objects into Different Boxes

Transcript

0:00Introduction

Hello everyone! Okay, one small puzzle first. Ten identical balls, four different boxes. In how many ways can I put the balls into the boxes? Let's try listing. All ten in the first box. Nine in the first, one in the second. Hmm, how long will this list be? Very long! You could write for an hour! Today we count them all in one line, with stars and bars. This comes up often in JEE, so let's begin.

0:31From boxes to stars and bars

First, the conditions: the objects are identical, the boxes are different, and a box may stay empty, okay? Let x one be the number in box one, x two the number in box two, up to x k. The small number at the bottom right of x names the box; the three dots mean and so on. They add up to n, and each x i is greater than or equal to zero. So sharing is just solving this equation in non negative integers. Clear? Now look at the figure. The orange dots are the stars: seven identical objects. The blue lines are the bars, the walls between boxes. Two stars, a bar, four stars, a bar, one star. So x one is two, x two is four, x three is one. Three boxes, and only two bars. Now tell me, for k boxes, how many bars do you need? k minus one! Yes, exactly. The bars are only the walls between the boxes. So every way of sharing is a row of n stars and k minus one bars: n plus k minus one places in all. Right? Once you choose which places hold the bars, the row is fixed, since all the stars look the same. So choose k minus one places out of n plus k minus one: n plus k minus one C k minus one. The capital C has n plus k minus one at its top left, and k minus one at its bottom right. In the figure, nine C two, thirty six solutions. With me? Now a twist. What if no box may be empty, so each x i is at least one? Can we still use the same formula? No, no, careful! That formula allows empty boxes. The trick: first put one object in each box. That uses k objects, and n minus k are left, free to go anywhere. So the count becomes n minus one C k minus one. Got it?

2:32Lower bounds, upper bounds and inequalities

Alright, that trick works for any lower bound. Suppose each x i must be at least a i. Give box i its a i objects first, and let y i be what it gets after that: y i equals x i minus a i. Now each y i is greater than or equal to zero. Okay? And the new total? The sum of the y i's equals n, minus the sum of the a i's. That big symbol is the capital Greek letter sigma; it means add them all up. Then use stars and bars, as before. Simple, right? Now the opposite case. What if a box can hold at most a certain number? Can we shift that out the same way? Not so easily. First count everything, ignoring the upper bound. Then subtract the solutions that break it. The full method is inclusion and exclusion, which you will meet in Chapter five. Today, a simple case in Example two. Clear? One more. What if the sum is at most n, not exactly n? How do we get an equation back? Add one more variable! On screen, the sign before n is less than or equal to. Bring in x k plus one, a slack variable, greater than or equal to zero, to take whatever is left over. Now the sum is exactly n: k plus one boxes, n stars. Got it?

4:01The same count in disguise

Now, stars and bars hides in other questions too. Selecting r objects from n kinds, with unlimited repetition, objects of one kind identical. Careful: here n is the number of kinds. Each kind is a box, and the r objects are the stars. So the count is n plus r minus one C r. Okay? And the number of terms of x one plus and so on up to x k, the whole bracket raised to the power n: the small n at its top right. In every term, the powers add up to n. Our equation again! So, n plus k minus one C k minus one terms. With me?

4:42Example 1: 10 identical balls in 4 boxes, then none empty

Now, remember our puzzle from the start? Let's finish it. In how many ways can ten identical balls be put into four different boxes? And in how many ways, if no box may be empty? Pause the video, and try it first. Done? Okay, let's check. Let x one to x four be the numbers of balls in the four boxes. They add up to ten, and each is at least zero. Right? Now, some students think: each ball can go into any of four boxes, so the answer is four to the power ten. Is that correct? No, no, careful! Four to the power ten counts different balls, where it matters which ball went where. Our balls are identical. Only how many land in each box matters. Clear? So, stars and bars: ten stars and three bars. Ten plus four minus one C four minus one, which is thirteen C three, two hundred and eighty six ways. See, our endless list from the start, counted in one line! Okay? And with no box empty? Give one ball to each box first, and six are left. So ten minus one C four minus one, that is, nine C three, eighty four ways. Got it?

6:02Example 2: 20 chocolates to 4 children, each gets 2 to 8

Now a harder one, JEE level. Twenty identical chocolates are given to four children, so that each child gets at least two, and at most eight. In how many ways? The children, of course, are different. Pause the video and try. Hint: handle the lower bound first. Done? Let's check. Let x i be the chocolates of child i. Give two to each child first: eight used, twelve left. Put y i equals x i minus two; then y one to y four add up to twelve. And since x i is at most eight, zero is less than or equal to y i, which is less than or equal to six. With me? Now ignore the upper bound for a moment. Twelve stars and three bars: fifteen C three, four hundred and fifty five. So the answer is four hundred and fifty five, right? No, no, careful! That count lets a child get more than six extra. So subtract the bad cases. Suppose one y i is seven or more. Put y i prime equals y i minus seven; the little dash is read prime. Now the sum is five: eight C three, fifty six. And this can happen for any of the four children. Clear? But wait. Should we also worry about two children breaking the limit together? No, they cannot! Seven plus seven is fourteen, which is greater than the twelve we have. So there is no double counting to fix. Okay? So, four hundred and fifty five, minus four times fifty six, which is two hundred and twenty four. Two hundred and thirty one ways. Shift out the lower bound, subtract the upper. That's it!

7:46Quick revision: stars and bars, bounds and slack variable

So, quick revision. n identical objects into k different boxes: n plus k minus one C k minus one; none empty, n minus one C k minus one. Lower bound: shift it out. Upper bound: subtract the cases that break it. Sum at most n: add a slack variable. Now try the practice problems on this page. All the best!