Notes on Combinatorics
Result 4: Unordered, with replacement:
`((n+k-1),(k))={(n+k-1)!}/{k!(n-1)!}'
Why isn't the formula `n^k/{k!}` ???
At first glance, you might think that there are `n^k` ways to distribute `k` markers in `n` bins, then divide by `k!` to get rid of duplicates, but this doesn't quite work. We can see this with the example of choosing 2 from the set `\{ A,B,C,D \} `: if we start with the ordered, with replacement case, we get `4^2 = 16` possibilities:
`[[A A,A B,A C,A D],[B A,B B,B C,B D],[C A,C B,C C,C D],[D A,D B,D C,D D]]`
Now get rid of "duplicates":
`[[A A,A B,A C,A D],[ ,B B,B C,B D],[,,C C,C D],[,,,D D]]`
We have 10 possibilities, which is greater than
`n^k/{k!} = 16/{2!} = 8`