Combinatorics

← return to practice.dsc40a.com


This page contains all problems about Combinatorics.


Problem 1

Source: Spring 2023 Final Part 2, Problem 2

You roll a 12-sided die 8 times.


Problem 1.1

What is the probability you roll 8 distinct values?

\dfrac{{12 \choose 8}\cdot8!}{12^8} = \dfrac{12}{12}\cdot\dfrac{11}{12}\cdot\dfrac{10}{12}\cdot\dots\cdot\dfrac{5}{12}

There’s two ways you can think of this problem.

The numerator {12 \choose 8}\cdot8! is the number of total possible permutations of 8 distinct values; {12 \choose 8} possible sets of 8 distinct values times 8! orderings, because the die could roll the same set of distinct values in 8! different ways. The denominator 12^8 is the number of total possible outcomes. Altogether, dividing the numerator by the denominator gives us the probability of rolling 8 distinct values.

We can also solve this problem differently by realizing that the rolls are independent. In the first roll the probability of getting a new number is 1 (since any number would be new), now in the second roll the probability of getting a new number is \frac{11}{12} since we’ve only rolled one number so rolling any of the other 11 numbers would be rolling a new number.If you keep doing this for each roll, and multiply the independent probabilities of getting a new number in each of the rolls you’ll get \dfrac{12}{12}\cdot\dfrac{11}{12}\cdot\dfrac{10}{12}\cdot\dots\cdot\dfrac{5}{12}


Problem 1.2

What is the probability you roll exactly 7 distinct values?

\dfrac{{8 \choose 2}\cdot{12 \choose 7}\cdot7!}{12^8}

Again, I’m going to show you two different ways you can think of this problem. We can get the total number of outcomes that get you exactly 7 distinct values by doing the following, first choose 7 from the 12 possible numbers (there’s {12 \choose 7} ways to do it), then choose a number to duplicate (there’s {7 \choose 1} ways to do that), lastly you need to order them. From the 8 possible places you have availible you need to choose 2 for the repeated value (there’s {8 \choose 2} ways to do that), then once you chose a placement for your reapeted value you need to choose one for each of the remaing 6 values(there’s 6! ways to do that). Finally just multiply the different ways you can perform each of those actions and you’ll get the number of ways you can roll 7 different values \begin{align*} {12 \choose 7}\cdot{7 \choose 1}\cdot{8 \choose 2}\cdot6! = {8 \choose 2}\cdot{12 \choose 7}\cdot7! \end{align*}

lastly, just divide by the total number of possible outcomes and you get \dfrac{{8 \choose 2}\cdot{12 \choose 7}\cdot7!}{12^8}

You could also find the number of rolls with exactly 7 different values by doing the following. First, select an ordered string of size 7 from the 12 possible values (there’s {12 \choose 7}\cdot7! ways to do that), then take the first value of the string as the duplicated value and keep the others as they are, now you only need to place 2 copies of the repeated value somewhere on your string of 6 numbers (there’s {8 \choose 2} ways to do that), multiply this the ways you can do these two actions and divide by total number of outcomes and you’ll get \dfrac{{8 \choose 2}\cdot{12 \choose 7}\cdot7!}{12^8} This solution is faster but less intuitive.



Problem 2

Source: Spring 2023 Final Part 2, Problem 4

At Panda Express, there are 18 items available on the menu. Food is served on plates that are divided into three equal sections, and all sections of the plate must contain exactly one menu item.


Problem 2.1

Suppose each section of the plate is a different color (in a clockwise order around the plate, the sections are red, yellow, blue). How many different-looking plates of food can be created, if we must have three different menu items on the plate?

One example plate of food has Honey Walnut Shrimp in the red section, Kung Pao Chicken in the yellow section, and brown rice in the blue section.

{18 \choose 3} \cdot 3!

This problem is exactly asking for the number of permutations of three elements from a pool of 18 elements, which is \begin{align*} 18\cdot17\cdot16 = \frac{18!}{15!} = {18 \choose 3} \cdot 3! \end{align*}

