Number of unique permutations on an alternating bitstring? Given an alternating bitstring of length k, how many unique permutations can be made from it?
To illustrate, I'll show some examples:
$$1 \rightarrow 1$$
$$10 \rightarrow 10,01$$
$$101 \rightarrow 101,011,110$$
$$1010 \rightarrow 1100,1001,1010,0110,0101,0011$$
So the answer to k=1 is 1, k=2 is 2, k=3 is 3, and k=4 is 6, but I need the general case. I assume it will involve a summation and rather k is even or odd, but I can't seem to find the right formula.
 A: Let $a$ be the # of $0$'s and $b$ be the # of $1$'s.  Then the formula is $\binom{a + b}{a}$.
As for where this comes from do you know any group theory?  You have a transitive action of the symmetric group, $S_{a + b}$, on $a + b$ letters on this space.  The stabilizer of your string is $S_a \times S_b$ (permuting only the $0$'s amongst themselves and only the $1$'s amongst themselves), so you then apply the orbit stabilizer relation.
A: If $k=2n$, there are $\binom{2n}n$ permutations: a permutation is completely determined by the location of the $n$ $0$’s. If $k=2n+1$, there are $\binom{2n+1}n$ permutations: a permutation is completely determined by the location of the $n$ $0$’s. 
Added: I wrote the brief explanations on the assumption that your alternating string always starts with $1$, but it makes no difference to the final result. If the length is even, say $2n$, you’ll have $n$ of each symbol, so there will be $\binom{2n}n$ possible permutations. If the length is odd, say $2n+1$, you’ll have $n$ of one symbol and $n+1$ of the other, so there will be $\binom{2n+1}n=\binom{2n+1}{n+1}$ permutations.
