Arrangements of Objects that are not all Different

Transcript

0:00Introduction

Hello everyone! Okay, one small puzzle before we start. Take the word MISSISSIPPI. Eleven letters. In how many ways can we arrange them? Eleven letters, so eleven factorial, right? That is almost forty million. Hmm. But the true answer is not even one thousandth of that! So where did all those arrangements go? Today we find out. And look, in JEE, words with repeated letters come up often. So, let's begin.

0:30Swapping identical letters gives nothing new

So, why is eleven factorial wrong? Eleven factorial, that is eleven with the exclamation mark on screen, treats all eleven letters as different. But our letters are not all different, right? Look at the four S's. Let me pretend, just for a moment, that they are different. I label them S one, S two, S three, S four. The small numbers below the S are only name tags, okay? Now take one arrangement, and keep the four places of the S's fixed. In how many orders can the four labelled S's fill those four places? Four factorial, yes! Four times three times two times one, twenty four orders. With me? But now remove the name tags. All twenty four look exactly the same on paper. One word! Swapping identical letters gives nothing new. Got it? So eleven factorial counted every real word four factorial times, just because of the S's. The fix? Divide by four factorial. And the same for every letter that repeats. Clear?

1:35Objects that are not all different

So now the general rule. Take n objects. p of them are alike, of one kind, and q are alike, of another kind, okay? Then r are alike, of a third kind, and the rest are all different. The small letters p, q and r just count the copies. Right? Now you tell me. Start with n factorial, as if everything were different. What should we divide by? Yes, exactly! One factorial for each kind. Arrangements in a row equal n factorial, over p factorial times q factorial times r factorial. Write this down. This one fraction is the heart of today's lesson. Okay? And the objects that are all different, the ones that appear only once? Do we divide for them too? Nothing to divide! Each one is alone, and one factorial is just one. So they never appear below the line. Clear?

2:31Two kinds only: shortest paths on a grid

Now a special case, really simple. Only two kinds of objects: a of one kind, and b of another, all in a row. Okay? Then the count is a plus b, in brackets, factorial, over a factorial times b factorial. And that is the same as a plus b C a: the capital C, with a plus b at its top left and a at its bottom right. Right? Now look at the grid on screen. The point O is at zero comma zero, and the point P is at five comma three. You may walk only along the grid lines. How would you describe a shortest path from O to the point P? Every step goes right or up, never back! Write R for one step right, and U for one step up. Then the path drawn on screen is the word R, R, U, R, R, U, U, R, okay? So a shortest path is just a word in R and U, nothing more. With me? How many letters? Three steps up and five steps right: three U's and five R's. Two kinds only! So eight factorial over five factorial times three factorial. Taking a as the three U's, that is eight C three, just as the figure shows: fifty six paths. See, a path problem became a word problem. That's it!

3:54Topper's trick: objects in a fixed order

Now let me share a trick that toppers use. Suppose some letters must appear in a fixed order, say the vowels in alphabetical order. How is that like today's idea? Here it is. Objects in a fixed order behave like identical objects! Whatever places they get, only one order is allowed there, just like identical letters give only one word. Okay? So, arrange them as if they were identical, and then write them in the only allowed order. Simple, right? So k objects in a fixed order, among n different objects, give n factorial over k factorial arrangements. Remember this one. It saves a lot of time. Got it?

4:35Example 1: arrangements of ALLAHABAD and MISSISSIPPI

Now, remember our puzzle from the start? Let's solve it, with one more word. In how many ways can the letters of ALLAHABAD be arranged? And of MISSISSIPPI? Pause the video, and try it first. Done? Okay, let's check. First, always list the letters. ALLAHABAD has nine letters: the letter A four times, the letter L twice, and H, B and D once each. Right? So nine factorial, over four factorial times two factorial. That is seven thousand five hundred and sixty. Clear? Now MISSISSIPPI. Eleven letters. I four times, S four times. So eleven factorial over four factorial times four factorial, right? No, no, careful! Count again. M once, I four times, S four times, and P twice! Forget the two P's, and your answer comes out double. So always list every letter first. Okay? So, eleven factorial over four factorial times four factorial times two factorial. Twenty four times twenty four times two is one thousand one hundred and fifty two. Answer: thirty four thousand six hundred and fifty. And there is our puzzle! Eleven factorial counted every real word one thousand one hundred and fifty two times. That is why the true answer was not even one thousandth of it. Mystery solved!

6:03Example 2: shortest grid paths avoiding the point (2,2)

Now a harder one, JEE level. How many shortest grid paths go from zero comma zero to four comma four, and avoid the point two comma two? Pause the video and try it. Hint: it is easier to count the paths you do not want. Done? Okay, let's check. First, all the paths. Four steps right and four steps up: four R's and four U's. Eight factorial over four factorial times four factorial, which is eight C four: seventy. Right? Now the bad paths, the ones through two comma two. Getting there takes two R's and two U's: four C two, six ways. And from two comma two on to four comma four? Again two R's and two U's: six ways. Okay? So, how many paths pass through two comma two? Six plus six, twelve, right? No, no, careful! Each of the six ways in can be followed by any of the six ways out. That is the multiplication principle: six times six, thirty six. Clear? So the paths that avoid two comma two: seventy minus thirty six. Thirty four. See? Count all the paths, then subtract the bad ones. That's it!

7:21Quick revision: n!/(p! q! r!), grid paths, fixed order

So, quick revision. Identical objects: divide n factorial by p factorial, q factorial and r factorial, a factorial for each kind. Two kinds in a row: a plus b, in brackets, factorial, over a factorial times b factorial, and a shortest grid path is just such a word. Objects in a fixed order: treat them as identical, n factorial over k factorial. Now go and try the practice problems on this page. List every letter first, and you will find them easy. All the best!