You should remember that whenever you draw items without replacement and the order matters then you are calculating a permutation. Alternatively, you can reason that in the red segment of the plate, you can have any of the 18 different menu items, then for the yellow segment you only have 17 menu items available, since the red already has one, lastly you have 16 items left for the blue part of the plate. Then just multiply all the ways you can choose menu items for each segment getting a total of \begin{align*} 18\cdot17\cdot16 = {18 \choose 3} \cdot 3! \end{align*}


Problem 2.2

Suppose each section of the plate is a different color (in a clockwise order around the plate, the sections are red, yellow, blue). How many different-looking plates of food can be created, if we are allowed to have the same food in multiple sections?

18^3

In this question, since we are allowed to repeat menu items, we have 18 options for each of the sections of the plate. Then when you multiply all the ways you can choose items for a secyion of the plate you get 18\cdot18\cdot18 = 18^3. Similarly to how we explained the question before this one, aske your self if the drawing process has replacement and if the order matters. In this case you’ll find that we have replacement and we also have ordeirng, so this is a sequence, and the number of sequence’s of lenght k from a pool of n elements is n^k.


Problem 2.3

Suppose each section of the plate is the same color (white). How many different-looking plates of food can be created, if we must have three different menu items on the plate?

One example plate of food has, in a clockwise order around the plate, Eggplant Tofu, Broccoli Beef, and fried rice. This is the same plate as the one that has, in a clockwise order, Broccoli Beef, fried rice, and Eggplant Tofu, because one plate can be rotated to look like the other (this counts as the same.)

2 \cdot {18 \choose 3}

Similarly to how we solved the previous problems, we are going to deconstruct the process of building a plate with the given characteristics. First, we know that any plate must have three items, so let’s start by choosing three items from the 18 menu items we have available (we have {18 \choose 3} ways to do that).

Now once you chose the menu items that go on your plate, you need to arange them on your plate, normally if we are aranging three distinct elements on a line we know that there’s 3! ways to do that, unfortunately like we saw in the prompt of this problem we need to account for when we rotate the plate. In the prompt it was signaled that the plate with Eggplant Tofu, Broccoli Beef, and fried rice in clockwise order around the plate, is the same as the plate with Broccoli Beef, fried rice, and Eggplant Tofu (also in clockwise order), this happens because if you rotate your fisrt plate in counter clockwise direction then you would get the second plate, and in fact we could do this again to show those two plates are the same as the plate with fried rice, Eggplant Tofu, and Broccoli Beef. If you were to do the rotation again you would get the original plate, so for any specific plate we can find three different lines that describe the same plate, thus if we divide the number of ways to order our 3 menu items on a line(3!) by 3, we should get the number of different plates we can build with any three items, so \frac{3!}{3} = 2

Finally we only need to mutiply the number of ways we can choose three menu items by the number of plates we can build with those three items getting 2 \cdot {18 \choose 3}.


Problem 2.4

Suppose each section of the plate is the same color (white). Now we’d like to consider what happens if we can have the same food in multiple sections. What do we need to add to 4.3’s answer to get the number of different-looking plates of food that can be created, if we are allowed to have the same food in multiple sections?

As before, two plates that can be rotated to look like one another count as the same.

2 \cdot {18 \choose 2} + {18 \choose 1}

Now that we are allowed to repeat menu items we need to consider the 2 new types of plates, type 1 a plate with the same menu item 3 times, type 2 a plate with a repeated menu item and an additional menu item. Then the total number of plates should be our answer from 4.3 plus the number of plates with type 1 and number of plates with type 2.

Type 1 Counting the number of type 1 plates should be fairly simple, if your plate only contains one menu item then there should be one plate of this type for each of the menu items, therefore there’s 18 plates like this.

Type 2 Now for type 2, we can start by chossing two items from the menu (there’s 18 \choose 2 ways to do that) then from here note that you need to choose which item you are going to repeat because depending on which one you choose to double you get a different plate (there’s 2 options to double), then you should also consider the order but you should realize that no matter how you arange the item on your plate you are just getting rotations of the same plate, therefore your total number of plates of type 2 is 2 \cdot {18 \choose 2}

