0
$\begingroup$

Coming up with a question whose answer is $\left(\!\!\binom{n}{k - n}\!\!\right)$ is easy: how many ways are there to create a $k$-multiset from $[n]$ such that each element in $[n]$ appears at least once? This is analogous to the question: how many ways are there to distribute $k$ identical objects to $n$ distinct recipients such that each recipient receives at least one object? You first distribute $k$ objects, then you are left to count the number of $(k - n)$-multisets from $[n]$. I get that.

Now coming up with a different way to answer these questions, namely with ${k - 1 \choose k - n}$, is where I'm struggling. I understand that you must first distribute $n$ objects to each recipient in $[n]$. Then you are left with $k - n$ objects to distribute. I don't know how to get to ${k - 1 \choose k - n}$.

Note: For those of you unfamiliar with the double parens notation, $\left(\!\!\binom{n}{k}\!\!\right)$, this denotes a $k$-multiset (or multichoose) taken from $[n]$. Examples of a $3$-multisets taken from [5] are $(1, 1, 1)$, $(3, 3, 4)$, $(1, 2, 3)$...

$\endgroup$
  • $\begingroup$ what does this double bracket notation means?? I do not even know how to right it in latex. $\endgroup$ – user265328 Sep 25 '15 at 16:42
3
$\begingroup$

It’s a basic stars and bars setup. After distributing $n$ objects, one to each of $n$ recipients, you have $k-n$ objects to distribute arbitrarily to the $n$ recipients. If you line the objects by recipient, placing dividers between those for one recipient and those for the next, you have a total of $(k-n)+n=k$ entities, $k-n$ of which are objects.

$\endgroup$
  • $\begingroup$ In the first line, should it be "After distributing $n$ objects..."? $\endgroup$ – James Pak Sep 25 '15 at 17:13
  • $\begingroup$ @James: It should indeed; fixed. Thanks! $\endgroup$ – Brian M. Scott Sep 25 '15 at 17:14

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.