Permutations in dictionary order

[Maths Pro]

If all the letters of the word UDAIPUR are arranged in all possible permutations and these permutations are listed in dictionary order, then the rank of the word UDAIPUR is_____? 1)1580 2)1579) 3)1582 4)1850
Now in dictionary order the words would look like ADIPRUU So with A in the starting place there would be 6!/2! =360 ways D in first place 360. I in first place 360...in short 360*5 = 1800 ways Now I am stuck. Only 50 more permutations when U in the first place? I am totally confused. Please help me understand.

 

[Maths Pro]

If all the letters of the word UDAIPUR are arranged in all possible permutations and these permutations are listed in dictionary order, then the rank of the word UDAIPUR is_____? 1)1580 2)1579) 3)1582 4)1850
Now in dictionary order the words would look like ADIPRUU So with A in the starting place there would be 6!/2! =360 ways D in first place 360. I in first place 360...in short 360*5 = 1800 ways Now I am stuck. Only 50 more permutations when U in the first place? I am totally confused. Please help me understand.

Sorry the word is UDAYPUR not UDAIPUR and I cannot solve beyond 6!/2!

 

[mrtwhs]

I tried to follow the same strategy that you used. I'm not sure but I think:
Starting with:
A there are [imath]\dfrac{6!}{2!}=360[/imath] ways
D there are [imath]\dfrac{6!}{2!}=360[/imath] ways
P there are [imath]\dfrac{6!}{2!}=360[/imath] ways
R there are [imath]\dfrac{6!}{2!}=360[/imath] ways
UA there are [imath]5!=120[/imath] ways
UDA is correct
UDAP there are [imath]3!=6[/imath] ways
UDAR there are [imath]3!=6[/imath] ways
UDAU there are [imath]3!=6[/imath] ways
UDAYP there are [imath]2!=2[/imath] ways and the second one is what you want.

360 + 360 + 360 +360 + 120 + 6 + 6 +6 + 2 = 1580 so I think it would be the 1580th word in the list of 2520.

However when I tried to do it in reverse alphabetical order I got it to be the 1579th word.

 

[Maths Pro]

I tried to follow the same strategy that you used. I'm not sure but I think:
Starting with:
A there are [imath]\dfrac{6!}{2!}=360[/imath] ways
D there are [imath]\dfrac{6!}{2!}=360[/imath] ways
P there are [imath]\dfrac{6!}{2!}=360[/imath] ways
R there are [imath]\dfrac{6!}{2!}=360[/imath] ways
UA there are [imath]5!=120[/imath] ways
UDA is correct
UDAP there are [imath]3!=6[/imath] ways
UDAR there are [imath]3!=6[/imath] ways
UDAU there are [imath]3!=6[/imath] ways
UDAYP there are [imath]2!=2[/imath] ways and the second one is what you want.

360 + 360 + 360 +360 + 120 + 6 + 6 +6 + 2 = 1580 so I think it would be the 1580th word in the list of 2520.

However when I tried to do it in reverse alphabetical order I got it to be the 1579th word

I guess you are almost there. Must be a minor mistake of adding 1 to get the rank. I tried with prototype MUSIC. I got 72nd rank. But with repeated letters I get confused. Is 72nd rank correct?

 

[blamocur]

Do you know how to figure out the rank of a "regular" permutation, i.e. the one without repeated elements? E.g. what is the order of 35142? I don't know the answer myself, but I'd take a look at Lehmer code.

 

[Maths Pro]

Okay I assume REGULAR could be arranged as AEGLR1R2U in dictionary order. Assuming R1 and R2 separate alphabets, I think REGULAR rank is 3045. But I am not sure. Please correct

 

[Maths Pro]

A in first place 6!, E in first place another 6!, likewise for G and L in first place total 2880.
Now R1A fixed : 5!=120
R1EA : 4! = 24
R1EGA,R1EGL,R1EGR2, 3! for each=3!*3=18
R1EGUA : 2!=2
R1EGULAR2 : 1 way
Total : 3045

 

[mrtwhs]

I'm confused. How are you defining rank? There are 2520 ways to arrange REGULAR. So how can one of them have rank 3045?

 

[blamocur]

I'm confused. How are you defining rank? There are 2520 ways to arrange REGULAR. So how can one of them have rank 3045?

I believe in that post two R's are considered different (R1 and R2), so there are actually 5040 ways.

 

[Dr.Peterson]

A in first place 6!, E in first place another 6!, likewise for G and L in first place total 2880.
Now R1A fixed : 5!=120
R1EA : 4! = 24
R1EGA,R1EGL,R1EGR2, 3! for each=3!*3=18
R1EGUA : 2!=2
R1EGULAR2 : 1 way
Total : 3045

Clearly this is not correct. Have you tried treating R and R as being different? It isn't a lot harder.

