Results 1 to 4 of 4

Thread: Multiset subset permutations

  1. #1
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,728
    Thanks
    1524

    Multiset subset permutations

    I am having a lapse in memory. I know I know this, but I don't recall how to calculate the number of permutations there are for a multiset.

    Here is the actual problem and how I am going about solving it. I have a deck of 60 cards. 22 of them are of type A, 4 are of type B, 4 of type C, and the rest of type D. I want to know the probability that if I draw 9 cards, I get exactly 3 of A, 2 of B, 1 of C, and 3 of D where the 9th card chosen is not B. I know a long, drawn-out process to calculate it, but I thought there was an easier way. Here is my solution:

    Suppose we have a sixty-element multiset with the following repetition numbers:

    $$\{22\cdot A, 4\cdot B, 4\cdot C, 30\cdot D\}$$

    And we want to know the number of 9-element permutations (not necessarily distinct). I can calculate this by figure out the number of permutations like this:

    $$\sum_{b=0}^4 \sum_{c=0}^4 \sum_{a=0}^{9-b-c}\dbinom{22}{a}\dbinom{4}{b}\dbinom{4}{c}\dbinom{ 30}{9-a-b-c} \dfrac{9!}{a!b!c!(9-a-b-c)!}$$

    This is the total number of possible ways to draw the first nine cards. Next, let's figure out the total number of ways to draw the first nine cards containing the elements I want:

    $$\dbinom{22}{3}\dbinom{4}{2}\dbinom{4}{1}\dbinom{ 30}{3}\left(\dfrac{9!}{3!2!1!3!}-\dfrac{8!}{3!1!1!3!}\right)$$

    I think this gives the correct answer, but it is not easy to figure out.
    Last edited by SlipEternal; Nov 21st 2018 at 06:18 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    6,534
    Thanks
    2880

    Re: Multiset subset permutations

    Suppose we look at the draw of the first 8 cards, and then the 9th separately.

    we'd want

    $P[(2,2,1,3)]P[a] + P[(3,2,0,3)]P[c] + P[(3,2,1,2)]P[d] = $

    $P[(2,2,1,3)]\dfrac{20}{52} + P[(3,2,0,3)]\dfrac{4}{52} + P[(3,2,1,2)]\dfrac{28}{52} = $

    $\dfrac{\dbinom{22}{2}\dbinom{4}{2}\dbinom{4}{1} \dbinom{30}{3}}{\dbinom{60}{8}}\dfrac{20}{52} +

    \dfrac{\dbinom{22}{3}\dbinom{4}{2}\dbinom{4}{0} \dbinom{30}{3}}{\dbinom{60}{8}}\dfrac{4}{52} +

    \dfrac{\dbinom{22}{3}\dbinom{4}{2}\dbinom{4}{1} \dbinom{30}{2}}{\dbinom{60}{8}}\dfrac{28}{52} = \dfrac{54880}{6951321}$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,728
    Thanks
    1524

    Re: Multiset subset permutations

    Quote Originally Posted by romsek View Post
    Suppose we look at the draw of the first 8 cards, and then the 9th separately.

    we'd want

    $P[(2,2,1,3)]P[a] + P[(3,2,0,3)]P[c] + P[(3,2,1,2)]P[d] = $

    $P[(2,2,1,3)]\dfrac{20}{52} + P[(3,2,0,3)]\dfrac{4}{52} + P[(3,2,1,2)]\dfrac{28}{52} = $

    $\dfrac{\dbinom{22}{2}\dbinom{4}{2}\dbinom{4}{1} \dbinom{30}{3}}{\dbinom{60}{8}}\dfrac{20}{52} +

    \dfrac{\dbinom{22}{3}\dbinom{4}{2}\dbinom{4}{0} \dbinom{30}{3}}{\dbinom{60}{8}}\dfrac{4}{52} +

    \dfrac{\dbinom{22}{3}\dbinom{4}{2}\dbinom{4}{1} \dbinom{30}{2}}{\dbinom{60}{8}}\dfrac{28}{52} = \dfrac{54880}{6951321}$
    Way easier! Thank you!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,372
    Thanks
    3268
    Awards
    1

    Re: Multiset subset permutations

    Quote Originally Posted by SlipEternal View Post
    Here is the actual problem and how I am going about solving it. I have a deck of 60 cards. 22 of them are of type A, 4 are of type B, 4 of type C, and the rest of type D. I want to know the probability that if I draw 9 cards, I get exactly 3 of A, 2 of B, 1 of C, and 3 of D where the 9th card chosen is not B. I know a long, drawn-out process to calculate it, but I thought there was an easier way. Here is my solution:
    I would find out how many ways that the ninth card drawn is a $B$, i.e. $3~A's$, 1 $B$, 1 $C$, & 3 $D's$ in the first eight then a $B$.

    There is a total of $48$ ways to choose nine of this collection. SEE HERE
    I used the generating function $\displaystyle {(\sum\limits_{k = 0}^9 {{x^k}} )^2}{(\sum\limits_{k = 0}^4 {{x^k}} )^{2}}$ The first factor is for $A~\&~D$, the second factor is for $B~\&~C$ The term $150x^9$ tells us that there are one hundred and fifty ways to make nine selections with no restrictions from that collection. Recall that selections have nothing to do with order. But you have introduced order into the question. Looking at that same webpage that are $125$ ways to select eight cards from the collection.
    Only one of those contain $3~A's$, 1 $B$, 1 $C$, & 3 $D's$ in the first eight then a $B$. The what is the probability the next card is a $B~?$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof of k-multiset coefficients, part 1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jun 19th 2010, 03:55 AM
  2. Circular Permutations of a Multiset
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jan 22nd 2010, 04:13 AM
  3. Multiset Addition Rule (proof required)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Aug 31st 2009, 07:21 AM
  4. Multiset
    Posted in the Statistics Forum
    Replies: 2
    Last Post: May 21st 2009, 03:41 AM
  5. Multiset
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Jan 27th 2008, 01:31 PM

/mathhelpforum @mathhelpforum