# Identity for a product of choose functions

Given non-negative integers $k$, $m$, $n$, where $n$ $\geq$ $m$ and $n$ $\equiv$ $m$ (mod $2$), can you show that:

$${n + k \choose m} {\frac{n - m}{2} + k \choose k} = \sum_{∀i, m_i \equiv n_i (mod 2)} \left[\prod_{i=0}^{k} {n_i \choose m_i}\right]$$

where $\sum_{i=0}^{k} m_i$ = $m$, $\sum_{i=0}^{k} n_i$ = $n$, and $m_i$, $n_i$ $\geq$ $0$ and $m_i$ $\leq$ $n_i$, $i$ = $0$, $k$.

The following is context on how I arrived to post this question. I posted this question after empirically verifying (up to D = 20) an answer essentially in the form of the left hand side of the equation above. Just recently, I set about to logically prove this result. I doing so, I wound up with an expression in the form of the right hand side of the equation. Thus, the above identity lies at the heart of the $CQHRL_D$ face counting question.

As to my progress on deriving this identity, I put myself at the starting line alongside others who are much more knowledgeable and capable; however I can count interest in the problem in my favor.

Begin by considering the trinomial coefficient for ($m$, $n$ - $m$, $k$); i.e., the coefficient of the $a$m$b$n-m$c$k term in the expansion of ($a$ + $b$ + $c$)n+k. This coefficient can be calculated by counting the number of corresponding terms in the full expansion of ($a$ + $b$ + $c$)n+k. The number of combinations of positions for the $m$ $a$ factors is ${n+k \choose m}$. For each of these, there are ${n-m+k \choose k}$ ways to arrange the $b$ and $c$ factors, for a total of ${n+k \choose m}$${n-m+k \choose k}. Also, note that in each of these terms, there are k+1 stretches of only a & b factors (possibly including the empty set); i.e., before the first c factor, between each pair of subsequent c factors, and after the last c factor. Each combination of (positioning of the k c factors, partition of the m a factors into m_i a factors in the ith stretch) corresponds to \prod_{i=0}^{k} {n_i \choose m_i} terms in the full expansion, where the ith stretch of only a & b factors has m_i a's and (n_i -m_i) b's; hence \sum_{i=0}^{k} m_i = m and \sum_{i=0}^{k} n_i = n. (Note that n_i - the length of the ith only a & b stretch - is determined by the positioning of the c's.) The total coefficient is obtained by summing the contributions over all such combinations of positionings of the k c factors and partitions of the m a factors, or \sum \left[\prod_{i=0}^{k} {n_i \choose m_i}\right]; where \sum_{i=0}^{k} m_i = m and \sum_{i=0}^{k} n_i = n. Now, we wish to count the elements of a subset of the terms described above - only those terms where there are an even number of b factors before the first c factor, between each pair of subsequent c factors, and after the last c factor. (As we are given that n \equiv m (mod 2), n-m is even, so we know this is possible.) Again, the number of combinations of positions for the m a factors is {n+k \choose m}. For the remaining factors, consider bb as a unit, as we know b's must occur in pairs among the c's. So the number of eligible arrangements of b's and c's is {\frac{n - m}{2} + k \choose k}, for a total count of {n+k \choose m}$${\frac{n - m}{2} + k \choose k}$.
Counting the other way, each eligible combination of (positioning of the $k$ $c$ factors, partition of the $m$ $a$ factors into $m_i$ $a$ factors in the $i$th stretch) again corresponds to $\prod_{i=0}^{k} {n_i \choose m_i}$ terms. To be eligible, ($n_i$ - $m_i$) must be even ∀$i$, which is equivalent to saying $n_i$ $\equiv$ $m_i$ (mod $2$) ∀$i$. So, the count is $$\sum_{∀i, m_i \equiv n_i (mod 2)} \left[\prod_{i=0}^{k} {n_i \choose m_i}\right]$$
A similar argument shows that given non-negative integers $k$, $m$, $n$, and $q$ where $n$ $\geq$ $m$, $q$ > $0$, and $n$ $\equiv$ $m$ (mod $q$),
$${n + k \choose m} {\frac{n - m}{q} + k \choose k} = \sum_{∀i, m_i \equiv n_i (mod q)} \left[\prod_{i=0}^{k} {n_i \choose m_i}\right]$$