5
$\begingroup$

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

  • 0
    You defined $a$ and $x$, but what's $f$?2011-10-01
  • 0
    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?2011-10-01
  • 0
    oops I meant x when I wrote f. edited.2011-10-01
  • 0
    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.2011-10-01
  • 0
    @Dum: Oh, you should probably change "where" to "for all $02011-10-01
  • 0
    The number of such sequences is simply $3^n$. Would you like me to explain how in an answer?2011-10-01
  • 0
    I am presumably misreading, but it looks like $x_{n+1}=3x_n$, which should not give much difficulty.2011-10-01
  • 0
    I edited it, hopefully it will be clear now.2011-10-01
  • 0
    @Dum: Wait, so it's *not* "for all $k$," it's "for *some* integer $k$," right?2011-10-01
  • 0
    @anon yes it is.2011-10-01
  • 0
    Unfortunately, your recurrence counts sequences like $011001111$ (in which the condition is satisfied for $k=1$ and $k=3$) multiple times.2011-10-01

2 Answers 2

3

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.

  • 0
    That makes sense, thank you!2011-10-01
0

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.

  • 0
    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?2011-10-01
  • 0
    @joriki: I assumed that the recurrence was correct; apparently it isn't.2011-10-01
  • 0
    That's right, it isn't.2011-10-01