Multinomial coefficients (general inequality).

Question

Fix $s, n$ in $\mathbb{N}.$ Let $n_1,..., n_s$ in $\mathbb{N}$ such that $n_k\geq 1.$ Set $N= \sum_{k=1}^sn_k.$ I want to prove that
$$\sum_{m_1+...+m_s=n}\prod_{k=1}^s(m_k+n_k)!\leq (n+N)!.$$

The simple case where $s=2$ is equivalent to prove that $$\sum_{m=0}^n (m+n_1)!(n-m+n_2)! \leq (n+N)!.$$ This can be proven by induction on $n;$ \begin{eqnarray}\sum_{m=0}^{n+1} (m+n_1)!(n+1-m+n_2)! &\leq& (n+1+n_1)!n_2! +(n+N)\sum_{m=0}^n (m+n_1)!(n-m+n_2)! \\ &\leq& (n+N)! +(n+N)(n+N)! \\ &=& (n+1+N)! \end{eqnarray} Any hint for the general case $s\geq 2?!$

Answer 1

You can use induction on $s$: for any $m_s'\ge 0$, $$ \sum_{m_s+m_{s+1} = m_s'} (m_s + n_s)!(m_{s+1}+n_{s+1})! \le (m_s' + n_s')!, $$ where $n_s' = n_{s} + n_{s+1}$. Therefore, $$ \sum_{m_1+...+m_{s+1}=n}\prod_{k=1}^{s+1}(m_k+n_k)! \\= \sum_{m_1+...+m_{s-1}+m_s'=n}\left(\prod_{k=1}^{s-1}(m_k+n_k)!\right)\sum_{m_s+m_{s+1} = m_s'} (m_s + n_s)!(m_{s+1}+n_{s+1})! \\\le \sum_{m_1+...+m_{s-1}+m_s'=n}\left(\prod_{k=1}^{s-1}(m_k+n_k)!\right) (m_s'+n_s')! $$ etc.

Answer 2

For any $\ell$ define the formal power series $$F_\ell(x)=\ell!+(1+\ell)!x+(2+\ell)!x^2+(3+\ell)!x^3+\cdots.$$ In terms of this power series, the left and right sides of the inequality are $$ \sum_{m_1+\cdots+m_s=n}\prod_{k=1}^s (m_k+n_k)!=[x^n]F_{n_1}(x)\times\cdots\times F_{n_s}(x)$$ and $$(n+n_1+\cdots+n_s)!=[x^n]F_{n_1+\cdots+n_s}(x) .$$ In the $s=2$ case, the OP already did all the hard work to show $$ [x^n]F_{n_1}(x)\times F_{n_2}(x)\le[x^n]F_{n_1+n_2}(x).$$ The rest follows by combining partial sums with the next term, like this: \begin{eqnarray*} % \nonumber to remove numbering (before each equation) [x^n]F_{n_1}(x)\times\cdots\times F_{n_s}(x) &\le& [x^n]F_{n_1+n_2}(x)\times F_{n_3}(x)\times\cdots\times F_{n_s}(x) \\ &\le& [x^n]F_{n_1+n_2+n_3}(x)\times F_{n_4}(x)\times\cdots\times F_{n_s}(x) \\ &\vdots&\\ &\le& [x^n]F_{n_1+\cdots+n_s}(x) . \end{eqnarray*}