Combinatorics - finding coefficients when summing over permutations of permutations I have $N$ 2-tuples. Each tuple* can either be up, in which case it has components $(a,b)$, or it can be down, in which case it has components $(c,d)$.
Given that exactly $N_\mathrm{up}$ of these tuples must be up, there are $N\choose N_\mathrm{up}$ ways to choose which ones.
For each of these ways, I would like to take the first component ($a$ or $c$) from $N_\mathrm{up}$ of the tuples, and the second component ($b$ or $d$) from the rest, and multiply them together forming a product $a^ib^jc^kd^l$, where $i+j+k+l=N$. There are similarly $N\choose N_\mathrm{up}$ ways to chose which tuples to take which component from.
I would like to get these products for all possible choices of which tuples are up or down, and all possible choices of which tuples to take the first component from, and add them up. This should give me a sum with ${N\choose N_\mathrm{up}}^2$ terms. However many of the terms will have the same powers of $a$, $b$, $c$, and $d$, and so I should be able to write the sum as:
$S(N,N_\mathrm{up}) = \sum\limits_{i+j+k+l=N}C_{ijkl}a^ib^jc^kd^l.$
My question is: For a given $N$ and $N_\mathrm{up}$, what are the coefficients $C_{ijkl}$? Any other expressions for the above sum would also be useful, even if it's not in this form.
I can of course calculate them as I need them with a short piece of code to loop over all the possibilities, but if there is a nice expression in terms of binomial coefficients or the like, that would be preferable as I can write it in a paper and propagate it through subsequent calculations.
* The tuples represent spin $\frac12$ systems in a quantum mechanics calculation I'm working on, hence the descriptions up and down. The spins are up and down in a different basis than I'm writing them in though, so their components are not just ones and zeros.
Example: Let's say $N=3$ and $N_\mathrm{up}=2$. Then we have the following 3 possible ways of arranging our tuples:
$\quad |\mathrm{up}\rangle,|\mathrm{up}\rangle,|\mathrm{down}\rangle\quad |\mathrm{up}\rangle,|\mathrm{down}\rangle,|\mathrm{up}\rangle\quad
|\mathrm{down}\rangle,|\mathrm{up}\rangle,|\mathrm{up}\rangle$
$=(a,b),(a,b),(c,d)\quad 
(a,b),(c,d),(a,b)\quad 
(c,d),(a,b),(a,b)\quad.$
For each of these are three ways to choose which $N_\mathrm{up}=2$ tuples we should take the first component from, taking the second component from the remaining tuple. I've written them all out below, with the component chosen from each tuple in bold:
$(\boldsymbol{a},b),(\boldsymbol{a},b),(c,\boldsymbol{d})\quad 
(\boldsymbol{a},b),(\boldsymbol{c},d),(a,\boldsymbol{b})\quad 
(\boldsymbol{c},d),(\boldsymbol{a},b),(a,\boldsymbol{b})\rightarrow aad + acb + cab$
$(\boldsymbol{a},b),(a,\boldsymbol{b}),(\boldsymbol{c},d)\quad 
(\boldsymbol{a},b),(c,\boldsymbol{d}),(\boldsymbol{a},b)\quad 
(\boldsymbol{c},d),(a,\boldsymbol{b}),(\boldsymbol{a},b)\rightarrow abc + ada + cba$
$(a,\boldsymbol{b}),(\boldsymbol{a},b),(\boldsymbol{c},d)\quad 
(a,\boldsymbol{b}),(\boldsymbol{c},d),(\boldsymbol{a},b)\quad 
(c,\boldsymbol{d}),(\boldsymbol{a},b),(\boldsymbol{a},b)\rightarrow bac + bca + daa$
So the total sum $S(N=3,N_\mathrm{up}=2)$ is:
$S(N=3,N_\mathrm{up}=2) = aad + acb + cab + abc + ada + cba + bac + bca + daa$
$\qquad\qquad\qquad\qquad = 6abc + 3a^2d.$
So for $N=3$ and $N_\mathrm{up}=2$, the only nonzero $C_{ijkl}$ are:
$C_{1110}=6$
and
$C_{2001}=3.$
I've been beating my head against this for a short while but haven't come up with anything. It seems so simple but my brain hasn't been cooperative so far. Any help would be appreciated!
I'm pretty sure Majorana worked this out in 1932, but I'm unable to extract the details from his paper, where things are pretty condensed, and perhaps this result is so trivial that everyone is happy to take it as a given!
 A: Consider just one fixed patterns of length $N$ consisting of $N_{up}$ components that are $up$ and $N_{down}$ components that are $down$. Then let us see what this pattern contributes to the sum. We have $N_{up}+N_{down}=N$ and we want to choose $i,j,k,l$ such that
