Permutation and combination when letters are repeated

[Maths Pro]

I have a doubt in permutation and combination problem. Here it goes : In how many different arrangements of letters in the word MAHARASHTRA have R and H never together? I tried to solve it using prototype QUEUES. Like in how many ways can letters be arranged to not have U and E together? I worked out manually and got 96 ways in which 24 are distinct. But to work out letters of MAHARASHTRA is a mammoth task. Please help me understand solution to this sum

 

[blamocur]

This one looks like a difficult combinatorics problem to me. If you have difficulties with permutations and combinatorics in general you might consider starting with simpler problems.

My intution tells me to look at "stars and bars" methods, like in this post by @Dr.Peterson.

 

[Dr.Peterson]

I agree on stars and bars; for an intro to that, see

Stars and bars (combinatorics) - Wikipedia

en.wikipedia.org

I would expect to need several cases, but I haven't tried yet.

How did you work out your answer for QUEUES? Can you list some of the arrangements? And what do you mean by "not distinct"? (I initially thought there were no such arrangements, because I misread the requirement.)

 

[blamocur]

And what do you mean by "not distinct"?

I do not represent @Maths Pro, but I'll venture a guess. There are 720 permutations of 6 letters, but in case of QUEUES only 720/4 = 180 result in different ("distinct"?) words because swapping U's or E's does not change the resulting word.

 

[mrtwhs]

I'm getting 88200. Here is my approach.

First line up M,A,A,A,A,S,T (everything except the two H's and two R's). This can be done in [imath]\dfrac{7!}{4!}=210[/imath] ways.

Spreading these seven letters out creates eight potential places to insert one of the four letters (H,H,R,R). So choose four of them in [imath]C(8,4)=70[/imath] ways.

Finally, order the four selected letters (H,H,R,R) in [imath]\dfrac{4!}{2!2!}=6[/imath] ways and insert them.

[imath]210 \cdot 70 \cdot 6=88200[/imath]

 

[Maths Pro]

I agree on stars and bars; for an intro to that, see

Stars and bars (combinatorics) - Wikipedia

en.wikipedia.org

I would expect to need several cases, but I haven't tried yet.

How did you work out your answer for QUEUES? Can you list some of the arrangements? And what do you mean by "not distinct"? (I initially thought there were no such arrangements, because I misread the requirement.)

By not distinct i mean I took QU1E1U2E2S. I had such arrangements QU1U2SE1E2, E1E2SU1QU2, U1QE1E2SU2, U1U2QSE1E2, U1QU2SE1E2, etc. Now to imagine in the word MAHARASHTRA will have M_A_A_A_A_H_T_S_R_R_H. I don't know how to arrange very very confused

 

[mrtwhs]

I agree with the OP about QUEUES. I get [imath]2 \cdot (3+3+6)=24[/imath].

 

[Dr.Peterson]

I agree with the OP about QUEUES. I get [imath]2 \cdot (3+3+6)=24[/imath].

It looks like you are using different methods for the two problems. It would be helpful to apply the same method to both, which could help confirm the method.

Where did 3+3+6 come from? (I could guess, and I think your answer is right, but a calculation does not explain itself!) If you're just trying not to reveal too much yet, that's fine.

I'm getting 88200. Here is my approach.

First line up M,A,A,A,A,S,T (everything except the two H's and two R's). This can be done in [imath]\dfrac{7!}{4!}=210[/imath] ways.

Spreading these seven letters out creates eight potential places to insert one of the four letters (H,H,R,R). So choose four of them in [imath]C(8,4)=70[/imath] ways.

Finally, order the four selected letters (H,H,R,R) in [imath]\dfrac{4!}{2!2!}=6[/imath] ways and insert them.

[imath]210 \cdot 70 \cdot 6=88200[/imath]

This appears to keep H's apart from one another, as well as from R's. That was my initial misreading of the problem. Or maybe I'm misreading your work.

I still haven't taken the time to work out an answer of my own.

 

[blamocur]

This appears to keep H's apart from one another, as well as from R's. That was my initial misreading of the problem. Or maybe I'm misreading your work.

My brute force script confirms the 88200 answer under this assumption.

 

[blamocur]

I believe I've solved it, but I am not too proud of the solution: it considers 7 different cases for placing [imath]H[/imath]'s

 

[mrtwhs]

It looks like you are using different methods for the two problems. It would be helpful to apply the same method to both, which could help confirm the method.

Where did 3+3+6 come from? (I could guess, and I think your answer is right, but a calculation does not explain itself!) If you're just trying not to reveal too much yet, that's fine.


