# Unique combinations from 7 items where repetition is allowed, and order doesn't matter

I am trying to calculate the number of unique combinations from a 7-element set where repetition is allowed and order doesn't matter.

For example: Suppose $S = \{a, b, c, d, e, f, g\}$, and I want 3 items per set.

• $aaa$ is valid.
• $aab$ is valid.
• $aab = aba = baa$ (these three outputs should only count as 1 combination)

I know I have to start with the total number of possible combinations ($7^n$) and remove the ones that are duplicates by nature, however I am blanking on how to handle the removal of duplicates (due to order not mattering).

## migrated from stats.stackexchange.comJul 10 '15 at 22:03

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

This is the "multiset" problem and is a duplicate of this question on Stack Overflow.

• No it is not, look again – 99ProblemsAndTheyreAllCode Jul 10 '15 at 22:53
• You may want to clarify the question, as your example looks like it has the solution 7 multichoose 3. Perhaps you're after the powerset of the multiset or the unordered tuples(S,k)? – blackeneth Jul 11 '15 at 1:01

The problem can be conceived as placing 3 identical balls into 7 distinct bins,

and solved using "stars and bars" explained here as ${(3+7-1)\choose(7-1}$ = 84

Just verifying by a longer method, you could categorise as

3 of a kind: ${7\choose 1} = 7$

2-1 of a kind: ${7\choose 1}\cdot{6\choose 1} = 42$

1-1-1 of a kind: ${7\choose 3}= 35$

Total # of combinations: 84