Lastly, just add both the plates of type 1 and type 2, and that’s the number you need to add to your answer from 4.3. Answer: 2 \cdot {18 \choose 2} + {18 \choose 1}



Problem 3

Source: Spring 2023 Midterm 2, Problem 1

A set of chess pieces has 32 pieces. 16 of these are black and 16 of these are white. In each color, the 16 pieces are:

When there are multiple pieces of a given color and type (for example, 8 white pawns), we will assume they are indistinguishable from one another.

Consider an experiment where each of n people selects one piece from their own set of 32 chess pieces, uniformly at random. The result of the experiment is a description of the colors and types of the pieces each person selected. For example, if n=3, one possible result is:

How many results are possible for this experiment with n people?

12^n.

The key to solving this problem is the note “When there are multiple pieces of a given color and type (for example, 8 white pawns), we will assume they are indistinguishable from one another.” This means we count each type of chess piece for the colors black and white. There are 6 different types of chess pieces: pawn, bishop, knight, rook, queen, and king. There are 2 possible colors: black and white. This means there are 6 \cdot 2 = 12 unique colored types of chess pieces.

There are 12 options for the first person, there are 12 options for the second person, and so on, for n people, so we can write:

12 \cdot 12 \cdot \dots \cdot 12 = 12^n

We see there are 12^n possible results for this experiment because there are n people in this experiment who can each select 12 unique combinations.


Problem 4

Source: Spring 2023 Midterm 2, Problem 2

A set of chess pieces has 32 pieces. 16 of these are black and 16 of these are white. In each color, the 16 pieces are:

When there are multiple pieces of a given color and type (for example, 8 white pawns), we will assume they are indistinguishable from one another.

Suppose you randomly select 2 pieces from a set of 32 chess pieces, without replacement.


Problem 4.1

You glance at the pieces just long enough to see that both pieces are white. What is the probability that you have 2 pawns?

\dfrac{8}{16}\cdot\dfrac{7}{15} = \dfrac{7}{30}

We get \dfrac{8}{16} from the fact there are 8 white pawns and 16 white chess pieces. So the chance of first getting a pawn is \dfrac{8}{16}.

Now we assume that we have a white pawn, meaning there are 8-1=7 white pawns left and 16 - 1 = 15 white chess pieces, which means we have a \dfrac{7}{15} chance for getting another white pawn.

From here we simplify the answer by writing:

\dfrac{8 \cdot 7}{16 \cdot 15} = \dfrac{56}{240} = \dfrac{7}{30}


Another way to solve this is by using combinatorics: Note that {8 \choose 2} means “8 choose 2.”

\dfrac{{8 \choose 2}}{16 \choose 2} = \dfrac{\frac{8}{32}\cdot\frac{7}{31}}{\frac{16}{32}\cdot\frac{15}{31}} = \dfrac{7}{30}


Problem 4.2

True or False: Having two pawns is independent of having two white pieces.

False.

We know that two probabilities are independent of each other if P(A \cap B) = P(A) \cdot P(B).

  • Let P(A) be the probability of getting a white piece twice in a row.
  • Let P(B) be the probability of getting a pawn twice in a row.

We can calculate the probability of getting a white piece twice in a row P(A) = \frac{16}{32} \cdot \frac{15}{31} = \frac{15}{62}. We get \frac{16}{32} from the fact there are 16 white pieces out of the 32 total pieces. We get \frac{15}{31} from the fact there are now 15 white pieces out of the 31 pieces left after taking out a white piece.

We can also calculate the probability of getting a pawn twice in a row. Note that the color of the pawn does not matter! P(B) = \frac{16}{32} \cdot \frac{15}{31} = \frac{15}{62}. We get \frac{16}{32} from the fact there are 16 pawns (8 black pawns plus 8 white pawns) out of the 32 total pieces. We get \frac{15}{31} from the fact there are now 15 pawns out of the 31 pieces left after taking out a pawn.

