8
$\begingroup$

Q: How many arrangements of a,a,a,b,b,b,c,c,c are there such that

$\hspace{5mm}$ (i). no three consecutive letters are the same?

$\hspace{5mm}$ (ii). no two consecutive letters are the same?

A:(i). 1314. ${\hspace{5mm}}$ (ii). 174.

I thought of using the General Principle of Inclusion and Exclusion along with letting $p_i$ denote a property that.. , and doing so, I will evaluate $E(0)$, which gives us the number of arrangements without any of the properties.

How do I go about doing that? I am trying to use the method stated above in solving this question, but I am unable to generalize the properties $p_i$.

$\endgroup$
  • $\begingroup$ For the first one : Total no. Of permutations : $\frac{9!}{3!.3!.3!} = 1680$ No of permutations having (at least) three consecutive letters same = $3*\frac{7!}{3!.3!}=420$ Hence no. Of permutations not having any three consecutive letters same = 1680-420=1260 . Are you sure that the answer is 1314? $\endgroup$ – user369582 Sep 28 '16 at 10:14
  • $\begingroup$ @Avi Yes, the answer is 1314 and the question is also from a textbook. $\endgroup$ – Stoner Sep 28 '16 at 10:27
6
$\begingroup$

(i)

For the first question, your idea of using the Inclusion-Exclusion Principle is the correct approach.

The number of distinguishable arrangements of the letters $a, a, a, b, b, b, c, c, c$ is $$\frac{9!}{3!3!3!}$$ where the factors of $3!$ in the denominator are attributable to the fact that interchanging identical letters in a given arrangement does not produce an arrangement that is distinguishable from the original arrangement. Alternatively, we can choose to fill three of the nine positions with $a$'s, three of the remaining six positions with $b$'s, and the remaining three positions with $c$'s, which can be done in $$\binom{9}{3}\binom{6}{3}\binom{3}{3} = \frac{9!}{3!6!} \cdot \frac{6!}{3!3!} \cdot \frac{3!}{3!0!} = \frac{9!}{3!3!3!}$$ ways.

From these, we must exclude those arrangements in which there are three consecutive identical letters.

Next, we count the number of arrangements in which a block of three consecutive identical letters appears. There are three ways to choose which letter appears in the block of three consecutive letters. Treating the block of three identical letters as one object, we have seven objects to arrange, the block and the other six letters. Since those six letters contain two sets of three identical letters, the number of arrangements containing a block of three consecutive letters is $$\binom{3}{1}\binom{7!}{3!3!}$$

However, we have counted arrangements in which two blocks of consecutive identical letters appear twice.

Next, we count arrangements in which two blocks of three consecutive identical letters appear. There are three ways to choose which two letters appear in blocks of three consecutive letters. If we treat each block as an object, we have five objects to arrange, the two blocks and the other three letters. Since the other three letters are identical, the number of arrangements containing two blocks of three consecutive letters is $$\binom{3}{2}\binom{5!}{3!}$$

If we subtract the number of arrangements in which two blocks of three identical letters appear from our initial count of the number of arrangements in which a block of three identical letters appears, we will not have counted arrangements in which three blocks of three identical letters appear since we first counted them three times, then subtracted them three times.

The number of arrangements with three blocks of three consecutive identical objects is $3!$.

By the Inclusion-Exclusion Principle, the number of arrangements in which at least one block of three consecutive letters appears is

$$\binom{3}{1}\binom{7!}{3!3!} - \binom{3}{2}\binom{5!}{3!} + \binom{3}{3}3!$$

so the number of arrangements in which no three consecutive letters are identical is $$\frac{9!}{3!3!3!} - \binom{3}{1}\frac{7!}{3!3!} + \binom{3}{2}\frac{5!}{3!} - \binom{3}{3}3!$$

(ii)

The second problem can also be handled by Inclusion-Exclusion Principle.

We wish to exclude pairs of identical letters.

One pair of consecutive identical letters:

There are three ways to choose the repeated letter. Treating that pair of identical letters as a block leaves us with eight objects, including two sets of three identical letters. The number of ways these objects can be arranged is $$\binom{3}{1}\frac{8!}{3!3!}$$

Two pairs of consecutive identical letters:

There are two cases. We can have three consecutive identical letters (two overlapping pairs) or two distinct pairs of consecutive identical letters (such as $aa$ and $bb$). We found above that there are $$\binom{3}{1}\frac{7!}{3!3!}$$ arrangements with three consecutive identical letters.

