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

Question

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$.

Answer 1

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.

Answer 2

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.