I notice that there are online calculators that give your answer as if it were correct; perhaps their authors were taught an incorrect definition for rank in this case. (You can see how wrong it is by entering, say, ABA.)

Here is one place I find some correct methods:

What is the rank of COCHIN

Is there any shortcut method for finding the rank of the word COCHIN? I mean is there any shortcut method for finding the rank of a word having repeated letters. For example there is a shortcut met...

math.stackexchange.com

A correct calculator mentioned there no longer exists.

 

[Dr.Peterson]

I hope it's obvious that I meant to say, "Have you tried treating R and R as being indistinguishable?"

The error, if we call it that, is in changing them to R1 and R2, which are different. That changes the problem.

 

[mrtwhs]

I believe in that post two R's are considered different (R1 and R2), so there are actually 5040 ways.

Now I'm really confused. I looked at REGULAR very carefully. Does one of the R's have red hair? Is one of the R's taller? Just how are they different? Also, the four answers given by the OP in post #1 clearly imply that the R's are identical.

 

[Dr.Peterson]

Now I'm really confused. I looked at REGULAR very carefully. Does one of the R's have red hair? Is one of the R's taller? Just how are they different? Also, the four answers given by the OP in post #1 clearly imply that the R's are identical.

Yes; but the comment you refer to is about an answer ("in that post") that treated them as R1 and R2:

A in first place 6!, E in first place another 6!, likewise for G and L in first place total 2880.
Now R1A fixed : 5!=120
R1EA : 4! = 24
R1EGA,R1EGL,R1EGR2, 3! for each=3!*3=18
R1EGUA : 2!=2
R1EGULAR2 : 1 way
Total : 3045

So it isn't yet answering the actual question. That's the point.

Your own answer, by the way, looks fine:

I tried to follow the same strategy that you used. I'm not sure but I think:
Starting with:
A there are [imath]\dfrac{6!}{2!}=360[/imath] ways
D there are [imath]\dfrac{6!}{2!}=360[/imath] ways
P there are [imath]\dfrac{6!}{2!}=360[/imath] ways
R there are [imath]\dfrac{6!}{2!}=360[/imath] ways
UA there are [imath]5!=120[/imath] ways
UDA is correct
UDAP there are [imath]3!=6[/imath] ways
UDAR there are [imath]3!=6[/imath] ways
UDAU there are [imath]3!=6[/imath] ways
UDAYP there are [imath]2!=2[/imath] ways and the second one is what you want.

360 + 360 + 360 +360 + 120 + 6 + 6 +6 + 2 = 1580 so I think it would be the 1580th word in the list of 2520.

However when I tried to do it in reverse alphabetical order I got it to be the 1579th word.

But perhaps you need to explain the last line, which implies you're not sure you were right.

 

[mrtwhs]

Yes; but the comment you refer to is about an answer ("in that post") that treated them as R1 and R2:

Actually I was saying that the answer made an assumption (R's are distinguishable) that did not appear (and was not implied) in the OP.

Your own answer, by the way, looks fine:

But perhaps you need to explain the last line, which implies you're not sure you were right.

When counting backwards, I stopped at the word just after the one I wanted. I should have gone one more. As you say, 1580 is correct.

 

[zen0Mesh]

You were actually very close. The key is to count how many permutations come before UDAYPUR in dictionary order, taking into account that the two U's are identical.

First arrange the letters alphabetically: A D P R U U Y.

Now count how many valid permutations come before UDAYPUR.

For the first letter, anything starting with A, D, P, or R will come before U.
For each of these cases, we fix that letter in the first position and permute the remaining six letters. Since there are two U's, we divide by 2!.

That gives 6!/2! = 360 each.

So far:
360 + 360 + 360 + 360 = 1440

Now we fix U in the first position and move to the second letter. The remaining letters are A D P R U Y.

The second letter in UDAYPUR is D. So we count permutations starting with UA.

Fixing UA leaves five distinct letters, so we get 5! = 120.

Total so far:
1440 + 120 = 1560

Now we fix UDA. The remaining letters are P R U Y.

The next letter is Y, so we count permutations starting with UDAP, UDAR, and UDAU.

Each of those leaves three letters, so each gives 3! = 6.

So we add 6 + 6 + 6 = 18.

Total:
1560 + 18 = 1578

Now we fix UDAY. The remaining letters are P R U.

The next letter is P, so we count permutations starting with UDAYP that come before UDAYPUR.

Fixing UDAYP leaves two letters R and U, which can be arranged in 2! = 2 ways. Since UDAYPUR is the second of those two, we add 2.

Final total:
1578 + 2 = 1580

So UDAYPUR is the 1580th permutation in dictionary order.

The confusion between 1579 and 1580 usually comes from forgetting that rank is position in the list starting from 1, not just the number of words before it.