7
$\begingroup$

Just starting to appreciate recurrence relations

Let $T_n = $ number of length-n ternary sequences with an even number of ones and an even number of zeroes.

$T_0 = 1$, because $0$ is an even number, and there are zero $1$s and zero $0$s.

$T_1 = 1$, because the sequence $\{2\}$ has zero $1$s and zero $0$s

How to find $T_n$?

Possibility: split into cases.

Case 1: We have an $n$ digit sequence with an even number of $0$s and an even number of $1$s.

To get to length $n$, we have all of the length $n-1$ sequences with an even number of $0$s and $1$s, which is $T_{n-1}$

Case 2: We have an $n$ digit sequence with an odd number of $0$s and an odd number of $1$s.

Here, we basically need the total amount of length-$n$ sequences with an odd number of $0$s and an odd number of $1$. This should be $3^n - T_{n-1}$.

Case 3: We have an even number of 0s, but an odd number of 1s.

Case 4: We have an odd number of 0s, but an even number of 1s.

How to account for cases 3 and 4?

$\endgroup$
  • $\begingroup$ Easier to go from $T_{n-2}$ to $T_n$ by inserting either two of "$0$"s or two of "$1$"s. This maintains the invariant that there are an even number of each of zeroes and ones. The question is, how many distinct places can you insert them? $\endgroup$ – Eric Towers May 1 '14 at 3:20
  • $\begingroup$ Alternatively, how many "$2$"s are there in a sequence length $n$, ($n$ even: an even number; $n$ odd: an odd number) How can they be distributed around? Of the remaining elements what choices for $k$ of these are zeroes and $\ell$ of these are ones, and how many ways can those be permuted? $\endgroup$ – Eric Towers May 1 '14 at 3:22
  • $\begingroup$ For the first comment, does that imply that $T_n = 2(T_{n-2})$? $\endgroup$ – compguy24 May 1 '14 at 3:45
  • $\begingroup$ Absolutely not: $2 \rightarrow 002, 020, 200$. $\endgroup$ – Eric Towers May 1 '14 at 3:47
  • $\begingroup$ Sorry, of course that is wrong. What does this comment mean "n even: an even number"? $\endgroup$ – compguy24 May 1 '14 at 3:48
4
$\begingroup$

Let $T_n$ be as in the post. Let $U_n$ be the number of $n$-sequences with an odd number of $0$ and an even number of $1$. Let $V_n$ be the number with an even number of $0$ and an odd number of $1$. (Note that by symmetry $U_n=V_n$.) Let $W_n$ be the number of $n$-sequences with an odd number of $0$ and an odd number of $1$. We have $$T_{n+1}=T_n +U_n+V_n.$$ This is because we can get a sequence of length $n+1$ with an even number of $0$ and of $1$ by appending a $2$ to such a sequence of length $n$, or by appending a $0$ to a sequence of length $n$ with an odd number of $0$ and an even number of $1$, or doing something similar to an $n$-sequence with an even number of $0$ and an odd number of $1$. Similarly, $$U_{n+1}=T_{n}+U_n+W_n,$$ $$V_{n+1}=T_n+V_n+W_n,$$ $$W_{n+1}=U_n+V_n+W_n.$$ A general way to attack the problem is then to express the above $4$ relationships in matrix terms, and using some linear algebra. That is, I believe, the best approach.

But we can bypass that by some manipulation. Use the fact that $V_n=U_n$ and $T_n+2u_n+W_n=3^n$. Then the first two recurrences can be rewritten as $$T_{n+1}=T_n+2U_n,$$ $$U_{n+1}=3^n-U_n.$$ Multiply each side of the first recurrence by $2$, and add. We get $$T_{n+1}+2U_{n+1}=T_n+2\cdot 3^n.\tag{1}$$ By bumping up the indices of the first recurrence by $1$, we get $$T_{n+2}=T_{n+1}+2U_{n+1}=T_{n+1}+ T_n +2\cdot 3^n-T_{n+1}=T_n+2\cdot 3^n.$$ We have reached the recurrence $$T_{n+2}=T_n+ 2\cdot 3^n.$$ This can be solved by standard methods.