We can now calculate P(A) \cdot P(B): \frac{15}{62} \cdot \frac{15}{62} = \frac{225}{3844}

Recall we calculate P(A \cap B) = P(A) \cdot P(B|A).

We solved for P(B|A) in part A of the problem: \frac{7}{30}. We also already solved for P(A) above: \frac{15}{62}.

\frac{15}{62} \cdot \frac{7}{30} = \frac{7}{124}

We can see that P(A \cap B) \neq P(A) \cdot P(B) because \frac{7}{124} \neq \frac{225}{3844}, so the answer is “False.”



Problem 5

Source: Winter 2023 Final, Problem 7


Problem 5.1

There is one box of bolts that contains some long and some short bolts. A manager is unable to open the box at present, so she asks her employees what is the composition of the box. One employee says that it contains 60 long bolts and 40 short bolts. Another says that it contains 10 long bolts and 20 short bolts. Unable to reconcile these opinions, the manager decides that each of the employees is correct with probability \frac{1}{2}. Let B_1 be the event that the box contains 60 long and 40 short bolts, and let B_2 be the event that the box contains 10 long and 20 short bolts. What is the probability that the first bolt selected is long?

P(\text{long}) = \frac{7}{15}

We are given that: P(B_1)=P(B_2)=\frac{1}{2} P(\text{long}|B_1) = \frac{60}{60 + 40} = \frac{3}{5} P(\text{long}|B_2) = \frac{10}{10 + 20} = \frac{1}{3}

Using the law of total probability:

P(\text{long})=P(\text{long}|B_1) \cdot P(B_1)+P(\text{long}|B_2) \cdot P(B_2) = \frac{3}{5} \cdot \frac{1}{2} + \frac{1}{3} \cdot \frac{1}{2} = \frac{7}{15}



Problem 5.2

How many ways can one arrange the letters A, B, C, D, E such that A, B, and C are all together (in any order)?

There are 3! \cdot 3! permutations.

We can treat the group of A, B, and C (in any order) as a single block of letters which we can call X. This will gurantee that any permutation we find will satisfy our condition of having A, B, and C being all together.

Our problem now has 3! = 6 permutations of our new letter bank: X, D, and E.

XDE XED DXE EXD DEX EDX

Let’s call these 6 permutations “structures”. For each of these structures, there are 3! = 6 rearrangements of the letters A, B, and C inside of X.

So, with 3! different arrangements of D, E and our block of letters (X), and with each of those arrangements individually having 3! ways to re-order the group of ABC, the overall number of permutations of ABCDE where ABC are all together, in any order, is 3! \cdot 3!.


Problem 5.3

Two chess players A and B play a series of chess matches against each other until one of them wins 3 matches. Every match ends when one of the players wins against the other, that is, the game does not ever end in draw/tie. For example, one series of matches ends when the outcomes of the first four games are: A wins, A wins, B wins, A wins. In how many different ways can the series occur?

There are 20 ways the series can be won.

The series ends when the last game in the series is the third win by either player. Overall, there must be at least 3 games to end a series (all wins by the same player) and at most 5 games to end a series (each player has two wins, and then a final win by either player) before either player wins 3 games. Let’s assume player A always wins, and then we’ll multiply the number of options by two to account for the possibilities where player B wins instead.

Breaking it down:

  • For a series that ends in 3 games - there is a single option (all wins by player A).

  • For a series that ends in 4 games, we’ve assumed the last game is a player A win to end the series, therefore the 3 preceding games have {3 \choose 2} options for player A winning 2 of the 3 preceding games.

  • For a series that ends in 5 games, we’ve assumed the last game is a player A win to end the series, therefore the 4 preceding games have {4 \choose 2} options for player A winning 2 of the 4 preceding games.

Overall, the number of ways the series can occur is: 2 \cdot (1 + {3 \choose 2} + {4 \choose 2}) = 20



Problem 6

Source: Winter 2024 Final Part 2, Problem 1

Consider an experiment where each of n people selects one piece from their own set of chess pieces, uniformly at random. A chess set has 32 pieces. 16 of these are black and 16 of these are white. In each color, the 16 pieces are:

