Multichoosing (Stars and bars)

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.

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.