Weak $k$-compositions with each part less than $j$

Question

I am trying to figure out a problem from Richard Stanley's $\textit{Enumerative Combinatorics}$, which has to do with weak compositions of $n$ (sequence of nonnegative integers whose sum adds up to $n$). The problem is as follows:

Let $\kappa(n,j,k)$ be the number of weak compositions of $n$ into $k$ parts, each part less than $j$. Give a generating function proof that $$\kappa(n,j,k)=\displaystyle \sum_{r+sj=n}(-1)^s\binom{k+r-1}{r}\binom{k}{s},$$

where the sum is over all pairs $(r,s)\in \mathbb{N}^2$ satisfying $r+sj=n$.

I see an alternating sum, so naturally I think about the Principle of Inclusion-Exclusion. I thought to consider the number of all weak compositions of $n$, which is $\binom{n+k-1}{k-1}$ and then remove all weak compositions whose largest part is $n$, $n-1$, $\ldots$, or $j$. I have made one observation, which is that

$$ \text{the number of weak compositions with largest part $j$}=\kappa(n,j+1,k)-\kappa(n,j,k),$$

unless somehow I am mistaken (in that case, please let me know). However, this led me to some ridiculous computations. Perhaps someone else has a suggestion?

Thank you for any help offered!

Answer 1

Rewrite the summation as

$$\sum_{s=0}^{\lfloor n/j\rfloor}(-1)^s\binom{k+n-sj-1}{n-sj}\binom{k}s=\sum_{s=0}^{\lfloor n/j\rfloor}(-1)^s\binom{k+n-sj-1}{k-1}\binom{k}s\;,$$

and write out the first few terms:

$$\binom{n+k-1}{k-1}-\binom{n-j+k-1}{k-1}\binom{k}1+\binom{n-2j+k-1}{k-1}\binom{k}2-\ldots\;.$$

We’re starting with the number of $k$-part weak compositions of $n$. Then we consider the possibility that a part is $j$ or larger; there are $\binom{k}1$ ways to choose the ‘bad’ part, and $\binom{n-j+k-1}{k-1}$ ways to distribute the remaining $n-j$ amongst all $k$ parts. Note that this allows for adding some of that $n-j$ to the ‘bad’ part, so we’ve covered every composition that makes that part $j$ or more.

And at this point I expect that you can probably finish the inclusion-exclusion analysis yourself.

Answer 2

You can do some reverse engineering on this, to get the answer in terms of generating functions. Note that your sum is $$\sum_{r+s=n} (-1)^{s/j}\binom{k+r-1}r\binom k{s/j}[j\mid s]$$

This is the coefficient of $x^n$ in the product $$\left(\sum_{r\geqslant 0}\binom{k+r-1}rx^r\right)\left(\sum_{s\geqslant 0}\binom{k}{s}(-1)^sx^{js}\right)$$

which is $$\frac{1}{(1-x)^k}(1-x^j)^k$$

which is $$(1+x+x^2+\cdots+x^{j-1})^k$$

Can you prove this counts what you want? (Note this is the generating function argument required by Stanley. In general, consider a finite set $A$ of natural numbers. Then I claim the number of solutions of $x_1+\cdots+x_k=n$ with $x_i\in A$ is the coefficient of $x^n$ in $$\left(\sum_{\alpha\in A}x^{\alpha}\right)^k$$

I could have started from this, but I wanted to give you an idea on how you could figure things out.