For the other case, there are three ways of choosing the letters of the alphabet from which the pairs of consecutive identical letters are chosen. This leaves us with seven objects, the two blocks of consecutive identical letters, the third letter from each chosen type, and the three letters of the third type. Since the three letters of the third type are indistinguishable, the number of such arrangements is $$\binom{3}{2}\frac{7!}{3!}$$ In total, the number of arrangements with two pairs of consecutive identical letters is $$\binom{3}{1}\frac{7!}{3!3!} + \binom{3}{2}\frac{7!}{3!}$$

Three pairs of consecutive identical letters:

Again, there are two cases. We could choose three pairs of consecutive identical letters from different letters of the alphabet or three consecutive identical letters (two overlapping pairs) and a pair of consecutive identical letters from a different letter of the alphabet.

If each pair of consecutive identical letters is from a distinct letter of the alphabet, we have six objects to arrange, $aa$, $bb$, $cc$, $a$, $b$, and $c$. This can be done in $$6!$$ ways.

For the other case, there are three ways of selecting the letter of the alphabet from which three consecutive identical letters are selected, and two ways of selecting the letter of the alphabet from which two consecutive identical letters are selected. Again, we have six objects, the block of three consecutive identical letters, the block of two consecutive identical letters, and the other four letters. Three of those other four letters are indistinguishable, so the number of such arrangements is $$\binom{3}{1}\binom{2}{1}\frac{6!}{3!}$$ Therefore, the total number of arrangement with three consecutive identical letters is $$6! + \binom{3}{1}\binom{2}{1}\frac{6!}{3!}$$

Four pairs of consecutive identical letters:

Again, we have two cases. We have two blocks of three consecutive identical letters (two sets of two overlapping pairs), or we have one block of three consecutive identical letters (two overlapping pairs) with a pair of consecutive identical letters from each of the other letters of the alphabet.

We found above that the number of arrangements with two blocks of three consecutive identical letters is $$\binom{3}{2}\frac{5!}{3!}$$ For the remaining case, there are three ways of choosing the letter of the alphabet with three consecutive identical letters. We have five objects, the block of three consecutive identical letters, the two blocks of two consecutive identical letters, and the two remaining single letters. They can be arranged in $$\binom{3}{1}5!$$ ways. The total number of arrangements with four pairs of consecutive identical letters is then $$\binom{3}{2}\frac{5!}{3!} + \binom{3}{1}5!$$

Five pairs of consecutive identical letters:

For this to occur, there must be two blocks of three consecutive identical letters (two sets of two overlapping pairs) and a block of two consecutive identical letters drawn from the other available letter. There are three ways of selecting the two letters from which the blocks of three identical consecutive letters are drawn. We now have four objects to arrange, the two blocks of three consecutive identical letters, the block of two consecutive identical letters, and the remaining letter. The number of such arrangements is $$\binom{3}{2!}4!$$

Six pairs of consecutive identical letters:

The only ways for this to occur is if we have three blocks of three consecutive identical letters (three sets of two overlapping pairs). We saw above that there are $$3!$$ such arrangements.

By the Inclusion-Exclusion Principle, the number of arrangements of the letters $a, a, a, b, b, b, c, c, c$ in which no two identical letters are consecutive is $$\frac{9!}{3!3!3!} - \binom{3}{1}\frac{8!}{3!3!} + \left[\binom{3}{1}\frac{7!}{3!3!} + \binom{3}{2}\frac{7!}{3!}\right] - \left[6! + \binom{3}{1}\binom{2}{1}\frac{6!}{3!}\right] + \left[\binom{3}{2}\frac{5!}{3!} + \binom{3}{1}5!\right] - \binom{3}{2}4! + \binom{3}{3}3! = 174$$

$\endgroup$
  • $\begingroup$ Wow! Thank you for your clear and precise explanation for part (i)! I get the whole idea now. :) @N.F.Taussig $\endgroup$ – Stoner Sep 28 '16 at 11:57
  • $\begingroup$ For part (ii), am I able to proceed using the General Principle of Inclusion and Exclusion method like the above as well? I thought of it and noted that for each type of letter, e.g. a a a, there are 3 ways to choose a pair (a, a) such that they are consecutive. Is this approach on the right track? $\endgroup$ – Stoner Sep 28 '16 at 11:59
  • $\begingroup$ I would have to think about how to use the Principle of Inclusion and Exclusion for the second part. A brute force approach is to consider where $c$'s can be placed in the arrangements of $a$'s and $b$'s so that no three consecutive letters are identical. The arrangements that begin with $a$ are $$\color{red}{aaabbb}, aababb, aabbab, aabbba, abaabb, ababab, ababba, abbaab, abbaba, abbbaa $$ It is not possible to place the $c$'s in the arrangement shown in red so that no three letters are consecutive. Place $c$'s between double letters first, then place the remaining $c$'s. $\endgroup$ – N. F. Taussig Sep 28 '16 at 13:04
  • $\begingroup$ Hmm.. does your example mean the case where 2 consecutive letters are the same such that I can proceed as follows: number of ways = number of ways without restriction - number of ways such that no 3 letters are consecutive to get the desired result for part (ii)? $\endgroup$ – Stoner Sep 28 '16 at 14:23
  • $\begingroup$ In my comment, I had a completely different brute force solution in mind. Given the arrangement $aababb$, we must place a $c$ between the two $a$'s and a $c$ between the two $b$'s, which yields $acababcb$. We can now place the third $c$ at the beginning, at the end, or one of the three positions in which we change from $a$ to $b$ or $b$ to $a$, giving five possible arrangements. Repeat for the remaining cases. However, I figured out how to do the problem using the Inclusion-Exclusion Principle. I have edited my solution accordingly. $\endgroup$ – N. F. Taussig Sep 29 '16 at 0:43
