$2^n$ sequence, exactly k runs 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.  
 A: 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 
A: 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.
