0

I have been given the following problem:
Use generating functions to determine the number of 10-digit ternary $(0,1,2)$ sequences in which the digit $2$ occurs at least once, and the digit $0$ occurs an even number of times.

My work thus far:
I know that the general formula is $$ r=t_0+t_1+t_2 $$ with $r=10$ and $t_0,t_1,t_2$ are just the number of occurrences for $0,1$ and $2$ respectively.
Next I have the following generating functions:
For ternary functions, the generating function is $$ r=(u_0+u_1+u_2)^n $$ with the digits $0,1,2$ being represented by $u_0,u_1,u_2$ and $n=10$.
For the constraint that there is an even number of $0-$digits, the formula is: $$ \frac{1}{2}\left((u_0+u_1+u_2)^n+(-u_0+u_1+u_2)^n\right) $$ I am however unsure as to how to implement the second constraint into the equation, namely that $1 \le u_2$, i.e. $1\le u_2 \le 10$

Firstly, is my work thus far correct?
Secondly, can anyone help me with the second constraint?

Martin Sieburg
  • 143

1 Answers1

0

I'm not sure how to bring generating functions in, but here's a way to get the answer without them.

You can choose $2k$ zeroes in $\displaystyle{10\choose2k}$ ways. Then the other $10-2k$ places can be filled with ones and twos, which would be $2^{10-2k}$ ways, but you can't have all twos, so $2^{10-2k}-1$ admissible ways. So, the number of admissible sequences with $2k$ zeros is $\displaystyle{10\choose2k}(2^{10-2k}-1)$. Summing on $k$, the total number of admissible sequences is $$ \sum_{k=0}^5{10\choose2k}(2^{10-2k}-1) $$ which we can write as $$ \sum_{k=0}^5{10\choose2k}2^{10-2k}-\sum_{k=0}^5{10\choose2k} $$ The Binomial Theorem says $$ 3^{10}=(2+1)^{10}=\sum_{r=0}^{10}{10\choose r}2^{10-r},\qquad1=1^{10}=(2-1)^{10}=\sum_{r=0}^{10}{10\choose r}2^{10-r}(-1)^r $$ Adding these together, and dividing by two, gives $$ (3^{10}+1)/2=\sum_0^5{10\choose2k}2^{10-2k} $$ A similar trick with $2^{10}+0^{10}=(1+1)^{10}+(1-1)^{10}$ gives $\sum_{k=0}^5{10\choose2k}=2^9$. So, the answer is $$ {3^{10}-2^{10}+1\over2}=29013 $$

Gerry Myerson
  • 179,216