# Thread: Combinations with repetition (I think)

1. ## Combinations with repetition (I think)

Long time no see...
My greetings to all forum users.

I know that if we have$\displaystyle k$ identical sets that each one of them has $\displaystyle n$ objects and we want to pick $k$ objects, one from each set, how many combinations do we have?
The formula is (stars and bars approach):
$\displaystyle CC(n,k)=\dfrac{(n+k-1)!}{k!(n-1)!}$

For example, we have two sets $\displaystyle k=2$ of four $\displaystyle n=4$ (same) primes and we want to find out how many combinations we can get, the answer is:
$\displaystyle CC(n,k)=\dfrac{(4+2-1)!}{2!(4-1)!}=10$

However if we have to pick up from $\displaystyle k$ sets, where every set is a subset of a previous one, how many combinations there are? For example, if we have the following 3 sets and pick up a prime from each one set, how many combinations do we have?
$\displaystyle \{2,3,5,7\}, n1=4, k=1$
$\displaystyle \{2,3\}, n2=2, k=2$
$\displaystyle \{2,3\}, n3=2, k=3$

Is there a compact formula? An explanation, if possible would be thankful.

Thank you very much.

2. ## Re: Combinations with repetition (I think)

In the first part it seems that you are asking about multisets.

But the second part about subsets seems to complicate things beyond a simple answer.

Give a better or fuller example of the second part.

3. ## Re: Combinations with repetition (I think)

Yes indeed, my example is incomplete. Sorry for that

To my previous example:

{2,3,5,7} n1=4, k=1
{2,3,} n2=2, k=2
{2,3,} n3=2, k=2

I extract my desired result as follow:

- First I get the combinations of first 2 sets (sets k=1, k=2, their combinations are 7):
(2,2), (2,3), (2,5), (2,7), (3,3), (3,5), (3,7)

- Then I use the new set and the third (of the initial sets, in this case set k=3) and i extract their combinations. I do not want the duplicates. Their combinations in this case are 10:
(2,2,2), (2,2,3), (2,2,5), (2,2,7), (2,3,3), (2,3,5), (2,3,7), (3,3,3),(3,3,5),(3,3,7)

I repeat the steps (if i have more initial sets).
What i am trying to do is to find a general formula to caclulate the total combinations when i know the ordinal (n1,n2, n3,...) of the sets. My problem is that sets contain the same elements (let's keep it as primes) and so there might be duplicates.

Thank you a lot for your time.

4. ## Re: Combinations with repetition (I think)

Originally Posted by gdmath
To my previous example:
{2,3,5,7} n1=4, k=1
{2,3,} n2=2, k=2
{2,3,} n3=2, k=2
I extract my desired result as follow:
- First I get the combinations of first 2 sets (sets k=1, k=2, their combinations are 7)2,2), (2,3), (2,5), (2,7), (3,3), (3,5), (3,7)
Now I am truly confused. What you now have are ordered pairs:
$\displaystyle \{2,3\}\times\{2,3,5,7\}=\{(2,2), (2,3), (2,5), (2,7), (3,3), (3,5), (3,7)\}$ that is six pairs not seven.

Then do you want $\displaystyle \{2,3\}\times(\{2,3\}\times\{2,3,5,7\})~?$ which is twelve triples.
$\displaystyle \{(2,2,2), (2,2,3), (2,2,5), (2,2,7), (2,3,3), (2,3,5), (2,3,7)$$\displaystyle (3,2,2), (3,2,3), (3,2,5), (3,2,7), (3,3,3), (3,3,5), (3,3,7)\}$

5. ## Re: Combinations with repetition (I think)

Sorry for the inconvenience.

I will try to be more ananlytic, just in case.

There are two prime numbers $\displaystyle \{2,3\}$ in set A. And there are four prime numbers $\displaystyle \{2,3,5,7\}$ in set B. I have two slots (I, II). The first slot can be filled by an element of set A and the second slot by the element of set B. There are total 8 combinations $\displaystyle \{(2,2), (2,3), (2,5), (2,7),(3,2), (3,3), (3,5), (3,7)\}$. Correct?

My problem is that i do not wat to count the pair $\displaystyle (2,3) or (3,2)$ twice (i do not want duplicates).

Similarily, at next step, I do not want to count the permutations of same elements more than once. (For example: $\displaystyle \{(2,2,3), (2,3,2), (3,2,2)\}$ are the same combination).

My most sincere thanks that you have spent time on my problem.