Combinations and their Properties

Transcript

0:00Introduction

Hello everyone! Okay, one small puzzle before we start. Twelve people are in a room, and each person shakes hands with every other person exactly once. How many handshakes? Each person shakes eleven hands, and there are twelve people. So twelve times eleven, one hundred and thirty two, right? Hmm. The true answer is exactly half of that! So where did the extra handshakes come from? Today we find out. And look, selection questions like this come up often in JEE papers. So, let's begin.

0:34Combination: a selection, order does not matter

So, first, the meaning. Combination means a selection, where the order does not matter. Pick one person and then another, or the same two the other way round: it is the same group. Okay? Now, if the order did matter, you already know the count from permutations. n, times the bracket n minus one, and so on, down to the bracket n minus r plus one. The three dots mean the pattern continues. That is n P r: the capital P, with n at its top left and r at its bottom right. Right? Now take any one selection of r objects. It can be arranged in r factorial ways; the exclamation mark, as you know, is factorial. So what should we divide n P r by, to count each selection only once? Yes, exactly! By r factorial. The ordered choices come in groups of r factorial, and each group is just one selection. Clear? Now back to our puzzle. The small dot means times. Twelve times eleven, one hundred and thirty two, counts ordered pairs. So every handshake got counted two factorial times, that is twice, once from each side. Got it? We finish this in Example one.

1:46The formula for nCr

So now the formula. We select r objects from n different objects. The objects must be different. And the signs on screen say r is at least zero and at most n, okay? Then the number of selections is n C r: the capital C, with n at its top left and r at its bottom right. n C r equals n P r over r factorial, which is n factorial, over r factorial times n minus r, in brackets, factorial. Write this down. This one line is the heart of today's lesson. Right?

2:18Property 1: take r, or leave n-r

Now the properties. First, n C r equals n C n minus r. Why should these two be equal? Perfect! When you choose r objects to take, you are also choosing the n minus r objects to leave behind. So tell me, how would you find twelve C ten quickly? Not with ten factors on top! Twelve C ten equals twelve C two: twelve times eleven, over two, sixty six. Two factors instead of ten. See how fast?

2:49More properties

Now suppose one particular object must always be included. What is left to choose, and from how many? Correct! It already sits in the selection. So choose the other r minus one from the remaining n minus one: n minus one C r minus one. With me? And if it is always excluded, just throw it out. All r come from the other n minus one, so n minus one C r. Right? Now put these two together. Take n plus one objects and fix one of them. Every selection of r either includes it, in n C r minus one ways, or leaves it out, in n C r ways. So n C r plus n C r minus one equals n plus one C r. Clear? Next, r times n C r equals n times n minus one C r minus one. Think of committees of r people from n, each with a chairperson. Choose the committee, then its chairperson in r ways. Or choose the chairperson first, in n ways, then the other r minus one members from the remaining n minus one. Same count, both ways. Okay? And the last one: n C zero, plus n C one, and so on, up to n C n, equals two to the power n. Selections of every size, added up, give all the subsets of a set with n elements. And that number is two to the power n. Got it?

4:07The trap: first ask, does order matter?

Now the trap. Before you use any formula, decide first: does order matter? Choose a committee: it is just a group, so it is a combination. Right? Now, choose a president and a secretary. Combination or permutation? Permutation! The two posts are different. Swap the two people, and you get a different result. So here the order matters. Clear? And now the tricky one. Choose a committee of four, with a leader. What now? Choose the committee first: n C four. Then pick its leader from those four people: four ways. So n C four, times four. Students often call it a pure combination, or a pure permutation. It is neither! Careful, okay?

4:51Example 1: committee of 4 from 9, and 12-person handshakes

Now, remember our handshake puzzle? Let's finish it. Example one has two parts. First, in how many ways can a committee of four be chosen from nine people? Second, twelve people each shake hands with every other person once. How many handshakes take place? Pause the video, and try both. Done? Okay, let's check. Choosing a committee is a selection; the order does not matter. So nine C four: nine times eight times seven times six, over four factorial, that is twenty four. Three thousand and twenty four over twenty four: one hundred and twenty six. Clear? Now the handshakes. What exactly is one handshake, in counting terms? Very good! It is just a pair of people, and the order does not matter. So twelve C two: twelve times eleven, over two factorial. Sixty six handshakes. Okay? See, mystery solved! One hundred and thirty two counted every handshake twice. The sign on screen means divided by. One hundred and thirty two divided by two: sixty six. Got it?

6:01Example 2: cricket XI, one player included or excluded

Now a slightly harder one. In how many ways can a cricket eleven be chosen from fifteen players, if a particular player is always included? And if he is always excluded? The X I on screen is the Roman numeral eleven, a team of eleven players. Pause the video and try it. Alright, included first. He is always in, so we choose from the other fourteen. Fourteen C eleven, right? No, no, careful! This is the trap. He already takes one of the eleven places. So we choose only ten more, from the other fourteen. With me? So fourteen C ten. But no need for ten factors on top! Use our first property: fourteen C ten equals fourteen C four. Fourteen times thirteen times twelve times eleven, over four factorial: one thousand and one ways. Okay? Now excluded. Throw him out, so all eleven players come from the other fourteen. Fourteen C eleven, which is fourteen C three: fourteen times thirteen times twelve, over three factorial. Three hundred and sixty four ways. Clear? And a nice check. Every team either includes him or leaves him out. One thousand and one plus three hundred and sixty four is one thousand three hundred and sixty five, which is fifteen C eleven, all the teams. That is our addition property from earlier, at work. Perfect!

7:23Quick revision: nCr formula, properties, does order matter

So, quick revision. First, a selection where order does not matter: n C r equals n factorial, over r factorial times n minus r, in brackets, factorial. Then n C r equals n C n minus r, because taking r is leaving n minus r. One particular object included gives n minus one C r minus one, and excluded gives n minus one C r. And before any formula, always ask: does order matter? Now go and try the practice problems on this page. You will do them easily, I promise. All the best!