sum with partial multinomial coefficients

300 Views Asked by At

I have been motivated by answer on this question: Special sum of multinomial coefficients!

$$ S=\sum_{\substack{a_1+a_2+\dots+a_k=2n\\ a_i\text{ even}}}\frac{(2n)!}{a_1!a_2!\dots a_k!}=\frac{1}{2^k}\sum_{j=0}^{k}\binom{k}{j}(k-2j)^{2n}. $$

I am wondering if it is possible to find an explicit formula for

$$ S=\sum_{\substack{a_1+a_2+\dots+a_k=2n\\ \text{only $m\leq k$-components of } a_i\text{odd}}}\frac{(2n)!}{a_1!a_2!\dots a_k!} $$

1

There are 1 best solutions below

4
On BEST ANSWER

Let's use $n$ instead of $2n$ for greater generality.

Next, let's restrict to the first $m$ of the $a_i$s being odd:

$$ \sum_{m~\mathrm{of}~a_i~\mathrm{odd}}\binom{n}{a_1,\cdots,a_k} = \binom{n}{m}\sum_{\substack{a_1,\cdots,a_m~\mathrm{odd} \\ a_{m+1},\cdots,a_k~\mathrm{even}}}\binom{n}{a_1,\cdots,a_k} $$

If $f(x)=\sum f_k x^k$ is a polynomial then we have (anti-)symmetrization operators

$$ \frac{f(x)+f(-x)}{2}=\sum_{k~\mathrm{even}} f_kx^k, \quad \frac{f(x)-f(-x)}{2}=\sum_{k~\mathrm{odd}} f_kx^k. $$

So, for instance, we could write

$$ \sum_{k~\mathrm{odd}}\binom{n}{k} = \left.\frac{(1+x)^n-(1-x)^n}{2}\right|_{x=1}=2^{n-1}. $$

For us, though, we need $k$ variables $x_1,\cdots,x_k$. Define operators $R_i$ by

$$ R_i f(x_1,\cdots,x_i,\cdots,x_k) = f(x_1,\cdots,-x_i,\cdots,x_n) $$

with (anti-)symmetrizations $\frac{1}{2}(\mathrm{Id}\pm R_i)$. Then

$$ \sum_{\substack{a_1,\cdots,a_m~\mathrm{odd} \\ a_{m+1},\cdots,a_k~\mathrm{even}}}\binom{n}{a_1,\cdots,a_k} =\left.\frac{1}{2^k} \prod_{i=1}^m (\mathrm{Id}-R_i)\prod_{j=m+1}^k (\mathrm{Id}+R_j) (x_1+\cdots+x_k)^n\right|_{x_1,\cdots,x_k=1} $$

Abbreviate any product of $t$ distinct $R_i$s as $R^t$ for simplicity, in which case

$$ \left. R^t(x_1+\cdots+x_k)^n\right|_{x_1,\cdots,x_k=1} = (k-2t)^n. $$

The product of operators becomes

$$ \prod_{i=1}^m (\mathrm{Id}-R_i)\prod_{j=m+1}^k (\mathrm{Id}+R_j) = \sum_{t=0}^m \binom{m}{t} (-R)^t \sum_{s=0}^{k-m} \binom{k-m}{s}R^s. $$

In conclusion,

$$ \sum_{m~\mathrm{of}~a_i~\mathrm{odd}}\binom{n}{a_1,\cdots,a_k} = \frac{1}{2^k}\binom{n}{m}\sum_{t=0}^m \sum_{s=0}^{k-m}\binom{m}{t}\binom{k-m}{s} (-1)^t (k-2t-2s)^n. $$