$2^n$ sequence, exactly k runs

Question

This is a question from Knuths "The art of programming"

Among all $2^n$ sequences $a_1 a_2 ... a_n$ where each $a_j$ is either 0 or 1, how many have exactly k runs (that is, k-1 occurences of $a_j$ < $a_{j+1})$.

It's even answered with $ \binom {n+1} {2k-1}$, because $\binom{n}{2k-2}$ end with 0 and $\binom{n}{2k-1}$ end with 1, but I don't underestand why this holds.

Answer 1

Using $z$ for zeros and $w$ for ones and $u$ for runs we get the generating function

$$(1+z+z^2+\cdots) \\ \times \sum_{q\ge 0} u^{q} (w+w^2+\cdots)^q (z+z^2+\cdots)^q \\ \times (1+w+w^2+\cdots)$$

which is

$$\frac{1}{1-z} \\ \times \sum_{q\ge 0} u^{q} \frac{w^q}{(1-w)^q} \frac{z^q}{(1-z)^q} \\ \times \frac{1}{1-w}$$

or

$$\frac{1}{1-z} \frac{1}{1-uwz/(1-z)/(1-w)} \frac{1}{1-w} \\ = \frac{1}{(1-z)(1-w)-uwz}.$$

As a sanity check we put $u=1$ and $w=z$ to obtain

$$\frac{1}{(1-z)^2 - z^2} = \frac{1}{1-2z}$$

and we see that we have accounted for all strings of length $n.$ We no longer need the distinction between zeros and ones here so we obtain

$$\frac{1}{(1-z)^2-uz^2} = \frac{1}{(1-z)^2}\frac{1}{1-uz^2/(1-z)^2}.$$

Extract the coefficient on $[u^k]$ to get

$$\frac{z^{2k}}{(1-z)^{2k+2}}.$$

Continue with the coefficient on $[z^n]$ to obtain

$$[z^n] \frac{z^{2k}}{(1-z)^{2k+2}} = [z^{n-2k}] \frac{1}{(1-z)^{2k+2}} \\ = {n-2k+2k+1\choose 2k+1} = {n+1\choose 2k+1}$$

as claimed.

Here is the Maple code for this to clarify what interpretation of the question is being used:

X :=
proc(n)
option remember;
    local pos, d, ind, k, res;

    res := 0;
    for ind from 2^n to 2^(n+1)-1 do
        d := convert(ind, base, 2);

        k := 0;
        for pos to n-1 do
            if d[pos] > d[pos+1] then
                k := k + 1;
            fi;
        od;

        res := res + v^k;
    od;

    res;
end;


F := n ->
add(binomial(n+1,2*k+1)*v^k, k=0..floor(n/2));

This will yield e.g. for $n=10$ the generating function

$${v}^{5}+55\,{v}^{4}+330\,{v}^{3}+462\,{v}^{2}+165\,v+11.$$

The GF points us to OEIS A034867 where it is listed as non-increasing runs, which is the same by symmetry as non-decreasing ones.

Remark. The above counts boundaries between adjacent runs. So if we have $k-1$ boundaries we get $k$ runs. On substituting $k-1$ into the closed form we find

$${n+1\choose 2(k-1)+1} = {n+1\choose 2k-1}$$

which agrees with the OP.

Answer 2

We can look at 4 cases:

Where the sequence starts with 0/1 and ends with 0/1
1) 0...0
2) 1...0
3) 0...1
4) 1...1

At 1) we need to jump k-1 times from 0 to 1 and jump k-1 times back from 1 to 0, therefore we get 2k-2 points where we jump and we can think of $\binom{n-1}{2k-2}$ ways to choose these points

2) jump k-1 times from 0 to 1 and k-2 times back, therefore $\binom{n-1}{2k-3}$ ways to choose these points

Therefore we get $\binom{n}{2k-2}$ sequences, which end with 0

3) jump k-1 times from 0 to 1 and k times back, therefore $\binom{n-1}{2k-1}$ ways to choose these points

4) jump k-1 times from 0 to 1 and k-1 times back, therefore $\binom{n-1}{2k-2}$ ways to choose these points

Therefore we get $\binom{n}{2k-1}$ sequences, which end with 1