Derangements

Transcript

0:00Introduction

Hello everyone! Okay, one small puzzle before we start. Four letters, four addressed envelopes, and a careless clerk who puts the letters in at random. In how many ways can every letter go into a wrong envelope? Aman says: each letter has three wrong envelopes, so three times three times three times three, eighty one. But four letters in four envelopes can be arranged in only four factorial ways, that is twenty four, in total! Eighty one wrong ways, out of only twenty four? Something is wrong here, right? Today we find the real answer, using an idea called a derangement. In JEE, questions on derangements come up often. So, let's begin.

0:44No object in its own place

So, what is a derangement? Take n different objects, each with its own fixed place, like a letter and its own envelope. Shuffle them. If no object lands in its own original place, that arrangement is a derangement. Okay? We write the number of derangements of n different objects as capital D, with a small n at its bottom right. We read it D n. So D four means the number of ways four objects can all be out of place. With me? Let's build it slowly. One letter, and one envelope. In how many ways can that letter go into a wrong envelope? Zero, exactly! There is only one envelope, and it is the right one. So D one is zero. Now two letters. The only way to get both wrong is to swap them. So D two is one. Clear? Now three objects: one, two and three, sitting in places one, two and three. In how many ways can all three be out of place? Try listing them. Only two! Very good. Two, three, one: nobody is in their own place. And three, one, two: again, nobody. Every other order keeps at least one number at home. So D three is two. Got it?

2:03The formula and the recurrence

Now, listing works for three objects, but not for six or seven. So we need a formula. D n equals n factorial, times a bracket. Inside: one, minus one over one factorial, plus one over two factorial, minus one over three factorial, and so on. The exclamation mark means factorial, and the three dots mean and so on. The signs keep alternating. Right? The last term is minus one to the power n, over n factorial; the small n at the top right is the power. So the last sign is plus when n is even, and minus when n is odd. And the first two terms, one minus one, always cancel. Okay? But toppers often use a faster way: the recurrence. D n equals n minus one, times the bracket, D n minus one plus D n minus two. Those smaller subscripts mean the two previous values. So each value comes from the two just before it. Clear? Now you try. We know D three is two, and D two is one. Use the recurrence to find D four. Done? Here n is four, so n minus one is three. Three, times two plus one. Three times three: nine! Remember this nine, it is coming back soon. With me? In the same way, D five is four, times nine plus two: forty four. And D six is five, times forty four plus nine: two hundred and sixty five. Right? So here is the topper's trick: remember this row, D one, dot dot dot, up to D six. Zero, one, two, nine, forty four, two hundred and sixty five. It saves real time in the exam. Okay?

3:54Exactly r objects in their own places

Now a very common twist. Not all wrong, but exactly r objects in their own places. Think: if exactly r objects stay in their own places, what must happen to all the remaining ones? Yes, exactly! The remaining ones must all be out of place. So the answer is n C r, times D n minus r. That capital C, with n at its top left and r at its bottom right, is n C r. Got it? Why n C r? Because first we choose which r objects stay in their own places. Any r of the n can be the lucky ones. Okay? And why D n minus r? Because the other n minus r objects must form a derangement among themselves. Nobody else may land in their own place. Clear? Now the trap. Many students write n C r, times n minus r factorial. Oh no, careful! That factorial lets some of the rest also land in their own places, so you overcount. For the rest, always use D, never the factorial. With me?

5:01Example 1: 4 letters, all in wrong envelopes

Now, remember our careless clerk from the start? Let's finish it. Four letters are put into their four addressed envelopes at random. In how many ways do all the letters go into wrong envelopes? Pause the video, and try it first. Done? Okay, let's check. All letters wrong means no letter in its own place: a derangement of four. So the answer is D four. Right? Use the formula. Four factorial is twenty four. Inside the bracket: one, minus one, plus one half, minus one sixth, plus one over twenty four. Okay? Twenty four times one half is twelve. Twenty four times one sixth is four. And twenty four times one over twenty four is one. Twelve minus four plus one: nine! The same nine we got from the recurrence. Perfect! So, where did Aman's eighty one come from? Three to the power four: the small four at the top right. He let each letter pick a wrong envelope on its own, so two letters could share one envelope! But each envelope gets exactly one letter. See, mystery solved: nine, not eighty one. Clear?

6:14Example 2: 5 letters, exactly 2 and at least 3 right

Now a harder one. With five letters and their five envelopes, in how many ways are exactly two letters in the right envelopes? And at least three? Pause and try. Hint: split at least three into cases. Done? Okay, let's check. Exactly two right. Choose the two right letters: five C two, ten. The other three can go in three factorial ways. The cross on screen means times: ten times six, sixty, right? No, no, wait! That is the trap we just saw. Three factorial lets some of those three also go right. The other three must all be wrong: D three, which is two. So ten times two: twenty. Got it? Now, at least three right. Which cases do we need? Exactly three, exactly four, and all five. Correct! We take them one by one. First, exactly three: five C three is ten, and the other two must swap, D two, which is one. So ten times one, ten. Okay? Now exactly four right. Choose the four: five C four, that is five ways. So the answer is five, right? Oh no, careful! If four letters are right, the only envelope left for the fifth letter is its own. So the fifth is forced right too; that is exactly why D one is zero. Exactly four right is impossible: zero ways. Clear? And all five right? Every letter in its own envelope: just one way. With me? So, at least three right is ten plus zero plus one: eleven. And exactly two was twenty. That's it! Very good!

7:59Quick revision: D1 to D6, recurrence, exactly r in place

So, quick revision. Derangement means nothing in its own place, and remember the row: zero, one, two, nine, forty four, two hundred and sixty five. Use the alternating formula, or the recurrence: D n equals n minus one, times D n minus one plus D n minus two. And for exactly r in place, n C r times D n minus r, never n minus r factorial for the rest. Now go and try the practice problems on this page. You will find them easy, I promise. All the best!