Number of words with $3n$ letters where no $3$ consecutive letters are the same

Question

This is similar to this question, and I wanted to apply the technique of inclusion-exclusion to see if I understand it. I try to explain as many details as possible in my reasoning, and I would like to know if my solution is correct?

In an alphabet of $n$ distinct letters, how many words of length $3n$, where each letter appears $3$ times, can be formed such that no $3$ consecutive letters are the same?

Attempt.

Suppose first that the identical letters are distinguishable. Choose $k$ letters to form consecutive triples in our word, where $k=0,1,...,n$. There are ${n \choose k}$ choices for these letters. Then, we may order the remaining letters arbitrarily, of which there are $(3n-k)!$ ways to do so, since these are just permutations. Implicitly, we are regarding each triple as one letter.

Next, since we assumed the identical letters are distinguishable, each triple has $3!=6$ different orderings, giving a total of $6^k$ different orderings for our $k$ triples, by the product rule. These three steps are independent, so by the product rule, we get there are ${n \choose k}(3n-k)!6^k$ words with $k$ consecutive triples.

However, we now must account for the fact that there are identical letters. Each triple has $3!=6$ different orderings, so we have to divide by $6^n$ to remove the duplicate words. Thus, by principle of inclusion-exclusion, the total number of words is $$\sum_{k=0}^n \frac{1}{6^n} (-1)^k{n\choose k} (3n-k)!6^k = \frac{1}{6^n} \sum_{k=0}^n (-1)^k {n \choose k}(3n-k)!6^k.$$

Answer 1

Your proposed formula returns $-1$ when $n=1$ so cannot be correct.

You have the right idea, but when you remove $k$ occurrences of consecutive triples, there are $3n-3k$ letters remaining to permute.

To use your approach of treating each consecutive triple as a single letter, when you consider $k$ occurrences of consecutive triples, there are $3n-2k$ letters to permute because you lose $2$ letters for each triple.

Answer 2

This response is somewhat off point, because I am not directly addressing the original poster's request to evaluate his work. I found the original poster's analysis simply too confusing to review. So, I will simply describe how I would use Inclusion-Exclusion to attack the problem. Then, the original poster can review my response to see if they have any questions.

First, see this article for an introduction to Inclusion-Exclusion. Then, see this answer for an explanation of and justification for the Inclusion-Exclusion formula.

My approach will adopt the syntax of the second link above.

---

First, as is standard for this type of problem, I will (arbitrarily) regard instances of the same letter as indistinguishable.

Let $~S~$ denote the collection of all words of length $~3n~$ formed from an alphabet of $~n~$ letters, where each letter is used exactly $~3~$ times. So, the set $~S~$ includes words where consecutive letters do occur.

For $~k \in \{1,2,\cdots,n\},~$ let $~S_k~$ denote the subset of $~S,~$ where Letter-$k~$ occurs in three consecutive positions somewhere in the word.

Then, the desired computation is

$$|S| - |S_1 \cup S_2 \cup \cdots \cup S_n|. \tag1 $$

Note
An alternative approach, that I regard as just as difficult, would have been to have $~k \in \{1,2,\cdots,3n-2\},~$ and let $~S_k~$ denote the subset of $~S~$ where some triplet of three consecutive letters occurs in Position-$k.~$

I initially took the alternate approach, then changed my mind. The configuration of $~S_k~$ that I adopted seems easier for me to work with.

---

Let $~T_0~$ denote |S|.

For $~r \in \{1,2,\cdots,n\},~$

let $~T_r~$ denote $~\displaystyle \sum_{1 \leq i_1 < i_2 < \cdots < i_r \leq n} | ~S_{i_1} \cap S_{i_2} \cap \cdots \cap S_{i_r} ~|.$

That is, $~T_r~$ represents the sum of $~\displaystyle \binom{n}{r}~$ terms.

Then, by Inclusion-Exclusion theory, the computation in (1) above is equivalent to

$$\sum_{r=0}^n (-1)^r T_r. \tag2 $$

Therefore, the problem has been reduced to determining the formula for each $~T_r ~: ~r \in \{0,1,2,\cdots,n\}.~$

---

$\underline{\text{Computation of} ~T_0}$

$$T_0 = \binom{3n}{3} \times \binom{3n-3}{3} \times \cdots \times \binom{6}{3} \times \binom{3}{3} = \frac{(3n)!}{[3!]^n}. \tag3 $$

(3) above is explained by reasoning that there are $~\displaystyle \binom{3n}{3}~$ ways of positioning Letter-1. Once Letter-1 is positioned, there are then $~\displaystyle \binom{3n-3}{3}~$ ways of positioning Letter-2, and so forth.

---

$\underline{\text{Computation of} ~T_1}$

First, I will specifically compute $~|S_1|.~$

There are $~\displaystyle \binom{3n-2}{1}~$ possible starting positions for the three consecutive characters Letter-1, Letter-1, Letter-1.

