Multiset subset permutations

SlipEternal

MHF Helper
Nov 2010
3,728
1,571
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:

romsek

MHF Helper
Nov 2013
6,660
2,997
California
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}$
 

SlipEternal

MHF Helper
Nov 2010
3,728
1,571
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!
 

Plato

MHF Helper
Aug 2006
22,467
8,639
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~?$