This appears to keep H's apart from one another, as well as from R's. That was my initial misreading of the problem. Or maybe I'm misreading your work.

I still haven't taken the time to work out an answer of my own.

You are correct. I've kept all four letters apart. However the OP's original wording seems to allow HH as well as RR. So my answer undercounts.

For QUEUES I could see no slick solution so I lined up the Q and S (two ways) and then thought U's together and E's separate in three ways UU_E_E, E_UU_E and E_E_UU. The same strategy for two E's together and U's separate. Finally, both U's together and both E's together in six ways:
UU_EE_, _UU_EE and UU_ _ EE and you can interchange the U's and E's.

 

[Dr.Peterson]

By not distinct i mean I took QU1E1U2E2S. I had such arrangements QU1U2SE1E2, E1E2SU1QU2, U1QE1E2SU2, U1U2QSE1E2, U1QU2SE1E2, etc. Now to imagine in the word MAHARASHTRA will have M_A_A_A_A_H_T_S_R_R_H. I don't know how to arrange very very confused

That's what I guessed you meant; but you hadn't mentioned changing EE to E₁E₂, so I wanted to be sure.

Before we try to go further, we should probably clarify the problem:

In how many different arrangements of letters in the word MAHARASHTRA have R and H never together?

Am I right in thinking that this allows RR and HH, but not RH or HR?

Then I would restate the problem something like this:

Arrange the letters MSTAAARRHH so that R is never adjacent to H.​

Also, it may be helpful to know the context. What have you learned about combinatorics? If this is from a course, what topics were most recently taught? Or is it a challenge (say, from a contest) that we can expect to be as difficult as it appears?

I still have not taken the time to solve it fully; one way or another, I expect to consider multiple cases, but not too many. One possibility is to consider first arrangements of MSTAAARR, and then think about how to place two H's within that, without being next to either R.

And I might try out whatever strategy I consider on QUEUES, to see if it gives the known correct answer.

 

[blamocur]

Arrange the letters MSTAAARRHH so that R is never adjacent to H.

Nitpicking is my middle name, but, still, there are 4, not 3, A's in MAHARASHTRA

 

[Maths Pro]

Am I right in thinking that this allows RR and HH, but not RH or HR?

Yes that's exactly how it is.

 

[Maths Pro]

Also, it may be helpful to know the context. What have you learned about combinatorics? If this is from a course, what topics were most recently taught? Or is it a challenge (say, from a contest) that we can expect to be as difficult as it appears?

I have learned only basics of combinatronics. I still face challenges to comprehend circular permutations. But I am trying. Topics most recently taught were Addition principle, multiplication principle, Extended addition principle, extended multiplication principle, Invariance principle, Factorial notation, properties of factorial notation, Permutations when all objects are distrinct and permutations when repetitions are allowed, permutations when some objects are identical. All was going okay and suddenly this question cropped up

 

[blamocur]

All was going okay and suddenly this question cropped up

Personally, I found this problem difficult too. I'll try remembering to post my solution on Friday.

 

[Dr.Peterson]

Nitpicking is my middle name, but, still, there are 4, not 3, A's in MAHARASHTRA

And making silly errors is my middle name. Hopefully I would have counted letters before actually doing the work ...

I have learned only basics of combinatronics. I still face challenges to comprehend circular permutations. But I am trying. Topics most recently taught were Addition principle, multiplication principle, Extended addition principle, extended multiplication principle, Invariance principle, Factorial notation, properties of factorial notation, Permutations when all objects are distrinct and permutations when repetitions are allowed, permutations when some objects are identical. All was going okay and suddenly this question cropped up

