Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In how many ways can one arrange all of the letters in the word INFORMATION so that no pair of consecutive letters appears more than once. Eg ININformota is not acceptable as IN appears twice.

So in know there are $11!$ different arrangements of the word information. I need to use the inclusion and exclusion principle to eliminate the words that have repeated pairs of words. I am looking for a hint on how to go about counting the total number of words where IN is repeated twice and then NI is repeated twice, similarly where ON and NO are repeated, IO and OI are repeated. I guess hint whether ION and NOI would have to be considered or not.

share|improve this question
    
I don't think you are right about the $11!$ count... –  Thomas Andrews Jul 24 '13 at 22:06
    
You are right I didn't consider the fact some letters are repeated. So I would divide $11!$ by $2!*2!*2!$ –  Kj Tada Jul 24 '13 at 22:10
    
That's right so far. Now we must remove the bad ones. Have to be kind of careful there are a few doubly bads. This is what Inclusion/Exclusion if for. –  André Nicolas Jul 24 '13 at 22:38
    
thanks Andre, my problem is more so because we arent just dealing with repeated letters eg. IInformaton is allowed. I knnow that if two consecutive letters werent allowed I would take them as 1 i.e. $10!/{(2!*2!)}$ where two I's were consecutive. But in this instance I have to deal with a pair being repeated. –  Kj Tada Jul 24 '13 at 22:47
    
There are $\frac{9!}{(2!)^3}$ words in which IN is repeated (not necessarily like ININ. I think $\dots$INMAIN$\dots$ is also supposed to be bad. –  André Nicolas Jul 24 '13 at 23:43
show 3 more comments

2 Answers

up vote 1 down vote accepted

We give an analysis that bypasses explicit division. But it is essentially the same analyisis as yours.

There are $11$ slots into which we need to put letters. The "I" slots can be chosen in $\binom{11}{2}$ ways. For each such way, the number of ways to select the "N" slots is $\binom{9}{2}$, and then the number of ways to select the "O" slots is $\binom{7}{2}$. Once this is done, the remaining slots can be filled in $5!$ ways, for a total of $$\binom{11}{2}\binom{9}{2}\binom{7}{2}(5!)$.

Now we count the bad choices, where forbidden patterns occur.

First count the number of ways we can have two (say) IN. View this as a single "letter." So there are now $9$ slots to fill. We choose where the IN goes in $\binom{9}{2}$. For each choice we can select the slots for the O's in $\binom{7}{2}$ ways, and then the usual $5!$ for the rest. There is a total of $6$ sequences of length $2$ using different letters from I, N, O. So at first sight we seem to have $(6)\binom{9}{2}\binom{7}{2}(5!)$ bad choices.

However, when we added together the numbers of ways to have the various two-letter sequences repeated, we double-counted the choices where say a sequence like INO appears twice, for it was counted in the IN count and also in the NO count. So from the initial estimate of the bad choices, we must subtract, for OIN and the various others, the number of ways to obtain it. For OIN we have now $7$ slots, of which we must choose $2$. As usual multiply by $5!$, and by the number of permuatations of our $3$-letter set. So we get $3!\binom{7}{2}(5!)$. It follows that the number of "good" sequences is $$\left(\binom{11}{2}\binom{9}{2}\binom{7}{2}-(6)\binom{9}{2}\binom{7}{2}+(3!)\binom{7}{2}\right)(5!).$$

share|improve this answer
    
thanks Andre, you get the same answer as me so I must be correct i my approach but I am definitely intrigued by how you got your answer. Will be looking at it thoroughly a bit later. Thanks again for your help –  Kj Tada Jul 25 '13 at 3:04
    
Except in simple cases, I find it dangerous to deliberately overcount and then adjust. –  André Nicolas Jul 25 '13 at 3:32
add comment

So this is my own attempt at the question.

So total possible ways to permute INFORMATION is $N = 11!/{2!^3} = S_0$

Let $c_1$ be the total number of permutations in which IN and NI is repeated twice $=2*9!/{2!^2}$ $c_2$ is where ON and NO is repeated and $c_3$ is where $IO$ and OI is repeated and $c_1=c_2=c_3$ therefore $S_1 = 3*c_1$

now there are also the three letter words ION and NOI that are little tricky and there are $3!$ ways they can be arranged and thus they are are $3!*7!/{2!}$ lets call this $S_2$

so I am thinkinking it should be $S_0-S_1+S_2 = 4989600-544320+15120=4460400$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.