Mixed Problems: Set 3 (Distributions, Functions, Inclusion–Exclusion)

Transcript

0:00Introduction

Hello everyone! Okay, a small puzzle to start. Seven different balls, and three different boxes. Each ball can go into any box, so there are three to the power seven ways, that is two thousand one hundred and eighty seven. Now, in how many of these ways is no box empty? Hmm, not so easy, right? Today we solve a mixed set on distributions, functions, and inclusion and exclusion, and you will crack this puzzle in one line. Questions like these come up often in JEE Main, and each one should take you only a minute or two. So, let's begin.

0:39Move 1: identical objects, different boxes

So, move one, and it starts with reading the conditions. Are the objects identical or different? Are the boxes identical or different? Can a box stay empty? Here we have n identical objects, k different boxes, and empty boxes allowed, okay? Then it is stars and bars, and the count is 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. Right? Now, a twist. What if every box must get at least a certain number of objects, call it a? What do we do then? Yes, exactly! Give those away first. Put a objects in every box, and then share whatever is left with stars and bars, freely. Clear? And if a box can hold at most b objects? Now we cannot give anything away first. So, count everything, then subtract the ones that break the limit. That is inclusion and exclusion in its simplest form. Keep this for example two, okay? Here is one from this set. Twelve identical balls go into four different boxes, with at least two in each; the sign on screen is greater than or equal to. Give two to every box: that uses eight, and four are left. Four stars, three bars: four plus four minus one C four minus one, which is seven C three, thirty five ways. Got it?

2:10Move 2: different objects, no box empty

Now, move two. This time the objects are different, and the boxes are different too. Then each object simply chooses its box: k choices for the first, k for the second, and so on. So k times k, n times over: k to the power n, the small n at the top right. Okay? But tell me, in these k to the power n ways, can a box stay empty? Of course it can! All the objects can even land in one box. So, no box empty equals all the ways, minus those where some box is empty. Some box empty means at least one empty box, and with several boxes that can be empty together, this count is a job for inclusion and exclusion. Clear? And functions are the same story. The line on screen reads f from A to B; the arrow means each element of A is sent to one element of B, just as each object goes into one box. With me? So an onto function, where every element of B gets used, is exactly a distribution with no box empty. Same count, two different stories. Remember this link!

3:19Move 3: functions with a condition

Alright, move three. When a function has conditions on some of its values, fix those values first, and then the other values are free. Okay? Here is one from this set. How many onto functions f, from the set one to six, to the set a, b, have f of one equal to f of two? The curly brackets mark a set, and the three dots mean and so on. With me? So, f of one and f of two share one value: two choices, a or b. Then f of three up to f of six are free: two to the power four, sixteen. The dot means times, so two times sixteen is thirty two. So the answer is thirty two, right? No, no, wait! The question says onto, so both a and b must be used. Two of these thirty two functions send everything to one value, all to a, or all to b; these are the constant functions. Remove them: thirty two minus two, thirty. Got it?

4:24Example 1: 7 different balls in 3 boxes, none empty

Now, remember our puzzle from the start? Let's finish it. In how many ways can seven different balls be put into three different boxes, with no box empty? Pause the video, and try it first. Done? Okay, let's check. Different balls, different boxes, so by move two, each ball chooses a box: three to the power seven, two thousand one hundred and eighty seven ways in all. Okay? Now throw out the bad ones. Say box one is empty. Then each ball picks one of the other two boxes: two to the power seven, one hundred and twenty eight. Any of the three boxes can be the empty one: three times one hundred and twenty eight, three hundred and eighty four. So the answer is two thousand one hundred and eighty seven minus three hundred and eighty four, that is one thousand eight hundred and three, right? No, no, careful! This is the trap. Think of all seven balls in box one. Then box two is empty, and box three is empty too. So this way was thrown out twice: once with box two empty, and once more with box three empty. Clear? There are three such ways: everything in box one, or in box two, or in box three. Each was removed twice, but it should go only once, so we add each one back once: plus three. With me? So, three to the power seven, minus three times two to the power seven, plus three. Two thousand one hundred and eighty seven, minus three hundred and eighty four, plus three: one thousand eight hundred and six ways. Puzzle solved! Very good!

6:06Example 2: solutions of x+y+z=12 with x at most 3

Now a slightly harder one. Find the number of non-negative integer solutions of x plus y plus z equals twelve, with x less than or equal to three; that is the sign on screen. Non-negative means zero is allowed, okay? Pause and try. Hint: think of move one. Done? Okay, let's check. Think of twelve identical stars shared among three different boxes, called x, y and z. First, ignore the limit on x. Twelve stars and two bars: twelve plus three minus one C three minus one, that is fourteen C two, ninety one. With me? Now, x less than or equal to three is an upper limit. Which of these ninety one solutions break it? Yes, exactly! The ones with x four or more. And that is a lower limit, so move one handles it: give four to x first. Put x prime equals x minus four; the little dash is read prime. Then x prime plus y plus z equals eight. Okay? So, how many bad solutions are there? Eight stars and two bars: eight plus three minus one C three minus one, which is ten C two, forty five. Clear? So the answer is ninety one minus forty five: forty six. See the pattern? Count everything, then subtract the ones that break the limit. That's it!

7:39Quick revision: stars and bars, no box empty, onto

So, quick revision. Identical objects: stars and bars; give the lower limits away first, and subtract the cases that break an upper limit. Different objects: k to the power n; for no box empty, or onto, use inclusion and exclusion. Conditions on a function: fix those values first, and the rest are free. Now go and try the three practice problems on this page. Read the conditions first, and you will find them easy. All the best!