The result of the experiment is a description of the colors and types of the pieces each person selected. For example, if n=3, one possible result is:


Problem 6.1

How many results are possible for this experiment with n people?

12^n

To answer this question we must determine how many different pieces each person can choose. In a complete chess set we know that there’s pawns, knights, bishops, rooks, queens, and kings. Then we also know that each of these pieces can be aither black or white, therefore there’s a totoal of 6 \cdot 2 = 12 different pieces. Notice that a complete chess set has 32 total pieces, but there’s multiple duplicates in those 32 pieces that is why we say there’s only 12 different pieces on a chess set.

Now since every person has their own chess set, we know that each of them can get any of the 12 pieces, therefore if we do this with one person there would be 12 possible outcomes, now if we do it with two persons the first person can get any of the 12 pieces, but then for each piece that person 1 can choose person 2 can choose from their 12 pieces, which means that in this case there’s 12 \cdot 12 outcomes. if we keep doing this for n persons we’ll get that there’s 12 \cdot \dots \cdot 12 = 12^n.


Problem 6.2

As n becomes large, what fraction of n people has selected a black pawn? Choose the answer that’s closest to the actual fraction.

\frac{1}{4}

First, let’s calculate the probability of one person choosing a black pawn. We know that the complete chess set has 32 pieces, and out of those 32 there are 8 black pawns, which gives us a probability of \frac{8}{32} = \frac{1}{4} of selecting a black pawn. Now, think about how we interpret probabilities; for example, if we say that the probability of getting heads when flipping a coin is \frac{1}{2} that just means that if we flip a coin over and over, we expect to see heads \frac{1}{2} of the time. Similarly, when we say that the probability of choosing a black pawn is \frac{1}{4}, that means that if we were to choose a chess piece over and over, we expect to choose a black pawn \frac{1}{4} of the time.

As n becomes large, we choose chess pieces over and over n times. Therefore, you still expect to see the black pawn \frac{1}{4} of the time.



Problem 6.3

True or False: Having two pawns is independent of having two white pieces.

False.

We know that two probabilities are independent of each other if P(A \cap B) = P(A) \cdot P(B).

  • Let P(A) be the probability of getting a white piece twice in a row.
  • Let P(B) be the probability of getting a pawn twice in a row.

We can calculate the probability of getting a white piece twice in a row P(A) = \frac{16}{32} \cdot \frac{15}{31} = \frac{15}{62}. We get \frac{16}{32} from the fact there are 16 white pieces out of the 32 total pieces. We get \frac{15}{31} from the fact there are now 15 white pieces out of the 31 pieces left after taking out a white piece.

We can also calculate the probability of getting a pawn twice in a row. Note that the color of the pawn does not matter! P(B) = \frac{16}{32} \cdot \frac{15}{31} = \frac{15}{62}. We get \frac{16}{32} from the fact there are 16 pawns (8 black pawns plus 8 white pawns) out of the 32 total pieces. We get \frac{15}{31} from the fact there are now 15 pawns out of the 31 pieces left after taking out a pawn.

We can now calculate P(A) \cdot P(B): \frac{15}{62} \cdot \frac{15}{62} = \frac{225}{3844}

Recall we calculate P(A \cap B) = P(A) \cdot P(B|A).

To find P(B|A), we assume that both pieces are white and imagine the probabilities of getting two pawns from that batch of white pieces. To get the first pawn, the probability is \frac{8}{16} (8 pawns out of 16 white pieces). To get the second pawn, the probability is: \frac{7}{15} (7 remaining pawns out of 15 remaining white pieces). So, the probabilitiy of getting two pawns given we have two white pieces is P(B|A) = \frac{8}{16} \cdot \frac{7}{15} = \frac{7}{30}. We also already solved for P(A) above: \frac{15}{62}.

\frac{15}{62} \cdot \frac{7}{30} = \frac{7}{124}

We can see that P(A \cap B) \neq P(A) \cdot P(B) because \frac{7}{124} \neq \frac{225}{3844}, so the answer is “False.”



