IMC 2020 · Day 1 · P1

Let $N = \{1, 2, \dots, n\}$. Consider a word $w$ that satisfies the conditions and let $A, B, C, D \subset N$ be the sets of positions of letters $a$, $b$, $c$ and $d$ in $w$, respectively. By the definition of the words we have $A \sqcup B \sqcup C \sqcup D = N$. The sets $A$ and $B$ are constrained to have even sizes.

In order to construct all suitable words $w$, choose the set $S = A \cup B$ first; by the conditions, $|S| = |A| + |B|$ must be even. It is well-known that an $n$-element set (with $n \ge 1$) has $2^{n-1}$ even subsets, so there are $2^{n-1}$ possibilities for $S$.

If $S = \emptyset$ then we can choose $C \subset N$ arbitrarily, and then the set $D = S \setminus C$ is determined uniquely. Since $N$ has $2^n$ subsets, we have $2^n$ options for set $C$ and therefore $2^n$ suitable words $w$ with $S = \emptyset$.

Otherwise, if $k = |S| > 0$, we have to choose an arbitrary subset $C$ of $N \setminus S$ and an even subset $A$ of $S$; then $D = (N \setminus S) \setminus C$ and $B = S \setminus A$ are determined and $|B| = |S| - |A|$ will automatically be even. We have $2^{n-k}$ choices for $C$ and $2^{k-1}$ independent choices for $A$; so for each nonempty even $S$ we have $2^{n-k} \cdot 2^{k-1} = 2^{n-1}$ suitable words.

The number of nonempty even sets $S$ is $2^{n-1} - 1$, so in total, the number of words satisfying the conditions is $$1 \cdot 2^n + (2^{n-1} - 1) \cdot 2^{n-1} = 4^{n-1} + 2^{n-1}.$$

Let $a_n$ denote the number of words of length $n$ over $\mathcal{A} = \{a, b, c, d\}$ such that $a$ and $b$ appear even number of times. Further, we define the following sequences for the number of words of length $n$, all over $\mathcal{A}$.

• $b_n$ - the number of words with an odd number of $a$'s and even number of $b$'s
• $c_n$ - the number of words with even number of $a$'s and an odd number of $b$'s
• $d_n$ - the number of words with an odd number of $a$'s and an odd number of $b$'s

We will call them $A$-words, $B$-words, $C$-words and $D$-words, respectively.

It is clear that $a_1 = 2$ and that $$a_n + b_n + c_n + d_n = 4^n.$$ First, we find a recurrence relation for $a_n$. If an $A$-word of length $n$ begins with $c$ or $d$, it can be followed by any $A$-word of length $n - 1$, contributing with $2 a_{n-1}$. If an $A$-word of length $n$ begins with $a$, it can be followed by any word of length $n - 1$ that contains an odd number of $a$'s and even number of $b$'s, thus contributing with $b_{n-1}$. If an $A$-word of length $n$ begins with $b$, it can be followed by any word of length $n - 1$ that contains even number of $a$'s and an odd number of $b$'s, thus contributing with $c_{n-1}$. Therefore we have the following recurrence relation: $$\tag{1} a_n = 2 a_{n-1} + b_{n-1} + c_{n-1}.$$ Next, we find a recurrence relation for $b_n$.

If a $B$-word of length $n$ begins with $c$ or $d$, it can be followed by any $B$-word of length $n - 1$, contributing with $2 b_{n-1}$. If a $B$-word of length $n$ begins with $a$, it can be followed by any word of length $n - 1$ that contains even number of $a$'s and even number of $b$'s, contributing with $a_{n-1}$. If a $B$-word of length $n$ begins with $b$, it can be followed by any word of length $n - 1$ that contains an odd number of $a$'s and an odd number of $b$'s, contributing with $d_{n-1} = 4^{n-1} - a_{n-1} - b_{n-1} - c_{n-1}$. Therefore we have the following recurrence relation: $$\tag{2} b_n = b_{n-1} + 4^{n-1} - c_{n-1}.$$ Now observe that $b_k = c_k$ for all $k$, since simultaneously replacing $a$'s to $b$'s and vice versa we get a $C$-word from a $B$-word. Therefore (2) yields $b_n = 4^{n-1}$. Now (1) yields $$a_n = 2 \cdot a_{n-1} + 2 \cdot 4^{n-2}.$$ Solving the last recurrence relation (for example, diving by $2^n$ we get $x_n := a_n 2^{-n}$ satisfies $x_n - x_{n-1} = 2^{n-3}$, and it remains to sum up consecutive powers of 2) we get $$a_n = 2^{n-1} + 4^{n-1}.$$

Consider the sum $$\tag{$*$} \frac{(a+b+c+d)^n + (-a-b+c+d)^n + (-a+b+c+d)^n + (a-b+c+d)^n}{4}.$$ Expanding the parentheses as $$(a+b+c+d)^n = (a+b+c+d)(a+b+c+d) \dots (a+b+c+d),$$ we get a sum of products $x_1 \dots x_n$, $x_i \in \{a, b, c, d\}$, naturally corresponding to the words of length $n$ over the alphabet $\{a, b, c, d\}$. Consider the other terms in the numerator similarly.

If a word $x_1 \dots x_n$ contains $A, B, C, D$ letters $a, b, c$ and $d$ respectively, we get $a^A b^B c^C d^D$ with the coefficient $$\frac{1 + (-1)^{A+B} + (-1)^A + (-1)^B}{4} = \frac{(1 + (-1)^A)(1 + (-1)^B)}{4} = \begin{cases} 1, & \text{if } A \text{ and } B \text{ are even} \\ 0, & \text{otherwise.} \end{cases}$$ Hence, by substituting $a = b = c = d = 1$ in $(*)$ we get the answer $(4^n + 2^{n+1}) / 4 = 4^{n-1} + 2^{n-1}$.