The number of binary sequences generated by a parity map from all integer partitions of $n$ and their permutations

Question

Let $n$ be an integer and $n=(n_1,\dots,n_n)$ all its partitions. The partitions with less than $n$ integers (all but one) are padded by zeros from the left AND sorted such that first come even integers (I count zero as even) followed by odd integers. An example for $n=9$ is $$ ((1,1,1,1,1,1,1,1,1),(0,2,1,1,1,1,1,1,1),(0,0,2,2,1,1,1,1,1),(0,0,0,2,2,2,1,1,1),\\(0,0,0,0,2,2,2,2,1),(0,0,1,1,1,1,1,1,3),(0,0,0,2,1,1,1,1,3),(0,0,0,0,2,2,1,1,3),\\(0,0,0,0,0,2,2,2,3),(0,0,0,0,1,1,1,3,3),(0,0,0,0,0,2,1,3,3),(0,0,0,0,0,0,3,3,3),\\(0,0,0,4,1,1,1,1,1),(0,0,0,0,2,4,1,1,1),(0,0,0,0,0,2,2,4,1),(0,0,0,0,0,4,1,1,3),\\(0,0,0,0,0,0,2,4,3),(0,0,0,0,0,0,4,4,1),(0,0,0,0,1,1,1,1,5),(0,0,0,0,0,2,1,1,5),\\(0,0,0,0,0,0,2,2,5),(0,0,0,0,0,0,1,3,5),(0,0,0,0,0,0,0,4,5),(0,0,0,0,0,6,1,1,1),\\(0,0,0,0,0,0,2,6,1),(0,0,0,0,0,0,0,6,3),(0,0,0,0,0,0,1,1,7),(0,0,0,0,0,0,0,2,7),\\(0,0,0,0,0,0,0,8,1),(0,0,0,0,0,0,0,0,9)). $$ Now I apply the following entry-wise parity map $P(n_{even})\to0, P(n_{odd})\to1$ resulting in $$ ((1,1,1,1,1,1,1,1,1),(0,0,1,1,1,1,1,1,1),(0,0,0,0,1,1,1,1,1),(0,0,0,0,0,0,1,1,1),\\(0,0,0,0,0,0,0,0,1),(0,0,1,1,1,1,1,1,1),(0,0,0,0,1,1,1,1,1),(0,0,0,0,0,0,1,1,1),\\(0,0,0,0,0,0,0,0,1),(0,0,0,0,1,1,1,1,1),(0,0,0,0,0,0,1,1,1),(0,0,0,0,0,0,1,1,1),\\(0,0,0,0,1,1,1,1,1),(0,0,0,0,0,0,1,1,1),(0,0,0,0,0,0,0,0,1),(0,0,0,0,0,0,1,1,1),\\(0,0,0,0,0,0,0,0,1),(0,0,0,0,0,0,0,0,1),(0,0,0,0,1,1,1,1,1),(0,0,0,0,0,0,1,1,1),\\(0,0,0,0,0,0,0,0,1),(0,0,0,0,0,0,1,1,1),(0,0,0,0,0,0,0,0,1),(0,0,0,0,0,0,1,1,1),\\(0,0,0,0,0,0,0,0,1),(0,0,0,0,0,0,0,0,1),(0,0,0,0,0,0,1,1,1),(0,0,0,0,0,0,0,0,1),\\(0,0,0,0,0,0,0,0,1),(0,0,0,0,0,0,0,0,1)). $$ The number of different binary strings gets reduced, for the example above it is $$ (1, 1, 1, 1, 1, 1, 1, 1, 1) \to 1,\\ (0, 0, 1, 1, 1, 1, 1, 1, 1) \to 2,\\ (0, 0, 0, 0, 1, 1, 1, 1, 1) \to 5,\\ (0, 0, 0, 0, 0, 0, 1, 1, 1) \to 10,\\ (0, 0, 0, 0, 0, 0, 0, 0, 1) \to 12. $$

QUESTION: Suppose I take all permutations of each integer sequence such that it leads to the same binary string under $P$. Their number is a product of two multinomial coefficients, one for the odd part, the other one for the even part. How many of such bit strings are there? Let's illustrate some interesting numerology on the above example and take $(0, 0, 1, 1, 1, 1, 1, 1, 1)$. It comes from two partitions: $(0,2,1,1,1,1,1,1,1)$ and $(0,0,1,1,1,1,1,1,3)$. There are two ($=2\times1$) and seven ($=1\times 7$) permutations both leading to $(0, 0, 1, 1, 1, 1, 1, 1, 1)$ under $P$. In fact, doing this for all five binary strings I numerically found that the number is a binomial coefficient $$ \binom{n+k-1}{k}=[1,9,45,165,495], $$ for $k=0,\dots,4$ (counting from top to bottom).

QUESTION AGAIN: How to prove the appearance of the binomial coefficient?

Answer 1

You are counting all the compositions of $n$ into $m$ non-negative even parts and $n-m$ odd parts where the even parts come before the odd parts. You need $n$ and $n-m$ to have the same parity so $m=2k$ for some $k$.

The even parts add up to an even number, say $2s$, so the odd parts add to $n-2s$. Clearly $s$ is non-negative and $n-2s \ge n-2k$ so $0 \le s \le k \le \frac{n}{2}$.

Given $s$,

• the number of $2k$ even non-negative compositions of $2s$ is the number of $2k$ non-negative compositions of $s$ (dividing each part by $2$), which is ${s+2k-1 \choose s}$
• the number of $n-2k$ odd compositions of $n-2s$ is the number of $n-2k$ non-negative even compositions of $2k-2s$ (subtracting $1$ from each part), which is the number of $n-2k$ non-negative compositions of $k-s$ (dividing each part by $2$), i.e. ${n-s-k-1 \choose k-s}$

So summing over $s$ gives the number of compositions of $n$ into $2k$ non-negative even parts and $n-2k$ odd parts where the even parts come before the odd parts is $$\sum\limits_{s=0}^k {s+2k-1 \choose s}{n-s-k-1 \choose k-s} ={n+k-1 \choose k}$$ since in general $\sum\limits_{d=0}^c {a+d \choose d}{b-d \choose c-d} ={a+b+1 \choose c}$