2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How did you obtain that $\frac{1}{(1-x)^k}=\sum_{r\geq 0}\binom{k+r-1}{r} x^r$? $\endgroup$ – Selma Feb 24 '15 at 22:53
  • $\begingroup$ @Selma You can differentiate $(1-x)^{-1}=1+x+x^2+\cdots$ many times, or you can use that $(1+x)^{\alpha}=\sum_{\nu \geqslant 0}\binom {\alpha}\nu x^\nu$. Note that $\alpha$ can be any number, in particular $-k$. $\endgroup$ – Pedro Tamaroff Feb 24 '15 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.