Compute the number of n-tuples that contains odd numbers of 0's and 1's, using generating function

Question

I think the approach should be to break the n-tuples into 3 parts, but I'm trying to solve a simpler problem, by changing the set of choices from $\{0,1,2\}$ to $\{0,1\}$.

My approach in this new problem is to specify two sequences (instead of three as in the original one):

$a_n :=$ number of way to fill a set of n elements with an odd number of 0's. So $$a_n = \{0,1,0,1,0,1,0,1\ldots\}$$

Similarly, $b_n :=$ number of way to fill a set of n elements with an odd number of 1's. So $$b_n = \{0,1,0,1,0,1,0,1,\ldots\}$$

I found that the exponential generating function of $a_n$ and $b_n$ is:

$$\hat{A}(x) = \hat{B}(x)= \sum_{n=0}^\infty \frac{x^{2n+1}}{(2n+1)!} = \sinh(x)$$

I believe that $\hat{C}(x) := \hat{A}(x) \times \hat{B}(x) = \sinh^2(x)$ is the generating function of the modified problem, but I don't know how to simplify it to obtain a closed formula for $c_n$.

Also, am I right to assume that the difference between my problem and the original one is that the solution to the latter is "larger" than the former's?

For example, if $n = 3$, then my problem's $c_n$ should have a count of 0 (since there is no way to have an odd number of 0's and an odd number of 1's that sum into 3), but the original problem's should have a count of 1 (since we can add a 2 into (0,1,_) and obtain a satisfying tuple).

Finally, going from my problem to the original one, how should I think about the remaining sequence?

Answer 1

I don't know if we can complete the problem with that approach. Here's an alternative way to think about it. It will be convenient to define $s_n$ as the amount on $n$-uples with even zeros and odd ones, $r_n$ the amount of $n$-uples with odd zeros and even ones, $e_n$ the $n$-uples with even zeros and ones.

If $n \geq 3$, and $(a_i)_{1 \leq i \leq n}$ is a tuple with odd amount of ones and zeros, we can observe the first two places of the sequence. There are $9$ options, namely

$$ \{(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)\} $$

If we have an even amount of zeros and ones here, it is necessary and sufficient for the sequence to have an odd number of zeros and ones from $a_3$ onwards. There are three of this cases.

If both are odd amounts, we need the rest of the tuple to have even amounts of ones and zeros. There are two of this cases.

For the other four, the remaining part of the sequence should have even zeros and odd ones or vice versa, depending on the case.

This gives the following recurrence

$$ t_{n+2} = 3t_n + 2e_n + 2s_n + 2r_n $$

Now, noting that $t_n + e_n + r_n + s_n = 3^n$, we get

$$ t_{n+2} = t_n + 2\cdot3^{n} $$

and in particular, $t_{n+3} = t_{n+1} + 2\cdot3^{n+1}$, so

$$ t_{n+3} - 3t_{n+2} = t_{n+1} - 3t_n $$

and rewriting,

$$ t_{n+3} =3t_{n+2} + t_{n+1} -3t_n $$

There is a well known result for these type of recurrences, considering the polynomial

$$ P = X^3-3X^2-X+3 $$

Can you take it from here? (Hint below)

Since $P = (X-1)(X+1)(X-3)$, there exist constants $a,b,c \in \mathbb{C}$ such that $t_n = (-1)^na + 1^nb + 3^nc$. Since you know the first values of $t_n$, this is nothing more than solving a linear equation system.

Answer 2

For the exercise stated in the box let $T(x)$ be the generating function corresponding to $t_n$. Then $$ T(x)=\left(\frac{e^x-e^{-x}}{2}\right)\times \left(\frac{e^x-e^{-x}}{2}\right)\times e^x=\sum_{n=0}^\infty\left(\sum\left(\frac{n!}{k_1!k_2!k_3!}\right)\right)\frac{x^n}{n!}\tag{1} $$ where the inner sum ranges over $k_1, k_2, k_3$ such that $k_1+k_2+k_3=n$, $k_1, k_2$ both odd and $k_3>0$. But $$ T(x)=\frac{e^{3x}-2e^{x}+e^{-x}}{4} $$ so taking the coefficients we have that $$ t_n=\frac{1}{4}(3^n-2+(-1)^n)\quad (n\geq 1) $$