Thread: Combinations with repetition (I think)

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

I know that if we have identical sets that each one of them has 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):


For example, we have two sets of four (same) primes and we want to find out how many combinations we can get, the answer is:


However if we have to pick up from 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?




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

Thank you very much.

I do not follow your question.
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.

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.

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:
that is six pairs not seven.

Then do you want which is twelve triples.

Sorry for the inconvenience.

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

There are two prime numbers in set A. And there are four prime numbers 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 . Correct?

My problem is that i do not wat to count the pair 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: are the same combination).

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