Results 1 to 5 of 5

Math Help - Combinations with repetition (I think)

  1. #1
    Member
    Joined
    May 2009
    Posts
    77

    Combinations with repetition (I think)

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

    I know that if we have k identical sets that each one of them has 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):
    CC(n,k)=\dfrac{(n+k-1)!}{k!(n-1)!}

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

    However if we have to pick up from 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?
    \{2,3,5,7\}, n1=4, k=1
    \{2,3\}, n2=2, k=2
    \{2,3\}, n3=2, k=3

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

    Thank you very much.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,610
    Thanks
    1576
    Awards
    1

    Re: Combinations with repetition (I think)

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2009
    Posts
    77

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,610
    Thanks
    1576
    Awards
    1

    Re: Combinations with repetition (I think)

    Quote Originally Posted by gdmath View Post
    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:
    \{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 \{2,3\}\times(\{2,3\}\times\{2,3,5,7\})~? which is twelve triples.
    \{(2,2,2), (2,2,3), (2,2,5), (2,2,7), (2,3,3), (2,3,5), (2,3,7) (3,2,2), (3,2,3), (3,2,5), (3,2,7), (3,3,3), (3,3,5), (3,3,7)\}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2009
    Posts
    77

    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 \{2,3\} in set A. And there are four prime numbers \{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 \{(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 (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: \{(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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinations removing duplications and repetition
    Posted in the Statistics Forum
    Replies: 1
    Last Post: April 4th 2012, 03:27 AM
  2. Combination with repetition
    Posted in the Statistics Forum
    Replies: 5
    Last Post: October 17th 2011, 04:18 PM
  3. r-Combinations with Repetition Allowed
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: July 31st 2011, 04:12 PM
  4. Permutations without Repetition
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 29th 2009, 06:29 AM
  5. repetition
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: June 30th 2008, 04:13 PM

Search Tags


/mathhelpforum @mathhelpforum