[Math] Unique combinations of 7 items (repetition allowed, order doesn’t matter)

combinatorics

I am trying to calculate the number of unique combinations for a 7 element set with repetition allowed where order doesn't matter.

For example:

S = {a, b, c, d, e, f, g}

3 items per set

aaa: valid
aab: valid
aab = aba = baa (these three outputs should only count as 1 combination)

I've started with the total number of possible combinations (7^n) and tried remove the ones that are duplicates by nature, however I cannot figure out how to do this. Any help or pointers in the right direction is greatly appreciated.

Best Answer

This is known as multichoose; explicitly, the number you're after is "$7$ multichoose $3$." The basic theorem to keep in mind is that "$n$ multichoose $k$" equals $[n-1,k],$ where $$[-,-] : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$$ is the "symmetric binomial coefficient" defined by $$[a,b] = \frac{(a+b)!}{a!b!}.$$

So "$7$ multichoose $3$" equals $$[7-1,3]$$ which equals $$\frac{9!}{6!3!}$$ which equals $$84.$$

Related Question