0
$\begingroup$

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).

$\endgroup$

migrated from stats.stackexchange.com Jul 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.

1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ No it is not, look again $\endgroup$ – 99ProblemsAndTheyreAllCode Jul 10 '15 at 22:53
  • $\begingroup$ 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)? $\endgroup$ – blackeneth Jul 11 '15 at 1:01
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.