# Sum of the first k multi-nomial coefficients for fixed n

Multinomial coefficients are defined as $$\binom{n}{k_1,k_2,\cdots,k_m}$$ where $n=k_1+k_2+\cdots+k_m$

Is there closed form solution available for the sum of the first $t$ multinoial coefficients? Order of the coefficients is determined by the lexicographic arrangement of $k_1,k_2,\cdots,k_m$.

I am not sure how to write a correct mathematical notation for it.

$$\sum_{k_1+k_2+\cdots+k_m=n,~(k_1,k_2,\cdots,k_m)<^\mathrm{d} t} \binom{n}{k_1,k_2,\cdots,k_m}$$

where $(k_1,k_2,\cdots,k_m)<^\mathrm{d} t$ mean all orderings of $(k_1,k_2,\cdots,k_m)$ whose dictionary order is less than $t$.

## 2 Answers

Recall the multinomial theorem which states

$$(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1+k_2+\cdots+k_m=n} {n \choose k_1, k_2, \dots, k_m} \prod_{1\le t\le m}x_{t}^{k_{t}}$$

Evaluating the left hand side at $(1,1,\dots, 1)$ is, I think, what you are asking and this gives the value $m^n$

Now that I see you want the first $\vec{k}$ (where I assume you have a well order determined by lexicographic ordering) then notationally perhaps you would like to write

$$\sum_{\substack{\vec{1}\leq \vec{w}\leq \vec{k},\\ \sum w_i = 1}}{n \choose k_1, k_2, \dots, k_m}$$ where $\vec{1} = \underbrace{(1,1,\dots, 1)}_{m\text{ times}}.$ Furthermore, you may also want to specify that all the vectors $\vec{z} = (z_1,z_2, \dots, z_m) \in \mathbb{N}^m$ and things like that.

• No, it would give $m^n$. But that is sum of all the terms, not the partial sum I am looking for. Dec 7, 2015 at 11:04
• Thanks for pointing that out, I have included a proposed notation for what you actually asked for. Dec 7, 2015 at 11:23
• Thanks. Should I take a symbol with overhead arrow as lexicographic order? Concise but new to me. Dec 7, 2015 at 11:27
• No, I was using that overhead arrow to denote the fact that our elements of summation are vectors. You may also want to clearly state that they are non-negative integer-vectors regardless of the fact that this type of combinatorics is clearly discrete. Dec 7, 2015 at 11:30
• I have addressed some of these facts in a further edit to my answer. Dec 7, 2015 at 11:34

Not even the partial sums $$\sum_{0 \le k \le m} \binom{n}{k}$$ for $$m < n$$ have a nice closed expression, so I think the chance of the formula you want is very slim.