§ Stars and bars by direct bijection
We know that the number of element multisets using letters from
is . That is, we are allowed to pick elements from
repeatedly, and we want such elements.
§ The usual proof: stars and bars
The usual proof involves creating "stars" ( ) which need to be placed in
buckets. These buckets are created by having "bars" ( ). For example, if we
wish to consider all element multisets of the letter : :
§ Direct bijection.
To build a direct bijection, map a multiset of into a subset of , which
is counted by .
I found this very elegant, because it "de-multisets" the multiset by adding just enough to make each element unique,
and then simply counts the unique subset. Very slick! We need to add to the final index, and the largest number
we can have is so we need values. We need a size multiset, making us need .
- We are first given a multiset of , say ( for multiset).
- We make the representation unique by imposing an ascending order, so we write , where each .
- Now, we map the above sequence to a set of unique values, by mapping . Since we have that .
- This gives us the set .
- See that this process is reversible. Given some set, say , order in ascending order to get and then subtract from to get .
- Reference: Bijective Combinatorics