$$
\begin{align}
&i+j+k+l&&=&&N\\
&i+j&&=&&N_{up}\\
&k+l&&=&&N_{down}\\
&i,j&&\leq &&N_{up}\\
&k,l&&\leq &&N_{down}
\end{align}
$$
Combining the above information we see that $j,k\leq N_{\min}=\min(N_{up},N_{down})$. So if we first choose $j,k\leq N_{\min}$ then $i,l$ are determined by the equations $i=N_{up}-j$ and $l=N_{down}-k$. Once $i,j,k,l$ are given then we can calculate the number $D_{(i,j,k,l)}$ of contributions of the product $a^i b^j c^k d^l$ from this given fixed pattern to the sum as
$$
D_{(i,j,k,l)}=D_{(j,k)}=\binom{N_{up}}{j}\binom{N_{down}}{k}
$$
Note that this did not in any way depend on the pattern we fixed but only on $N_{up}$ (and $N_{down}$) so since there are $\binom{N}{N_{up}}$ such patterns we get
$$
C_{(i,j,k,l)}=C_{(j,k)}=\binom{N}{N_{up}}D_{(j,k)}=\binom{N}{N_{up}}\binom{N_{up}}{j}\binom{N_{down}}{k}
$$
But in fact I prefer the coefficients $D_{(j,k)}$. So with this we can write the sum explicitly:
$$
\begin{align}
S(N,N_{up})&=\binom{N}{N_{up}}\cdot\sum_{j,k=0}^{N_{\min}}D_{(j,k)}a^{N_{up}-j}b^j c^k d^{N_{down}-k}\\
&=\binom{N}{N_{up}}\cdot\sum_{j,k=0}^{N_{\min}}\binom{N_{up}}{j}\binom{N_{down}}{k}a^{N_{up}-j}b^j c^k d^{N_{down}-k}
\end{align}
$$
In your example we have $N=3$, $N_{up}=2$ so $N_{down}=N_{\min}=1$. Therefore we get $j,k\leq 1$ and can calculate
$$
\begin{align}
C_{(2,0,0,1)}&=C_{(0,0)}=\binom{3}{2}\binom{2}{0}\binom{1}{0}=3\\
C_{(1,1,0,1)}&=C_{(1,0)}=\binom{3}{2}\binom{2}{1}\binom{1}{0}=6\\
C_{(1,1,1,0)}&=C_{(1,1)}=\binom{3}{2}\binom{2}{1}\binom{1}{1}=6
\end{align}
$$
where you forgot the possibility $(j,k)=(1,0)$ or more detailed $(i,j,k,l)=(1,1,0,1)$ corresponding to terms of the form $abd$ in your example. The entire sum will be
$$
\begin{align}
S(3,2)&=\binom{3}{2}\cdot\sum_{j,k=0}^{1}\binom{2}{j}\binom{1}{k}a^{2-j}b^j c^k d^{1-k}\\
&=3\cdot(a^2 b^0 c^0 d^1+2 a^1 b^1 c^0 d^1+2 a^1 b^1 c^1 d^0)\\
&=3a^2 d+6abd+6abc
\end{align}
$$
in the current example. I hope this was clear enough...
