The number of transitions in a binary sequence is the number of times the sequence switches from $0$ to $1$ or vice versa. For example, the sequence $00000000$ has $0$ transitions and the sequence $00011100$ has $2$.
Define the set $T_{n,k}$ to be the set of integers in the range $[0,2^n-1]$ whose $n$-bit binary sequences have exactly $k$ transitions. For example, we can partition the integers 0 through 15 into these four sets:
- $T_{4,0} = \{0000,1111\} = \{0,15\}$
- $T_{4,1} = \{0001,0011,0111,1000,1100,1110\} = \{1,3,7,8,12,14\}$
- $T_{4,2} = \{0010,0100,0110,1001,1011,1101\} = \{2,4,6,9,11,13\}$
- $T_{4,3} = \{0101,1010\} = \{5,10\}$
I'm interested in sums of powers of these sets: Let
$$S_{n,k,p}=\sum_{m\in T_{n,k}}m^p.$$
Here are a few special cases:
$$S_{n,k,0}=2\binom{n-1}{k}$$
$$S_{n,k,1}=(2^n-1)\binom{n-1}{k}$$
$$S_{n,0,p}=(2^n-1)^p \quad \text{if} \ p>0$$
$$S_{n,1,2}=4^n\left(n-\frac{7}{3}\right)+2^{n+1}+\frac{1}{3}$$
Could there be a closed-form expression for $S_{n,k,p}$? I'd also be happy with an algorithm to compute it which is better than exponential in $n$.
(My motivation is that I write mathematical software which I test by generating random inputs. It's particularly useful to generate integers whose binary representations have few transitions, as these integers are likely to trigger edge cases in my code. Solving the problem I have posed here would help me analyze the distribution of such integers. More information here.)