Counting Functions

Transcript

0:00Introduction

Hello everyone! Okay, a quick puzzle first. Set A has four elements, and set B has three. How many functions go from A to B? Half the class says four cubed, sixty four. The other half says three to the power four, eighty one. And how many of those functions use every element of B? So, who is right? By the end, you will answer both in a minute. It comes up often in JEE questions. So, let's begin.

0:32All functions, one-one functions, bijections

So, let's set up. f, a colon, then an arrow from A to B: f sends every element of A to exactly one element of B, okay? The two vertical bars mean the number of elements: A has m elements, and B has n. With me? Now, take just one element of A, okay? How many choices does it have for its image? n choices, yes! Any element of B can be its image, and the next element again has n choices. So, we multiply. But this is where half the class goes wrong. Is it n to the power m, or m to the power n? n to the power m. Absolutely! n times itself, m times, once for every element of A; the dots mean and so on. The base is the size of the target set; the power is the number of elements choosing. Got it? Now, one-one: no two elements share an image. The first element has n choices, the next n minus one, and so on, down to n minus m plus one. That is n P m: the small n at the top left, capital P, and the small m at the bottom right. In the bracket, the less than sign with a line under it means less than or equal to: m cannot exceed n. Clear? And when m equals n, a one-one function pairs off the two sets perfectly: a bijection. n P n is just n factorial; the exclamation mark means factorial. Okay?

1:59Onto, into and many-one functions

Next, onto: every element of B is the image of something; nothing in B is left out. This is harder, because together, the elements of A must cover everything. Right? So, we want the functions that miss none of the elements of B, okay? Which tool from this chapter counts none of the bad properties? Inclusion and exclusion, exactly! The bad property is missing an element. Choose i elements of B to miss: n C i ways, C for combinations. Then everything lands in the other n minus i: n minus i, to the power m. The product is S i: capital S, with a small i at the bottom right. With me? Now, start from the total, subtract S one, add S two, and so on; the total is the i equals zero term. So, onto is the sum, for i from zero to n, of minus one to the power i, times n C i, times n minus i to the power m. The big Greek letter sigma means sum, and minus one to the power i makes the signs alternate. Clear? Now two words that sound alike. Into means not onto: something in B is missed. So, into is n to the power m, minus the onto count. Right? And many-one means not one-one: at least two elements of A share an image. So, many-one is n to the power m, minus n P m. Don't mix them up! Into is about the target, something missed; many-one is about the inputs, two of them sharing an image. Got it?

3:31Increasing functions, and fixed values

Now a special kind of function. The curly brackets hold the sets: inputs one up to m, outputs one up to n. Strictly increasing means f of one is less than f of two, and so on, up to f of m. Each value beats the one before. Okay? Now, the values are all different, just like a one-one function. So the answer is n P m, right? No, no, careful! Just pick which m values are used. Once picked, there is only one way to place them: smallest first, and so on. The order is forced. So, n C m: choosing, not arranging. Clear? And non-decreasing? Now the signs are less than or equal to, so equal values are allowed. Choose the m values with repetition; the order is again forced. That gives n plus m minus one, C m. Got it? Last, a useful habit. If the question fixes some values, settle those first, then count the rest freely. You will see it in the second example. With me?

4:32Example 1: all, one-one, onto functions and bijections

Now, remember our puzzle? Here it is, with two more parts. Part a: all functions from a four-set, a set with four elements, to a three-set. Part b: one-one functions, three-set to five-set. Part c: onto functions, four-set to three-set. Part d: bijections of a five-set to itself. Pause the video, and try it first. Done? Okay, let's check. Part a: four elements, three choices each. Three to the power four, eighty one. Not four cubed! The base is the size of the target. So the eighty one half of the class was right. Okay? Part b: five P three, five times four times three: sixty. The dots on screen mean times. Right? Now part c, onto: the second half of our puzzle. From eighty one, remove the functions missing one target element: three choices for it, sixteen functions each. Eighty one minus forty eight: thirty three, right? Oh no, careful! Take a function sending everything to one element. It misses the other two, so we removed it twice. So, add back three C two, times one to the power four: three. The last term, minus three C three times zero to the power four, is zero. Eighty one minus forty eight, plus three: thirty six. Puzzle solved! Got it? And part d: five factorial, one hundred and twenty. That's it!

6:05Example 2: non-decreasing functions from a 5-set to a 3-set

Now a harder one. Functions from one up to five, to the set one, two, three. How many are non-decreasing? And how many onto functions have f of one equal to one? Pause and try. Hint: for part two, fix f of one first. Done? Okay, let's check. Non-decreasing first. Five inputs, so m is five; three outputs, so n is three. Now wait. Five inputs, only three outputs: is it even possible? Yes, it is! Values may repeat. n plus m minus one is seven: seven C five. Choosing five is leaving out two, so seven C two: twenty one. Very good!

6:49Example 2, part two

Now part two. Fix the condition first: f of one is one, so the value one is covered. The other four values, f of two up to f of five, must use both two and three. We fill the diagram as we go. Okay? The box, U, holds all the choices: four values, three options each. Three to the power four, eighty one. Right? Careful: here A and B are just names for the two circles. Circle A: the functions that miss two, so every value is one or three: two to the power four, sixteen. Circle B: those that miss three, also sixteen. With me? Now the overlap in the middle. Which functions miss both two and three? Only one, yes! Every value equals one. The upside down cup means intersection, so A intersection B holds just that one function. Clear? So, onto is eighty one, minus two times sixteen, plus one: fifty. Fifteen only in circle A, fifteen only in circle B, one in both, and fifty outside: our onto functions. Perfect!

7:54Quick revision: all, one-one, onto and increasing functions

So, quick revision. All functions: n to the power m; one-one: n P m; bijections: n factorial. Onto, by inclusion and exclusion; into and many-one, by subtracting from the total. Strictly increasing: n C m; non-decreasing: n plus m minus one, C m. Now go and try the practice problems on this page. You are ready for them. All the best!