Number of integral solutions of $x_1+x_2+\cdots+x_k=n$ with conditions $1\leq x_1<\cdots<x_k\leq m$ for some integers $m,n,k$

Question

I have known that the number of positive integral solutions of $$x_1+\cdots+x_k = n$$ is $\binom{n-1}{k-1}$. Do we have any formula to count the number of solutions of the equation $$x_1+\cdots+x_k = n$$ with conditions $1\leq x_1<\cdots<x_k\leq m$ for some integers $m,n,k$?

Answer 1

Using generating functions the problem becomes slightly clearer.

If we remember that the generating function for partitions of $n$ into distinct parts $p_d(n)$ with part sizes $j=1$ and $j=m$ is:

$$\prod_{j=1}^{m}(1+q^j)=\sum_{n}p_d(n)q^n\tag{1}$$

since the coefficient of $q^n$ gets a contribution of $1$ for each possible distinct partition of $n$.

Then all we need to do is use some enumerator ($x$ say) to count the number of parts. This enumerator must simply tag each part enumerator $q^j$ in our product. Hence our required generating function for partitions of $n$ into $k$ distinct parts $p_d(n,k)$ with part sizes between $1$ and $m$ is a modified version of $(1)$:

$$\prod_{j=1}^{m}(1+xq^j)=\sum_{n,k}p_d(n,k)x^kq^n\tag{2}$$

It is also possible to express the product in terms of Gaussian binomial coefficients as:

$$\prod_{j=1}^{m}(1+xq^j)=\sum_{n,k}p_d(n,k)x^kq^n=\sum_{k}{m\choose k }_qq^{\binom{k+1}{2}}x^k\tag{3}$$

so that you would be looking for the $q^n$ coefficient of ${m\choose k}_qq^{\binom{k+1}{2}}$.

Answer 2

[Too long to comment] Not a simple one, as far as I know. You can start by noting that we must have each $x_i \geq i$, so (setting $y_i = x_i -i$) the problem is equivalent to counting solutions for $\sum y_i = n - \binom{k+1}2$ for $0 \leq y_1 \leq y_2 \leq \dots \leq y_k \leq m-k$. That problem without the $\leq m-k$ restriction is discussed at Number of integer solutions if $x_1\leq x_2\leq x_3\leq \cdots\leq x_r\leq k$, and there's a recursion you can use. To deal with the $\leq m-k$ restriction, subtract off the cases where $y_k > m-k$; you can do this by another recursion.