Multichoosing (Stars and bars)
Suppose we have 'n' Stars and 'k' bins. We have to distribute 'n' stars in 'k' bins (using k-1 bars) such that bins can be empty. We can do this in $\binom {n+k-1}{k-1}$ = $\binom {n+k-1}{n}$ ways. But Sometimes we use another notation $\left({{k}\choose {n}}\right)$ to represent $\binom {n+k-1}{k-1}$, Which says 'k multichoose n'. But normally as n > k, then how can we choose more objects from less objects i.e. n from k. So, I think It has to be like this $\left({{n}\choose {k}}\right)$.
$\endgroup$ 23 Answers
$\begingroup$The notation $\left( \! \binom{k}{n} \! \right)$ stands for the number of multisets of size $n$ on $k$ symbols. The important thing to note is that the $k$ symbols are distinguishable and the $n$ "positions" in the multiset are indistinguishable (order doesn't matter).
This suggests a bijection (one-to-one correspondence) with the number of ways to put balls (indistinguishable objects) in labeled boxes (distinguishable objects). Specifically, the $k$ symbols in the multiset correspond to the boxes, and the $n$ positions in the multiset correspond to the balls.
Therefore, $$ \left( \! \binom{k}{n} \! \right) = \binom{n + k - 1}{k - 1} = \binom{n + k - 1}{n}. $$ The only restrictions on the integers $k$ and $n$ are $$ n \ge 0 \quad \text{and} \quad k \ge 1. $$
In particular, it doesn't matter which is greater.
$\endgroup$ 2 $\begingroup$The normal notation $n\choose{k}$ is read aloud as "n choose k" because it is the number of ways to construct a set of k objects by choosing them from a set of n objects. The key thing to note her is that you are choosing without repetition. Once an object has been chosen, there are less objects to choose from.
The notation $\left( k \choose n\right)$ is read aloud as "k multichoose n" because it is the number of ways to choose a set of n objects by choosing them from a set of k objects, but this time you are allowed to choose as many of each object as you like. So if you like, you write down what you chose and then you put the object back, so there are always the same number of objects to choose from. Alternatively, you can think that there are a large collection of objects that come in k types. Thus k can be smaller than n because you just choose some of the same objects you already chose to make up the extra. Indeed, even if k was 1, you could still choose n of the same object and it would work.
The reason the k is at the top is because of how it relates to the "stars and bars". Remember that the stars and bars are really a description of the instructions for making your combination. You have n stars and k bins. You imagine your k bins in a row, and you start at the leftmost bin. In the "stars and bars" notation, the star tells you to put another star in the bin you're up to, and the bar tells you to switch to a new bin.
Now think about choosing n objects out of k when you can choose objects multiple times. Number your k objects from 1 to k and start out thinking about object 1. Now the stars tell you to pull out another of the same object, and the bars tell you to start looking for a new type of object.
$\endgroup$ $\begingroup$"How can we choose more objects from less objects i.e. $n$ from $k$" (when $n > k$)?
It is very easy. We do not "use up" one of the $k$ objects when we choose it. We can choose the same object again as many times as we like (just as we can put many stars in the same bin).
You have a pile of $n$ stars. One at a time, you pick up a star, choose a bin (from a set of $k$ bins), and put the star in it. Then you repeat the process (choosing from the same set of $k$ bins every time) until all stars are in bins.
Now you have made $n$ selections from an initial set of $k$ choices. And you can keep on making as many more selections as you want from the same set.
Note that using the stars-and-bars argument, you can conclude that $$ \left( \! \binom{k}{n} \! \right) = \binom{n + k - 1}{k - 1}. $$ The right side has a $k$ on the bottom and an $n$ on the top, sure enough. But it also has a $k$ on top. So the right side already looks a little like the left side, though not very much.
But you could just as easily use stars-and-bars to say that $$ \left( \! \binom{k}{n} \! \right) = \binom{k + n - 1}{n}. $$ Now that looks much more compatible. Both the left and right side have a $k$ on top and an $n$ on the bottom, showing that the notations are not so very contradictory after all. The top part of the right-side notation is just a little larger than the top of the left side, namely it is greater by $n - 1$.
$\endgroup$
