4
$\begingroup$

I'm looking for an alternative to the following (possibly standard) proof for the number of weak compositions:

The number of $k$-compositions of $n+k$ corresponds to a weak one by subtracting 1 from each "bin". Thus we have $\binom{n+k-1}{k-1}$.

While I kind of like this proof and always felt it made sense lately I've been left wanting something a little more convincing. Does anyone have a different proof of this result?

$\endgroup$
5
$\begingroup$

The argument that you outlined should be completely convincing: it displays a bijection between the set of weak $k$-compositions of $n$ and the number of $k$-compositions of $n+k$.

It’s certainly possible to give another argument, however. Line up $k-1$ dividers, and distribute your $n$ objects into the $k-1$ spaces between adjacent dividers, before the first divider, and after the last one. Each possible distribution of objects gives you a weak $k$-composition of $n$, and vice versa. Each of these distributions can be regarded as a string of $n$ objects and $k-1$ dividers, and the corresponding weak composition is completely determined by the location of the dividers in the string. There are $\binom{n+k-1}{k-1}$ ways to place the $k-1$ dividers in the string, so there are $\binom{n+k-1}{k-1}$ weak compositions of $n$.

This is one of the two arguments commonly known as stars-and-bars arguments.

$\endgroup$

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.