A combinatorial question about odd and even numbers

Question

Consider an $n$ tuple. Each index of the tuple is filled with a symbol chosen from the following set comprising of four symbols: \begin{equation} S = \{a, b, c, d\}. \end{equation}

Note that there are $4^{n}$ possible fillings.

I want to count the number of possible tuples such that $b$-s, $c$-s, and $d$-s all occur in it an even number of times (not necessarily the same even number for each.)

For example, if $n = 4$, then $bbba$ is not a valid tuple --- as it has $3$ $b$-s, which is an odd number. However $bb cc$ is a valid tuple — as both $b$ and $c$ occur an even number of times.

---

For $n = 2$, the valid choices are $aa, bb, cc, dd$.

Hence, the number of such tuples is $4$.

For $n = 3$, the valid choices are $aaa, abb, acc, add, bba, cca, dda, bab, cac, dad$.

So, $10$ choices.

Is there a general pattern?

Answer 1

Imagine that $a,b,c,d$ are variables. Then the polynomial $(a+b+c+d)^n$, when expanded out, lists precisely the $4^n$ possible tuples. (This would be exactly true if the variables didn't commute. Expanding as a usual polynomial will gather all the tuples with the same numbers of $a$s, $b$s, $c$s, and $d$s; fortunately the property we care about is fine with that.)

For each such monomial, if we plug in $b=1$ and then $b=-1$ and sum, then we get $0$ if the monomial has an odd number of $b$s and a contribution of $2$ of the (slightly simplified) monomial if it has an even number of $b$s. The same holds true with $c$ and $d$; and we can simply set $a=1$ to not care about its parity. Therefore the number of such tuples is exactly $$ \frac18 \sum_{b\in\{-1,1\}} \sum_{c\in\{-1,1\}} \sum_{d\in\{-1,1\}} (1+b+c+d)^n = \frac{4^n+3\cdot 2^n+(-2)^n}8. $$ This appears to be sequence A032121 in the Online Encyclopedia of Integer Sequences, which definitely refers to $n$-tuples on a $4$-symbol alphabet, although the property seems different from what is described here.

Answer 2

For a generating function approach:

Let $F_i(z)$ be the OGF of the number of words where exactly $i$ out of $\{b,c,d\}$ occur an odd number of times in the word. For example, $F_1(z)$ at $n=3$ counts $aab$, $aac$, $aad$, $bbb$, $bbc$, $bbd$, $ccb$, $ccc$, $ccd$, $ddb$, $ddc$, $ddd$ and permutations of these, for a total of $30$. $F_0(z)$ is what we want.

By conditioning on the final letter, we get the recursive relationship $$ \begin{array}{lll} F_0 &= &1 &+ &F_0\cdot z&+&F_1\cdot z&& \\ F_1 &= &&&F_0\cdot 3z &+ &F_1\cdot z &+ &F_2\cdot 2z &\\ F_2 &= &&&&&F_1\cdot 2z &+ &F_2\cdot z &+ &F_3\cdot 3z \\ F_3 &= &&&&&&&F_2\cdot z &+ &F_3\cdot z\ , \end{array} $$ which solves to $$ F_0(z) = \frac{6z^3-4z^2-3z+1}{16z^3-4z^2-4z+1} = \frac18\left( 3 + \frac{1}{1-4z} + \frac{3}{1-2z} + \frac{1}{1+2z} \right) . $$ From the partial fraction decomposition we immediately get $$ [z^n]F_0(z) = \frac{4^n+3\cdot2^n+(-2)^n}{8} $$ for $n\ge1$ (and $1$ for $n=0$).

Answer 3

Since this is tagged combinatorial-proofs, here’s a purely bijective solution. Let the “signature” of a tuple be the numbers of $b$s, $c$s, and $d$s mod 2, and let $x_s$ be the number of tuples with signature $s$ (so we seek $x_{000}$).

By the symmetry $b → c → d → b$, we have $x_{100} = x_{010} = x_{001}$ and $x_{110} = x_{101} = x_{011}$. We can count all $4^n$ tuples as follows:

$$x_{000} + 3x_{100} + 3x_{011} + x_{111} = 4^n. \tag{1}$$

Consider the transformation that flips the first letter that’s $a$ or $b$ to $b$ or $a$, respectively. This is a self-inverse transformation that exchanges signatures $000 ↔ 100$, $010 ↔ 110$, $001 ↔ 101$, $011 ↔ 111$, except that it fails on the $2^n$ tuples made entirely from $c$ and $d$. If $n$ is even, the signatures of these failing tuples are half $000$ and half $011$; if $n$ is odd, they’re instead half $010$ and half $001$. So:

\begin{gather*} x_{000} - x_{100} = 2^{n - 2} + (-2)^{n - 2}, \tag{2} \\ x_{011} - x_{111} = 2^{n - 2} + (-2)^{n - 2}, \tag{3} \\ x_{010} - x_{110} = 2^{n - 2} - (-2)^{n - 2}, \tag{4} \\ x_{001} - x_{101} = 2^{n - 2} - (-2)^{n - 2}. \tag{5} \\ \end{gather*}

By $\text{(1)} + 7·\text{(2)} + \text{(3)} + 4·\text{(4)}$, we have

$$8x_{000} = 4^n + 8(2^{n - 2} + (-2)^{n - 2}) + 4(2^{n - 2} - (-2)^{n - 2}), \\ x_{000} = \frac{4^n + 3·2^n + (-2)^n}{8}.$$

Answer 4

This problem is amenable to exponential generating functions. Indeed, the egf for the $a$'s is given by $$ A(x)= \sum_{n=0}^\infty\frac{x^n}{n!}=e^x $$ while the egfs for the $b$'s, $c$'s and $d$'s are simulatenously equal to $$ B(x)=\sum_{n=0}^\infty\frac{x^{2n}}{(2n)!}=\frac{e^x+e^{-x}}{2}. $$ Hence the egf for the number of words of length $n$ with the required restrictions $c_n$ is given by $$ C(x) = A(x)B(x)^3 = \sum_{n=0}^\infty\left( \sum_{ \substack{x_{1}+x_{3}+x_{3} + x_{4} = n\\ \quad x_{1}\geq 0, \;x_{2},\; x_{3}, \; x_{4} \;\text{even}}} \frac{n!}{x_1!x_2!x_3!x_4!}\right)\frac{x^n}{n!}=\sum_{n=0}^\infty c_n \frac{x^n}{n!}.\tag{0}$$

But $$ A(x)B(x)^3=\frac{1}{8}(e^{4x}+3e^{2x}+3+e^{-2x})=1+\sum_{n=1}^\infty\left(\frac{4^n+3(2^n)+(-2)^n}{8}\right)\frac{x^n}{n!}.\tag{1} $$ Comparing (0) and (1) it follows that $c_0 = 1$ (empty word) and $$ c_n = \frac{4^n+3(2^n)+(-2)^n}{8}; \quad( {n\geq 1}). $$