1
$\begingroup$

Compute the number of words made of $2n$ letters taken from the alphabet $\{a_1, a_2,\ldots,a_n\}$ such that each letters occurs exactly twice and no two consecutive letters are equal.

I started first of all thinking about the possibilities when we are not restricted by the fact that two consecutive letters are equal. Because we need to choose $2n$, and letters occur exactly twice, so that we can permute each letter pair $2!$ times, we will have something like this: $$\frac{2n!}{(2!)^n} = \frac{2n!}{2^n}$$ Now, I have to somehow exclude the possibilities when two consecutive letters are equal. I was stuck here, then I came across the answer to the problem (which I assume is the same problem), from Putnam and Beyond, page 326 in the PDF, and 309 of the book. I see that he has used inclusion-exclusion principle, but I didn't quite get how the numbers were obtained. Any explanation of that answer, or another solution is highly welcomed.

$\endgroup$
1
$\begingroup$

The strategy taken is to find the total number ways to arrange the letters $-$ the total number of ways to arrange the letter such that at least one pair of letters are together.

The total number of ways to arrange the letter as you have found is: $$\frac{(2n)!}{2^n}$$ Let $A_i$ be the number of ways to arrange the $2n$ letters such that $i^{th}$ pair are together. Therefore, we need to find:

$$|\overline{A_1 \cup A_2 \cup \dots \cup A_n}|=\frac{(2n)!}{2^n}-|A_1 \cup A_2 \cup \dots \cup A_n|$$

$\sum_{i=1}^n|A_i|$ is the number of ways to arrange the letters with any $1$ pair together and is given by:

$$\binom{n}{1}\frac{(2n-1)!}{(2!)^{n-1}}$$

This is because we arrange the remaining $2n-2$ letters and the $1$ grouped pair. After which we divide by $(2!)^{n-1}$ as there are $n-1$ remaining pairs.

Next, we have to find $\sum_{1 \leq i,j \leq n} |A_i \cap A_j|$, the case when any two pairs are together. Using a similar argument, we have:

$$\binom{n}{2}\frac{(2n-2)!}{(2!)^{n-2}}$$

Extending this to the $k^{th}$ case, to find $\sum_{1 \leq i,j \dots,k \leq n} |A_i \cap A_j\dots \cap A_k|$ we can extend the formula to:

$$\binom{n}{k}\frac{(2n-k)!}{(2!)^{n-k}}$$

Using the inclusion and exclusion principle,

$$|\overline{A_1 \cup A_2 \cup \dots \cup A_n}| =\frac{(2n)!}{2^n}-\sum_{i=1}^n|A_i|+\sum_{1 \leq i,j \leq n} |A_i \cap A_j|-\sum_{1 \leq i,j \dots,k \leq n} |A_i \cap A_j\dots \cap A_k|$$

$$\quad \quad \quad \quad \quad =\frac{(2n)!}{2^n}-\binom{n}{1}\frac{(2n-1)!}{(2!)^{n-1}}+\binom{n}{2}\frac{(2n-2)!}{(2!)^{n-2}}+\dots+(-1)^k\binom{n}{k}\frac{(2n-k)!}{(2!)^{n-k}}$$

$$=\sum_{k=0}^n(-1)^k\binom{n}{k}\frac{(2n-k)!}{(2!)^{n-k}}$$

$\endgroup$
0
0
$\begingroup$

I'll expand slightly on the answer.

We assume we have $2n$ letters $L = \{a_1,\ldots,a_n,a'_1,\ldots,a'_n\}$ that we permute in $(2n)!$ ways. Then we consider $a_i$ and $a'_i$ to be the same letter, so that the end result is garantueed to have all letters exactly twice. But then we can exchange every pair $a_i$, $a'_i$ without affecting the end result, so we have to divide by $(2!)^n = 2^n$. So we $\frac{(2n)!}{2^n}$ total permutations.

So we have to count all permuations that have some pair (or more) of adjacent equal letters. So define $A_k$ to be the subset of all permutations of $L$ such that $a_k$ is next to $a'_k$.

Then

$$\biggl|\bigcup_{i=1}^n A_i\biggr| = \sum_{i=1}^n\left|A_i\right|\; -\sum_{1 \le i < j \le n}\left|A_i\cap A_j\right|\; + \sum_{1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|\;-\ \ldots\ +\; \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right|\text{.}$$

The total minus this number is what we are looking for.

Now to count $A_k$ for a fixed $k$, we create a fake letter $A_k$ which equals $a_k a'_k$. Then we permute $L \cup \{A_k\} \setminus \{a_k, a'_k\}$, which has $(2n-1)$ elements. After permuting those in $(2n-1)!$ many ways, we identify the $a_i, a'_i$ for $i \neq k$ again, so we have $\frac{(2n-1)!}{2^{n-1}}$ such permutations. So the sum of the $A_i$ is just $n$ that (once for every index).

Now for the intersections of $l$ many $A_k$, we create $l$ fake letters $A_i$, and then permute $(2n- l)!$ many letters, divide by $2^{n-l}$ (for switching the remaining letters), and note that we have $\binom{n}{k}$ many such intersections, all with the same number.

Now plug in the formula.

$\endgroup$

Your Answer

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