That sounds like enough; what makes this sort of problem harder is not a special tool, but the need to find a model on which to build a method -- that is, a way to imagine creating an arrangement, that will produce each possibility exactly once. There are often several ways to do it, and one may be easier than another. (Actually, I'm often not sure of my answer until I find two different methods that give the same result.)

But now I have been able to find an orderly method that works for QUEUES, which can also apply to MAHARASHTRA. Here it is:

We want to arrange QSEEUU so that U is never adjacent to E.​

​

First arrange QSEE, then insert two U's in legal positions. I'll first insert U and V, then divide by 2 because UV and VU represent the same arrangement.​

​

(1) There are 3! = 6 ways to arrange QSEE with EE together (treating them as a unit). Now, of the 5 locations to put the next letter, 3 are next to an E, so 2 are allowed for U; then similarly 6-3 = 3 are allowed for V. But U and V can be swapped, so this gives 6*2*3/2 = 18 ways.​

​

[for example, with .Q.E.E.S., 2 places are allowed for U, oQxExExSo. Having placed it, say as oQxExExSoUo, there are 3 open places for V. Having placed it, say as QEESVU, both that and QEESUV represent QEESUU.]​

​

(2) There are 4!/2! - 3! = 6 ways to arrange QSEE with EE not adjacent (the rest of the ways to arrange QSEE). Now,of the 5 locations to put the next letter, 4 are next to an E (2 on each side of each E), so 1 is allowed for the first U; then 6-4 = 2 are allowed for V. Again we divide by 2 to get 6*1*2/2 = 6 ways.​

​

[for example, with .Q.E.S.E., 1 place is allowed for U, oQxExSxEx. Having placed it, say as oUoQxExSxEx, there are 2 open places for V. Having placed it, say as UVQESE, both that and VUQESE represent UUQESE.]​

​

This gives a total of 18+6=24 ways.​

The same can be done for MAHARASHTRA. I'll leave that for others to try, rather than give away the full answer (also, rather than risk getting a number wrong). And there may well be an easier way.

 

[Maths Pro]

And making silly errors is my middle name. Hopefully I would have counted letters before actually doing the work ...


That sounds like enough; what makes this sort of problem harder is not a special tool, but the need to find a model on which to build a method -- that is, a way to imagine creating an arrangement, that will produce each possibility exactly once. There are often several ways to do it, and one may be easier than another. (Actually, I'm often not sure of my answer until I find two different methods that give the same result.)

But now I have been able to find an orderly method that works for QUEUES, which can also apply to MAHARASHTRA. Here it is:

We want to arrange QSEEUU so that U is never adjacent to E.​

​

First arrange QSEE, then insert two U's in legal positions. I'll first insert U and V, then divide by 2 because UV and VU represent the same arrangement.​

​

(1) There are 3! = 6 ways to arrange QSEE with EE together (treating them as a unit). Now, of the 5 locations to put the next letter, 3 are next to an E, so 2 are allowed for U; then similarly 6-3 = 3 are allowed for V. But U and V can be swapped, so this gives 6*2*3/2 = 18 ways.​

​

[for example, with .Q.E.E.S., 2 places are allowed for U, oQxExExSo. Having placed it, say as oQxExExSoUo, there are 3 open places for V. Having placed it, say as QEESVU, both that and QEESUV represent QEESUU.]​

​

(2) There are 4!/2! - 3! = 6 ways to arrange QSEE with EE not adjacent (the rest of the ways to arrange QSEE). Now,of the 5 locations to put the next letter, 4 are next to an E (2 on each side of each E), so 1 is allowed for the first U; then 6-4 = 2 are allowed for V. Again we divide by 2 to get 6*1*2/2 = 6 ways.​

​

[for example, with .Q.E.S.E., 1 place is allowed for U, oQxExSxEx. Having placed it, say as oUoQxExSxEx, there are 2 open places for V. Having placed it, say as UVQESE, both that and VUQESE represent UUQESE.]​

​

This gives a total of 18+6=24 ways.​

The same can be done for MAHARASHTRA. I'll leave that for others to try, rather than give away the full answer (also, rather than risk getting a number wrong). And there may well be an easier way.

So when RR are adjacent we have 8x7!/4! ways of arranging them(considering RR as one unit), simultaneously keeping HH adjacent(considering HH as one unit) in remaining 7 places that are not adjacent to RR, right? Example :
1)RR M_A_A_A_A_S_T_ 2)_MRRA_A_A_A_S_T_ 3)_M_ARRA_A_A_S_T_ ..... 8)_M_A_A_A_A_S_TRR
That makes 8x7x7!/4! =11760 ways.

Now when RR are adjacent in 8 places, H not adjacent to another H in 7C2 ways, right? That makes 8x(7C2)x7!/4! i.e 35280 ways. So total 11760 +35280=47040 ways. Am I right so far?

 

[blamocur]

Now when RR are adjacent in 8 places, H not adjacent to another H in 7C2 ways, right? That makes 8x(7C2)x7!/4! i.e 35280 ways. So total 11760 +35280=47040 ways. Am I right so far?

Hopefully I am not breaking the forum's rules too much by publishing my answer, which is 170520. I first ran a brute-force script to get the answer, then went through several erroneous (i.e., with wrong answer) solutions before, hopefully, arriving at a correct one. There is still a tiny probability that my solution is not logically correct but produced the correct answer by chance, so I'll be interested to hear your opinions after I post the solution on Friday.

 

[Maths Pro]

Hopefully I am not breaking the forum's rules too much by publishing my answer, which is 170520.

Please help me understand what am I missing. I was going to multiply 47040 by 2 and take that as an final answer.