Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a finite sequence of zeros and ones of length $3n$, with $n$ an integer. We write an element of this sequence as $a_i$. How many sequences are there such that there exists an integer $k$, $0<k\le n$, such that $\sum^{3k}_{j=1}a_j=2k$? Here is what I have as of now: let $x_n$ be this number. We notice that $x_1=\binom{3}{2}=3$, and $x_n=\binom{3n}{2n}-\binom{3}{2}x_{n-1}+2^{3}x_{n-1}=\binom{3n}{2n}+5x_{n-1}$. How would I find a sum form solution to this? Also, does this seem correct? I got this because $\binom{3n}{2n}$ counts the total number of sequences satisfying the condition for $k=n$, $\binom{3}{2}x_{n-1}$ is the number of sequences satisfying it for both $k=n$ and $k=n-1$, and the number of sequences satisfying $k=n-1$ should be $x_{n-1}$, and we can choose the last three elements at random, so we multiply by $2^3$.

share|improve this question
    
You defined $a$ and $x$, but what's $f$? –  J. M. Oct 1 '11 at 1:46
    
The condition just says there are $2k$ ones in the first $3k$ terms, and the other $n-3k$ terms can each be $0$ or $1$ independently with no restrictions, which would mean the answer is simply $\tbinom{3k}{2k}2^{n-3k}$ sequences, no? –  anon Oct 1 '11 at 1:52
    
oops I meant x when I wrote f. edited. –  DumbQuestion Oct 1 '11 at 1:56
    
anon, that is the solution for some fixed k, but I want to find it over all $k\le n$, so I have to make sure I am not double counting. –  DumbQuestion Oct 1 '11 at 1:58
    
@Dum: Oh, you should probably change "where" to "for all $0<k\le n$" in the question then. –  anon Oct 1 '11 at 2:02

2 Answers 2

up vote 3 down vote accepted

The recurrence relation you derived isn't right. I'm not sure I understand your explanation of the derivation, but it seems you may have confused the number of sequences of length $3(n-1)$ fulfilling the condition for any $k$ with the number of sequences of length $3(n-1)$ fulfilling the condition for $k=n-1$.

Let's call a sequence of length $3k$ that has $2k$ ones "$k$-balanced", and a sequence that is $k$-balanced but not $j$-balanced for any $j\lt k$ "$k$-exclusive". To get the correct result, consider the number $a_n$ of $n$-exclusive sequences. We can count this as the number $\binom{3n}{2n}$ of $n$-balanced sequences minus the number of all $n$-balanced extensions of $k$-exclusive sequences for $0\lt k\lt n$. For each $k$, there are $a_k$ $k$-exclusive sequences to be extended, and the remaining $3(n-k)$ values must contain exactly $2(n-k)$ ones for the sequence to be $n$-balanced. Thus

$$a_n=\binom{3n}{2n}-\sum_{k=1}^{n-1}\binom{3(n-k)}{2(n-k)}a_k\;.$$

The left-hand side is the missing $n$-th term of the sum, so this becomes

$$\sum_{k=1}^n\binom{3(n-k)}{2(n-k)}a_k=\binom{3n}{2n}\;.$$

Now

$$\sum_{k=1}^n\binom{3(n-k)}{2(n-k)}\binom{3k}{2k}\frac2{3k-1}=\binom{3n}{2n}\;,$$

so

$$a_k=\binom{3k}{2k}\frac2{3k-1}\;.$$

For more on this, see What's the probability that a sequence of coin flips never has twice as many heads as tails? and Combinatorial proof of $\binom{3n}{n} \frac{2}{3n-1}$ as the answer to a coin-flipping problem.

The desired number $x_n$ is the number of all extensions of $k$-exclusive sequences to length $3n$, of which there are $2^{3(n-k)}$. Thus

$$x_n=\sum_{k=1}^na_k2^{3(n-k)}=\sum_{k=1}^n\binom{3k}{2k}\frac{2^{3(n-k)+1}}{3k-1}\;.$$

Wolfram|Alpha gives a "closed form" for this similar to the one in David's answer.

share|improve this answer
    
That makes sense, thank you! –  DumbQuestion Oct 1 '11 at 14:11

If $x_n$ was $\binom{3n}{2n}+5x_{n-1}$, which it isn’t, we would have

$$ x_n=\sum_{k=1}^{n} 5^{(n-k)} \binom{3k}{2k} $$ Mathematica gives the following “closed form”:

$$ x_n=-\frac{1}{5} \binom{3 n+3}{2 n+2} \, _3F_2\left(1,n+\frac{4}{3},n+\frac{5}{3};n+\frac{3}{2},n+2;\frac{27}{20}\right) -\alpha \;5^n $$ where $ \alpha=1+2 i \sqrt{\frac{5}{7}} \cos \left(\frac{1}{6} \cos ^{-1}\left(-\frac{17}{10}\right)\right) $ is a (complex) root of $7 z^3-21 z^2+36 z-27$, and $_3F_2$ is a generalized hypergeometric function.

share|improve this answer
    
If I understand the question correctly, this is wrong. It gives $x_3=234$, whereas $x_3$ should be $261$. Can you explain how you came up with this? –  joriki Oct 1 '11 at 10:44
    
@joriki: I assumed that the recurrence was correct; apparently it isn't. –  David Bevan Oct 1 '11 at 11:01
    
That's right, it isn't. –  joriki Oct 1 '11 at 11:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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