2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

We will establish the identity by counting the elements of the same set two different ways.

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 $i$th stretch) corresponds to $\prod_{i=0}^{k} {n_i \choose m_i}$ terms in the full expansion, where the $i$th 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 $i$th 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]$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.