In the process I also thought of a #binomial #coefficient interpretation for choosing k things out of a bag of n objects when the objects can be put back and picked again. In probability problems, this is referred to as picking "with replacement".

Usually, when we say, n choose k, we do not allow repeated choices, every chosen object has to be chosen once. In this case, I want to allow replacements but at the same time, I want to keep using my trusted n choose k idea.

Here's my way around this: We'll still be picking k things, but we'll pick them not from 1 to n but from the set {1, 2, ..., 𝑛, 𝑟₁, 𝑟₂, ..., 𝑟ₖ₋₁}. That is, in addition to the n objects, we add what I'm calling "replacement tokens" 𝑟ₓ. If any of the 𝑟ₓ gets picked, then it is interpreted as the 𝑥th choice was put back and you are now choosing to pick that again. Since the 𝑘th choice is not put back, we only need replacement tokens for choices 1 to k-1.

With these replacement tokens, the problem becomes a standard choose k things out of this set, which we can resolve using the binomial coefficient to get: \({ n+k-1 \choose k }\).

I believe the standard approach to this is via #StarsAndBars but I liked the idea of this "replacement token". Admittedly, I didn't want to use stars and bars here and made up some stuff which I happened to like. :)

#math #counting #proof