Then, once the Letter-1 triplet is positioned, similar to the analysis in the computation of $~T_0,~$ there are then $~\displaystyle \frac{[3(n-1)]!}{[3!]^{n-1}}~$ ways of positioning the remaining letters.

Further, by symmetrical considerations, you have that $~|S_k| = |S_1| ~: ~k \in \{2,3,\cdots,n\}.$

Therefore,

$$T_1 = \binom{n}{1} \times \binom{3n-2}{1} \times \frac{[3(n-1)]!}{[3!]^{n-1}}. \tag4 $$

---

$\underline{\text{Helper Function} ~f(r)}$

Before continuing with $~T_2, T_3, \cdots,~$ I am going to define a helper function $~f(r),~$ for $~r \in \{2,3,\cdots,n\},~$ as follows.

Let $~f(r)~$ denote the number of ways of positioning Letter-1, Letter-2, ..., Letter-r under the assumptions that:

• Each of the $~r~$ letters is used to form a triplet of $~3~$ consecutive letters.

• The Letter-1 triplet occurs first, followed by the Letter-2 triplet, followed by the Letter-3 triplet, and so forth.

• No consideration is given to the number of ways of then distributing the remaining $~(3n-3r)~$ letters represented by Letter-(r+1), Letter-(r+2), ..., Letter-n.

Then, as explained below, the computation of $~f(r)~$ is a Stars and Bars problem. For Stars and Bars theory, see this article and this article.

Consider the following tableau

_ _ L-1 _ _ L-2 _ _ ... _ _ L-r _

In the above tableau, you start with $~3n~$ positions. Then $~3r~$ of these positions are occupied by the $~r~$ letters. So, you have $~(3n-3r)~$ positions that are available for the remaining $~(n-r)~$ letters. Further, as shown in the tableau above, the $~r~$ letters create $~(r+1)~$ islands.

Let $~x_1, x_2, \cdots, x_{r+1}~$ denote the size of each of these islands, respectively. There is a bijection between any satisfying ordered $~(r+1)$-tuple $~(x_1, \cdots, x_{r+1})~$ and any satisfying distribution of Letter-1, Letter-2, ..., Letter-r (in that order) as triplets.

Therefore $~f(r)~$ equals the number of solutions to:

• $x_1 + x_2 + \cdots + x_{r+1} = 3n - 3r.$

• $x_1, x_2, \cdots, x_{r+1} \in \Bbb{Z_{\geq 0}}.$

By Stars and Bars theory, you therefore have that

$$f(r) = \binom{[3n-3r] + r}{r} = \binom{3n-2r}{r}. \tag5 $$

---

$\underline{\text{Computation of} ~T_r ~: 2 \leq r \leq n}$

First, assume that you are trying to compute the very first term in $~T_r,~$ which represents $~|S_1 \cap S_2 \cap \cdots \cap S_r|.~$

So, Letter-1, Letter-2, ..., Letter-r will all be triplets.

These $~r~$ triplets can be positioned in $~(r!) \times f(r)~$ ways.

Further, once these triplets are positioned, by analysis similar to that in the previous sections, the remaining $~(3n - 3r)~$ letters can be positioned in $~\displaystyle \frac{[3(n-r)]!}{[3!]^{n-r}}~$ ways.

Therefore,

$$~|S_1 \cap S_2 \cap \cdots \cap S_r| = (r!) \times f(r) \times \frac{[3(n-r)]!}{[3!]^{n-r}}.$$

Then, by considerations of symmetry, you have that

$$T_r = \binom{n}{r} \times |S_1 \cap S_2 \cap \cdots \cap S_r|.$$

Therefore,

$$T_r = \binom{n}{r} \times (r!) \times f(r) \times \frac{[3(n-r)]!}{[3!]^{n-r}}$$

$$= \frac{n!}{(n-r)!} \times \binom{3n-2r}{r} \times \frac{[3(n-r)]!}{[3!]^{n-r}}. \tag6 $$

---

$\underline{\text{Final Computations}}$

$$|S| - |S_1 \cup S_2 \cup \cdots \cup S_n| = \sum_{r=0}^n (-1)^r T_r. $$

$$T_0 = \frac{(3n)!}{[3!]^n}.$$

$$T_1 = \binom{n}{1} \times \binom{3n-2}{1} \times \frac{[3(n-1)]!}{[3!]^{n-1}}. $$

For $~r \in \{2,3,\cdots,n\}:~$

$$T_r = \frac{n!}{(n-r)!} \times \binom{3n-2r}{r} \times \frac{[3(n-r)]!}{[3!]^{n-r}}.$$

---

$\underline{\text{Addendum}}$

If you wish to consider all $~3n~$ letters as distinguishable, the adjustment to my analysis is minor.

In any distribution of the $~(3n)~$ letters, there are $~(3!)~$ ways of permutting the three occurrences of Letter-k, regardless of where Letter-k occurs, for each $~k \in \{1,2,\cdots,n\}.~$

Therefore, you simply apply the scalar of $~(3!)^n~$ to my final computations.