From the multinomial formula we have

$$(x_1 + x_2 + \dotsb + x_m)^n = \sum_{k_1+k_2+\dotsb+k_m=n, \ k_1, k_2, \dotsc, k_m \geq 0} {n \choose k_1, k_2, \dotsc, k_m} \prod_{t=1}^m x_t^{k_t}\,.$$

I wish to evaluate the RHS, but with the additional constraint that each exponent $k_i$ can not exceed some positive integer $a<n$. That is, $$ \sum_{k_1+k_2+\dotsb+k_m=n, \ 0\leq k_1, k_2, \dotsc, k_m \leq a} {n \choose k_1, k_2, \dotsc, k_m} \prod_{t=1}^m x_t^{k_t}\,. $$ While I can obviously calculate this, my question is whether there is a simple way to express the polynomial with the restriction on the exponents. This is to ultimately facilitate computation. For example, in the case where $a=n-1$ we could write this as $$ \left(\sum_{i=1}^m x_i\right)^n - \sum_{i=1}^m x_i^n. $$ Is there a simple way of expressing the polynomial for other integer values $0< a<n$?

  • 1
    $\begingroup$ Even for the binomial case, you can't really simplify $\sum_{n-a\leq k \leq a} \binom{n}{k} x^k$ in any meaningful way. $\endgroup$ Commented Mar 15, 2022 at 22:14

1 Answer 1


The idea of subtracting large powers from the multinomial can be extended with the inclusion-exclusion principle:

$$ \sum_{k_1+k_2+\dotsb+k_m=n,\atop 0\leq k_1, k_2, \dotsc, k_m \leq a} {n \choose k_1, k_2, \dotsc, k_m} \prod_{t=1}^m x_t^{k_t} = n! \sum_{S\subseteq [k]} (-1)^{|S|} \sum_{t_s\geq a+1, s\in S\atop \sum_{s\in S} t_s\leq n} \frac{\big(\sum_{i=1\atop i\not\in S}^m x_i\big)^{n-\sum_{s\in S} t_s}}{(n-\sum_{s\in S}t_s)!} \prod_{s\in S} \frac{x_s^{t_s}}{t_s!}. $$

If we introduce a truncated exponential series $\exp_l(x) := \sum_{t\geq l} \frac{x^t}{t!}$. Then the above formula can be seen as $$[z^n]\ n!\sum_{S\subseteq [k]} (-1)^{|S|}\exp\big(z\sum_{i=1\atop i\not\in S}^m x_i\big) \prod_{s\in S} \exp_{a+1}(x_sz).$$

I'm not sure how helpful it is.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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