Counting Special Functions

Transcript

0:00Introduction

Hello everyone! Okay, one small puzzle before we start. Three friends are going to a party, and the shop has T-shirts in five colours. Each friend picks one colour. In how many ways can they choose? Three times five, fifteen? Hmm, not so fast. And in how many ways can they choose so that every colour gets worn? Now, think about that one! Look, each friend going to one colour is nothing but a function, from friends to colours. Today we count functions of every type, and we will even crack a JEE Advanced two thousand eighteen question. So, let's begin.

0:43All functions: every element picks a partner

So, set A has small m elements, and set B has small n elements, okay? And a function sends every element of A to exactly one element of B, right? Take the first element of A, okay? How many places can it go? Yes, any of the n elements of B: n choices. The second element? Again n choices, because two elements may share an image, right? So we multiply n by itself, m times: n times n times n, and so on, which is n to the power m, okay? Now, the first JEE trap. Is it n to the power m, or m to the power n? See, the base is the size of the target set; the power is the size of the starting set. Clear? So in our puzzle, it is not three times five. Hold that thought. And constant functions, where every element goes to the same place? Just pick that one element of B: n ways. Really simple.

1:39One-one, many-one and bijections

Alright, now one-one functions: no two elements share an image. The first element has n choices. How many are left for the second one? Yes, n minus one, because one image is already taken! Then n minus two, and so on, for all m elements. So one-one functions number n P m: n times n minus one, down to n minus m plus one. And notice the condition, m less than or equal to n, okay? Many-one simply means not one-one. So many-one is n to the power m, minus n P m. Total minus the good ones, that's it. And when m equals n, the one-one functions are the bijections: n factorial of them, the n with the exclamation mark. Got it?

2:29Onto functions: every element of B is hit

Now the star of today's class: onto functions, where every element of B gets hit, okay? Start small: let B have just two elements. All functions: two to the power m. So all of them are onto, right? No, no, careful! The two constant functions send everything to one element, and miss the other one. Remove them: two to the power m, minus two. With me? Onto three elements: three to the power m, minus three times two to the power m, plus three. Why plus three? Wait for the trick. And the general formula, onto n elements, with m at least n. The big sigma means add up the terms, as r goes from zero to n. Each term is minus one to the power r, times n C r, the bracket with n on top and r below, times n minus r, to the power m. The minus one to the power r just makes the signs alternate. And into is simply not onto: n to the power m, minus the onto ones. Very simple.

3:32Topper's trick: build the onto formula yourself

Now a trick that toppers use: don't mug up this formula, build it. Step one: count all the maps, n to the power m. Step two: remove the maps that miss a chosen element. Choose that element in n C one ways, and send everything to the other n minus one: n minus one, to the power m. Now think. Take a map that misses two elements. How many times did we remove it? Twice, exactly! Once for each missing element. So we add back the maps that miss two: n C two, times n minus two to the power m. And so on: plus, minus, plus. This is inclusion and exclusion, from chapter one! Put n equals three, and the term three times one to the m is our plus three. One more way: split A into n non-empty groups, then give each group a different element of B, in n factorial ways. Keep this ready; it is a beautiful check in example two.

4:29Increasing functions: just choose the values

One more quick pair, for functions between ordered sets of numbers. Strictly increasing: say you have picked which m values get used. Can you arrange them in any other way? No, you can't! The smallest input must take the smallest value, the next one the next value, and so on. The order is forced. So just choose m values out of n: n C m ways. Non-decreasing? Now values may repeat, so we choose m values with repetition: n plus m minus one, C m. Clear?

5:00Example 1: all, one-one, many-one, onto maps from 3 to 5

So, remember our three friends and five colours? Here it is in JEE language. Set A has three elements, and set B has five. Find the number of functions, one-one functions, many-one functions and onto functions from A to B, okay? Pause the video, and try it first. Done? Okay, let's check. All functions: five to the power three. That is one hundred and twenty five. So our friends have one hundred and twenty five choices, not fifteen. Mystery solved! One-one: five choices, then four, then three. Five times four times three: sixty. Many-one: total minus one-one. One hundred and twenty five minus sixty: sixty five. And onto? Zero! Three elements can never cover all five. So that was our second puzzle: there is no way for every colour to get worn, right?

5:59Example 2: JEE Advanced 2018 one-one and onto count

Now a real JEE Advanced question, from two thousand eighteen. Set X has five elements, and set Y has seven. Alpha counts one-one functions from X to Y, and beta counts onto functions from Y to X: the two Greek letters on screen, okay? Find one over five factorial, times beta minus alpha. Pause and try. Hint: watch the directions. Alright, alpha first: one-one, from X to Y, okay? So is it seven P five, or five P seven? Many students grab five P seven here, and get stuck. Look, the five elements of X go into seven. Seven choices, then six, five, four, three. So alpha is seven P five: two thousand five hundred and twenty. Now beta: onto, from seven elements to five. So m is seven, and n is five. Five to the seven, minus five times four to the seven, plus ten times three to the seven, minus ten times two to the seven, plus five times one to the seven, minus zero. Work it out, and it comes to sixteen thousand eight hundred. Big numbers, right? So let's check with the grouping trick. Split the seven elements into five non-empty groups. Sizes three, one, one, one, one: seven C three, thirty five ways. Or two, two, one, one, one: half of seven C two times five C two, one hundred and five ways. The half is there because the two pairs could come in either order. So one hundred and forty groupings, times five factorial, one hundred and twenty. Sixteen thousand eight hundred again. Perfect match! Last step. Beta minus alpha is fourteen thousand two hundred and eighty. Divide by one hundred and twenty. One hundred and nineteen! JEE Advanced, done in a few clean lines.

7:59Quick revision: all, one-one, bijection and onto counts

So, quick revision. All functions: n to the power m. One-one: n P m. Bijections: n factorial. Onto: build it with inclusion and exclusion; onto two elements is two to the power m, minus two. Into and many-one: total minus the good ones. Now go and try the practice problems on this page. You will enjoy them, I promise. All the best!