Problem 7

Source: Winter 2024 Midterm 2, Problem 1

Quarks are one of the smallest fundamental particles in physics. There are 6 types of quarks: up, down, top, bottom, strange, charm. Each one of the 6 types of quarks can be in two states: quark or antiquark.


Problem 7.1

Consider an experiment where we select n quarks uniformly at random. The result of the experiment is a description of the type and state of the quark selected. For example, if n=3, one possible result is:

How many results are possible for this experiment with n quarks?

12^n

Each quark has 6 \cdot 2 = 12 possibilities because there are 6 possible types and 2 possible states. Since our experiment involves independently picking one of these 12 possibilities for each of our n quarks, the total number of results for the experiment is 12^n.



Problem 7.2

A meson is formed by combining two quarks. In order to form a meson, the two quarks must satisfy the following rules:

Consider an experiment where we select n mesons uniformly at random. How many results are possible for this experiment?

None of the above (72^n).

For making a meson, we need to choose two quarks. The first quark we choose has 6 \cdot 2 = 12 possibilities because there are 6 possible types and 2 possible states. However, our second quark cannot have the same state as our first; so the second quark has 6 \cdot 1 = 6 possibilities because there are still 6 possible types, but only 1 possible state.

This means a single meson has 12 \cdot 6 = 72 possibilities. (If the order of the quark and antiquark did not matter, it would instead have \frac{72}{2} = 36 possibilities). So, an experiment where we select n mesons uniformly at random has 72^n unique results.



Problem 8

Source: Winter 2024 Midterm 2, Problem 2

A special poker card deck contains the 52 standard cards:

Heart: 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A
Diamond: 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A
Club: 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A
Spade: 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A


…plus two wildcards: a Red Joker and a Black Joker. The total number of cards in this card deck is 54.


Problem 8.1

How many different four-card hands can be selected from this deck? (Note: order does not matter in a card hand.)

{54 \choose 4} = 316251

Since order does not matter, we would use a combination instead of a permutation here. From 54 unique cards in our poker deck, we can choose 4 at random to get a card hand.

An alternative way to think about it: there are 54 options for the first card we pick, 53 for the second card, 52 for the third card, etc. For four cards, we have 54 \cdot 53 \cdot 52 \cdot 51 hands. However this will count the same hand in different card orders as different hands, which we don’t want. To correct this, we divide by 4! (4 \cdot 3 \cdot 2 \cdot 1), because each unique hand will appear 24 times but in different orders.

\frac{54 \cdot 53 \cdot 52 \cdot 51}{4 \cdot 3 \cdot 2 \cdot 1} = {54 \choose 4} = 316251



Problem 8.2

For this deck, how many 5 card hands are there that include four-of-a-kind (four cards of the same value)? Show your work.

650

Since the first 4 cards are four-of-a-kind (same number), there are 13 ways to select a four-of-a-kind. For the 5th card, there are 50 total choices (12 remaining values \cdot 4 suits + 2 wildcards). So there are a total 13 \cdot 50 = 650 options.


Problem 8.3

In certain poker rules, a bomb is defined as either four-of-a-kind, or two wildcards (red joker and black joker). Suppose you randomly draw a 4 card hand and you found a bomb in it, what is the probability that the bomb is four-of-a-kind? Show your work.

P(\text{Four of a kind | Bomb}) = \frac{1}{103}

The number of hands containing two jokers (the other two cards are arbitrary) is given by: \begin{align*} \underbrace{{2 \choose 2}}_{\text{Two Jokers}} \cdot \underbrace{{52 \choose 2}}_{\text{Other Two Cards}} = \frac{52 \cdot 51}{2} = 1326. \end{align*} The number of hands that form four of a kind is 13, one for each of the 13 unique values in a deck.


For a bomb to occur, the four cards either contain two jokers or form four of a kind. Hence, \begin{align*} P(\text{Four of a kind | Bomb}) = \frac{13}{13 + 1326} = \frac{1}{103} \end{align*}



👋 Feedback: Find an error? Still confused? Have a suggestion? Let us know here.