arranging letters without repetition

Question

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.

Answer 1

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!).$$

Answer 2

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$