$\endgroup$
  • $\begingroup$ Your system of recurrences gives a system of equations for generating functions, solve for them and you get a generating function for the result. $\endgroup$ – vonbrand May 1 '14 at 22:24
  • $\begingroup$ Yes, that is a good way to do it. However, in this case we can get a simple closed form, which is probably best. $\endgroup$ – André Nicolas May 1 '14 at 22:59
2
$\begingroup$

Consider the string $\underbrace{0\cdots0}_{2i}\underbrace{1\cdots 1}_{2j}\underbrace{2\cdots 2}_{k}$, and $2i+2j+k=n$, $i,j,k\in\Bbb N_0$. Then you're looking for $$v_n=\sum_{2i+2j+k=n}\binom{n}{2i,2j,k}$$

Note $v_0=1,v_1=1,v_2=3,v_3=7,v_4=21,v_5=81,\ldots$. This can be tackled as follows.

We have $$w_n=\frac{v_n}{n!}=\sum_{2i+2j+k=n}\frac 1{(2i)!}\frac 1{(2j)!}\frac 1{k!}$$

Now we may write $$w_n=\sum_{k=0}^n\frac{1}{k!}\sum_{2i+2j=n-k}\frac{1}{(2i)!}\frac{1}{(2j)!}$$

that is $$w_n=\sum_{k=0}^n \frac{1}{k!}u_{n-k}$$ with $$u_n=\sum_{2i+2j=n}\frac{1}{(2i)!}\frac{1}{(2j)!}$$

It is evident that $u_{2n+1}=0$, $u_0=1$ and $(2n)!{u_{2n}}=\displaystyle\sum_{i=0}^n\binom{2n}{2i}=2^{2n-1},n\geqslant 1$ (this can be seen by expanding $2^{2n}$ as $(1+1)^{2n}$ and $0$ as $(1-1)^{2n}$ and killiog odd numbers by adding), so that for $n\geqslant 1$ $${v_n} = 1+\frac{1}{2}\sum\limits_{k\;\rm even>0}^n\binom nk2^{k} $$

This matches Andre's recurrence.

$\endgroup$
  • $\begingroup$ I've added a solution which gives your formula almost instantly by setting up a bijection. $\endgroup$ – Calvin Lin May 1 '14 at 12:27
1
$\begingroup$

Consider all the strings with an even number of total ones and zeros. Let there be $k$ total one's and zeros. Then $k$ is even. Fix $k$, let’s count the number of trenary strings. First, there are ${ n \choose k}$ positions for the 1’s and 0’s, and then there are 2 choices for the value in each of these positions. The rest of the positions must be 2. Hence, there are $\sum_{ k \text{ even } } {n \choose k} 2^k $ of them.

Of these, pair them up according to those that differ only in the first non 2 digit. In this pair, clearly one of them has an even number of ones and an even number of 2's. Note that the only string not paired is the string of all 2's.

Hence, the total number of strings with an even number of 1 and even number of 0 is

$$.5 \times (-1+\sum_{ k even } {n \choose k} 2^k) +1 $$

This matches Pedro's answer.

$\endgroup$
  • $\begingroup$ So how does this account for cases 3 and 4, when we had odd 1s, even 0s, and even 1s, odd 0s? $\endgroup$ – compguy24 May 1 '14 at 4:00
  • $\begingroup$ @compguy24 sorry I misread the question initially and deleted it quickly. I've edited it now. $\endgroup$ – Calvin Lin May 1 '14 at 12:26
  • $\begingroup$ "Clearly, there are..." I don't see it immediately. $\endgroup$ – Pedro Tamaroff May 1 '14 at 18:30
  • $\begingroup$ @PedroTamaroff Added explanation of the rule of product. $\endgroup$ – Calvin Lin May 1 '14 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.