A combinatorial question about odd and even numbers 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?
 A: 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.
A: 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}.$$
A: 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}).
$$
A: 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$).
