Computing an arbitrary number of sums of sums

Question

I want to determine a closed-form expression for the sum $$f(n,m) = \sum_{k_1=1}^n \sum_{k_2=1}^{n-k_1}\dots \sum_{k_m=1}^{n-\sum_{i=1}^{m-1} k_i}1$$ for arbitrary $n$ and $m$. I know that the solution will be a polynomial, so a closed-form solution exists. I have reformulated the problem as the recursion problem $$f(n,m) = \sum_{k=1}^n f(n-k, m-1),$$ $$f(n, 1) = n.$$ However, here I got stuck. Does anyone have helpful ideas for me?

Answer 1

Fix $n$ and $m$. For any choice of $k_1, ..., k_m$, let $k_{m+1} = n - \sum_{i=1}^mk_m$. Then the expression you have translates to the number of solutions to the following system of equations: $k_1, \ldots, k_m \geq 1$, $k_{m+1} \geq 0$, and $\sum_{i=1}^{m+1} k_i = n$.

This can be solved by the "stars and bars" counting formula: Letting $k'_i = k_i - 1$ for $i = 1, \ldots, m$ annd $k'_{m+1} = k'_m$, we have $\sum_{i=1}^{m+1}k'_i = n-m$ and $k'_i \geq 0$, the number of solutions to which is $\binom{n-m + (m+1) - 1}{(m+1) - 1)} = \binom{n}{m}$.