Rank in Dictionary Order

Transcript

0:00Introduction

Hello everyone! Okay, a small puzzle before we start. Take the four letters of the word rank: R, A, N and K, okay? Now make every possible word with all four letters, each used exactly once, and write those words in dictionary order, the way a dictionary lists them. Four different letters give four factorial, that is twenty four words. So where does the word rank itself sit in that list? Its first letter, R, comes last in alphabetical order, so rank must be the very last word, number twenty four, right? Hmm, not so fast! By the end of this video, you will find its exact position without writing the list at all. And questions like this come up often in JEE, so let's begin.

0:50Rank: the position in dictionary order

So, first, what do we mean by rank? Write all the arrangements of the letters in dictionary order. The position of our word in that list is its rank. Okay? Now, for a long word, that list is huge. So tell me: how can we find the position without writing the whole list? We count only the words that come before ours! And which words come before it? The words that agree with ours so far, and then have a smaller letter at the next place. That is exactly how a dictionary works, letter by letter. Right? Now suppose we have counted every word that comes before ours. Is the rank equal to that count? No, no, careful! Our own word comes right after all of them. So the rank is one plus the number of words before it. Such a small plus one, but forgetting it is a very common mistake. Clear?

1:43The method, letter by letter

Now the method, in three steps. Step one: write the letters of the word in alphabetical order. This is your dictionary, okay? Step two: look at the first place. For every different letter smaller than the actual first letter, put it in the first place, and count the arrangements of the remaining letters. All these words come before ours. With me? Step three: now fix the actual first letter, and do the same for the second place. Then fix the second letter, move to the third place, and so on, till the word ends. Got it? But wait. What if some letters in the word repeat? Is it still a plain factorial for the remaining letters? No! Swapping two identical letters gives the same word, so we must divide. If m letters are left, with p of one kind alike and q of another kind alike, the arrangements are m factorial over p factorial times q factorial. The exclamation mark is the factorial sign, and the three dots mean one more factorial below for every other letter that repeats. Okay?

2:47Example 1: rank of the word RANK

Alright, let's solve our puzzle. Find the rank of the word rank among the arrangements of its letters. Four different letters, each used exactly once, in dictionary order. Pause the video and try it. Done? Okay, let's check. Step one, alphabetical order: A, K, N, and then R at the end. Our word starts with R, the biggest letter here. Right? Now, three letters are smaller than R: A, K and N, okay? How many words start with one of them? Fix any one of them in the first place, and the other three letters can be arranged in three factorial, that is six ways. Three such letters, so three times three factorial: eighteen words. The cross means times. All eighteen come before rank. With me? Now fix R in the first place. In the second place our letter is A, and nothing is smaller than A, so no words there. Next, fix R and A in the first two places. In the third place our letter is N, and K is smaller. So R, A, K, N comes first: one word. And right after it, our word rank. Clear? So the rank is eighteen, plus one for R, A, K, N, plus one for our own word. Twenty! Not twenty four, as we guessed at the start. Puzzle solved. Very good!

4:16Example 2: rank of SUCCESS, with repeated letters

Now a harder one, with repeated letters. Find the rank of the word success, among the arrangements of its letters in dictionary order. Seven letters, all used each time, but some of them repeat, okay? Pause the video and try it. Done? Okay, let's check. Alphabetical order: two Cs, then E, then three Ss, and U last of all. Our word starts with S, so the smaller letters are C and E, right? Now, careful. There are two Cs. So do we count the words starting with C two times? No! Only once. Both Cs look the same, so a C in front gives the same words either way. Put C first. Six letters are left: C, E, U and three Ss. The three Ss are alike, so six factorial over three factorial: seven hundred and twenty over six, one hundred and twenty. Got it? Next, E first. Six letters are left: two Cs, the U and three Ss. So six factorial over two factorial times three factorial. Seven hundred and twenty over twelve: sixty. With me? Now fix S in the first place, and look at the second place: our letter there is U, okay? Which letters can go second and are smaller than U? C, E and S! Yes, S too, because two more Ss are still left. Many students forget this one. S, C: five letters left with two Ss alike, so five factorial over two factorial, sixty. S, E: two Cs alike and two Ss alike, five factorial over two factorial times two factorial, thirty. S, S: two Cs alike, sixty again. Clear? Now fix S and U in the first two places. The letters left are C, C, E, S, S, already in alphabetical order. So success is the very first word beginning with S, U, okay? So add them all: one hundred and twenty, plus sixty, plus sixty, plus thirty, plus sixty. That makes three hundred and thirty words before success. And plus one for the word itself. Rank three hundred and thirty one. Perfect!

6:39Quick revision: count smaller letters, divide repeats, add 1

So, quick revision. Write the letters in alphabetical order, and count the words with a smaller letter, place by place. When letters repeat, count each different letter only once, and divide by the factorials of the alike letters. And the rank is one plus the number of words before it. Now go and try the two practice problems on this page. You will find them easy, I promise. All the best!