4
$\begingroup$

This answer is based upon a generating function of generalized Laguerre polynomials \begin{align*} L_k^{(\alpha)}(t)=\sum_{i=0}^k(-1)^k\binom{k+\alpha}{k-i}\frac{t^i}{i!} \end{align*}

The Laguerre polynomials have some remarkable combinatorial properties and one of them is precisely suited to answer problems of this kind. This is nicely presented in Counting words with Laguerre series by Jair Taylor. We find in section $3$ of this paper:

Theorem: If $m_1,\ldots,m_k,n_1,\ldots,n_k$ are non-negative integers, and $p_{m,n}(t)$ are polynomials defined by \begin{align*} \sum_{n=0}^\infty p_{m,n}(t)x^n=\exp\left(\frac{t\left(x-x^m\right)}{1-x^m}\right) \end{align*} then the total number of $k$-ary words that use the letter $i$ exactly $n_i$ times and do not contain the subwords $i^{m_i}$ is \begin{align*} \int_0^\infty e^{-t}\prod_{j=1}^k p_{m_j,n_j}(t)\,dt \end{align*}

Here we consider a $3$-ary alphabet $\{a,b,c\}$ and words built from the characters $$a,a,a,b,b,b,c,c,c$$

First case: Bad words $\{aaa,bbb,ccc\}$

We have $m_1=m_2=m_3=3, n_1=n_2=n_3=3$

We obtain with some help of Wolfram Alpha

\begin{align*} p_{3,3}(t)&=[x^3]\exp\left(\frac{t\left(x-x^3\right)}{1-x^3}\right)\\ &=[x^3]\left(1+tx+\frac{1}{2}t^2x^2+\left(\frac{1}{6}t^3-t\right)x^3+\cdots\right)\\ &=\frac{1}{6}t^3-t \end{align*}

It follows

\begin{align*} \int_0^\infty e^{-t}\left(\frac{1}{6}t^3-t\right)^3\,dt=1314 \end{align*}

Second case: Bad words $\{aa,bb,cc\}$

We have $m_1=m_2=m_3=2, n_1=n_2=n_3=3$ and obtain

\begin{align*} p_{2,3}(t)&=[x^3]\exp\left(\frac{t\left(x-x^2\right)}{1-x^2}\right)\\ &=[x^3]\left(1+tx+\left(\frac{1}{2}t^2-t\right)x^2+\left(\frac{1}{6}t^3-t^2+t\right)x^3+\cdots\right)\\ &=\frac{1}{6}t^3-t^2+t \end{align*}

It follows

\begin{align*} \int_0^\infty e^{-t}\left(\frac{1}{6}t^3-t^2+t\right)^3\, dt=174 \end{align*}

$\endgroup$
  • $\begingroup$ Wow this is an interesting read! Unfortunately my study of math is not so far as of now.. Mind if I ask which area of mathematics is the generalized Laguerre polynomials found in? $\endgroup$ – Stoner Sep 29 '16 at 14:37
  • $\begingroup$ @Stoner: Never mind! Just keep in mind for the future there was something with Laguerre and counting words. You might face them when studying orthogonal polynomials, differential equations or more general real/complex analysis and of course combinatorics. :-) $\endgroup$ – Markus Scheuer Sep 29 '16 at 15:02
  • 1
    $\begingroup$ Ah I will be taking advanced courses in real and complex analysis in the near future and also that of combinatorics! Thanks again for your help and insight! :) $\endgroup$ – Stoner Sep 29 '16 at 15:59
  • $\begingroup$ @Stoner: Great! You're welcome! $\endgroup$ – Markus Scheuer Sep 29 '16 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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