CSE 312 – Section 1 Solutions

Spring 2026

Review

a): Sum rule. If you can choose from EITHER one of \(n\) options, OR one of \(m\) options with NO overlap with the previous \(n\), then the number of possible outcomes of the experiment is \(n + m\).
b): Product rule. In a sequential process with \(m\) steps, if there are \(n_1\) choices for the 1st step, \(n_2\) choices for the 2nd step (given the first choice), ..., and \(n_m\) choices for the \(m\)th step (given the previous choices), then the total number of outcomes is \(n_1n_2...n_m\).
c): Permutations. The number of ways to order \(n\) distinct elements is \(n!\).
d): \(k\)-permutations. The number of ways to choose a sequence of \(k\) distinct elements from a set of \(n\) elements is \(P(n,k) = \frac {n!}{(n-k)!}\).
e): Subsets. The number of ways to choose a \(k\)-element subset of a set of \(n\) elements is \(C(n,k) = \binom {n}{k} = \frac {n!}{k!(n-k)!}\).
f): Complementary counting. If \(S\) is a set and is the disjoint union of two sets \(A\) and \(B\), then you can find the size of \(A\) by finding the size of \(S\) and then subtracting the size of \(B\). The rest of these will be covered in class on January 5 or January 8.
g): Binomial theorem. \(\forall x,y \in \mathbb {R}, \forall n \in \mathbb {N}\): \((x+y)^n = \sum _{k=0}^n \binom {n}{k} x^k y^{n-k}\)
h): Inclusion-exclusion. \(|{A \cup B}| =|A| + |B| - |A \cap B|\).
i): Inclusion-exclusion. \(|{A \cup B \cup C}| =|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + | A \cap B \cap C|\).
j): Multinomial coefficients. Suppose there are \(n\) objects, but only \(k\) are distinct, with \(k \leq n\). (For example, “godoggy” has \(n=7\) objects (characters) but only \(k=4\) are distinct: \((g, o, d, y)\)). Let \(n_i\) be the number of times object \(i\) appears, for \(i \in \{1, 2, \ldots , k\}\). (For example, \((3,2,1,1)\), continuing the “godoggy” example.) The number of distinct ways to arrange the \(n\) objects is \(\binom {n}{n_1, ..., n_k} = \frac {n!}{n_1!\cdot ....\cdot n_k!}\).

1 Seating

How many ways are there to seat 10 people, consisting of 5 couples, in a row of 10 seats if …

a)

…all couples are to get adjacent seats?

We apply the Product Rule by breaking this into a sequence of choices.

Step 1: Consider each couple as a single unit. There are 5 units to arrange in a row, which can be done in \(5!\) ways.
Step 2: Within each of the 5 units, the couple can be seated in \(2! = 2\) ways (Person A on the left, or Person B on the left). For 5 couples, this gives \(2^5\) arrangements.

By the Product Rule, we multiply the choices: \( 5! \cdot 2^5\)

b)

…anyone can sit anywhere, except that one couple insists on not sitting in adjacent seats?

Method 1: Complementary Counting Let \(S\) be the set of unrestricted arrangements of the 10 people. \(|S| = 10!\). Let \(E\) be the set of arrangements where the specific couple IS sitting together. To find \(|E|\), treat the couple as a single unit. We now have 9 units to arrange (\(9!\) ways). Within their unit, the couple can sit in \(2!\) ways. By the Product Rule, \(|E| = 9! \cdot 2\). By Complementary Counting, the number of arrangements where they are NOT together is: \(10! - 9! \cdot 2 = 8 \cdot 9!\)

Method 2: Casework and the Sum Rule Let the couple be Person A and Person B. We use the Sum Rule across two disjoint cases based on where Person A sits:

Case 1: Person A sits on an end seat.
- Step 1: Choose an end seat for A (2 choices).
- Step 2: Choose a seat for B. B cannot sit next to A, leaving 8 choices.
- Step 3: Seat the remaining 8 people in the remaining 8 seats (\(8!\) choices).
By the Product Rule, there are \(2 \cdot 8 \cdot 8!\) ways for this case.
Case 2: Person A sits in a middle seat.
- Step 1: Choose a middle seat for A (8 choices).
- Step 2: Choose a seat for B. B cannot sit on either side of A, leaving 7 choices.
- Step 3: Seat the remaining 8 people (\(8!\) choices).
By the Product Rule, there are \(8 \cdot 7 \cdot 8!\) ways for this case.

By the Sum Rule, we add the cases together: \((2 \cdot 8 + 8 \cdot 7) \cdot 8! = 72 \cdot 8! = 8 \cdot 9!\)

2 Weird Card Game

In how many ways can a pack of \(52\) cards be dealt to \(13\) players, \(4\) to each, so that every player has \(1\) card of each suit?

We apply the Product Rule by dealing the cards one suit at a time.

Step 1: Deal the 13 hearts, one to each of the 13 players. There are \(13!\) ways to do this.
Step 2: Deal the 13 spades, one to each player (\(13!\) ways).
Step 3: Deal the 13 diamonds, one to each player (\(13!\) ways).
Step 4: Deal the 13 clubs, one to each player (\(13!\) ways).

By the Product Rule, we multiply the number of possibilities for each step: \((13!)^4\)

3 HBCDEFGA

How many ways are there to permute the 8 letters A, B, C, D, E, F, G, H so that A is not at the beginning and H is not at the end?

We will use the Principle of Inclusion-Exclusion (PIE) and Complementary Counting.

Let \(S\) be the set of all possible permutations of the 8 letters. Then \(|S| = 8!\).
Let \(E_A\) be the set of permutations where A is at the beginning. Then \(|E_A| = 7!\).
Let \(E_H\) be the set of permutations where H is at the end. Then \(|E_H| = 7!\).

Our goal is to compute \(|\overline {E_A \cup A_H}|\). By complementary counting, \[ |\overline {E_A \cup A_H}| = |S| - |E_A \cup A_H|\] and by PIE, \[|E_A \cup A_H| = |E_A| + |E_H| - |E_A \cap E_H|. \] Finally, since the intersection \(E_A \cap E_H\) represents permutations with A at the beginning AND H at the end, we have \(|E_A \cap E_H| = 6!\).

Putting it together, we have \[ |\overline {E_A \cup A_H}| = |S| - |E_A \cup A_H| = |S| - (|E_A| + |E_H| - |E_A \cap E_H|) = 8! - (2 \cdot 7! - 6!)\] So the answer is \(8! - (2 \cdot 7! - 6!)\)

4 Escape the Professor

There are \(6\) security professors and \(7\) theory professors taking part in an escape room. If \(4\) security professors and \(4\) theory professors are chosen and paired off, how many pairings are possible?

We apply the Product Rule in three steps:

Step 1: Choose 4 security professors out of 6. Order does not matter for selection, so there are \(\binom {6}{4}\) ways.
Step 2: Choose 4 theory professors out of 7. There are \(\binom {7}{4}\) ways.
Step 3: Pair the 4 selected theory professors with the 4 selected security professors. This can be done by choosing an order of the 4 theory professors to match with a fixed (arbitrary) line-up of security professors, which gives \(4!\) ways.

By the Product Rule, the total number of pairings is: \(\binom {6}{4}\binom {7}{4}4!\)

5 Birthday Cake

A chef is preparing desserts for the week, starting on a Sunday. On each day, only one of five desserts (apple pie, cherry pie, strawberry pie, pineapple pie, and cake) may be served. On Thursday there is a birthday, so cake must be served that day. On no two consecutive days can the chef serve the same dessert. How many dessert menus are there for the week?

We apply the Product Rule, starting from the most restricted day (Thursday) and working outwards.

Step 1: Choose Thursday’s dessert. It must be cake, so there is \(1\) choice.
Step 2: Choose Wednesday’s dessert. It cannot be cake, leaving \(4\) choices.
Step 3: Choose Tuesday’s dessert. It cannot be Wednesday’s dessert, leaving \(4\) choices.
Step 4: Choose Monday’s dessert. It cannot be Tuesday’s dessert, leaving \(4\) choices.
Step 5: Choose Sunday’s dessert. It cannot be Monday’s dessert, leaving \(4\) choices.
Step 6: Choose Friday’s dessert. It cannot be Thursday’s cake, leaving \(4\) choices.
Step 7: Choose Saturday’s dessert. It cannot be Friday’s dessert, leaving \(4\) choices.

By the Product Rule, we multiply the choices together: \(4 \cdot 4 \cdot 4 \cdot 4 \cdot 1 \cdot 4 \cdot 4 =\) \(4^6\)

6 Full Class

There are 40 seats and 40 students in a classroom. Suppose that the front row contains 10 seats, and there are 5 students who must sit in the front row in order to see the board clearly. How many seating arrangements are possible with this restriction?

We use the Product Rule.

Step 1: Select 5 seats from the 10 available in the front row for the 5 specific students (\(\binom {10}{5}\) choices).
Step 2: Arrange those 5 specific students into those 5 chosen seats (\(5!\) ways).
Step 3: Arrange the remaining 35 students into the remaining 35 seats anywhere in the classroom (\(35!\) ways).

By the Product Rule, the total number of seating arrangements is: \(\binom {10}{5}\cdot 5! \cdot 35!\)

7 Paired Finals

Suppose you are to take a CSE 312 final in pairs. There are \(100\) students in the class and \(8\) TAs, so \(8\) lucky students will get to pair up with a TA. Each TA must take the exam with some student, but two TAs cannot take the exam together. How many ways can they pair up?

We apply the Product Rule by breaking the pairing process into two sequential steps.

Step 1: Assign students to TAs. First, choose the 8 students who will pair with the TAs. There are \(\binom {100}{8}\) ways to choose them. Next, pair these 8 students with the 8 distinct TAs. There are \(8!\) ways to arrange these pairings. (For example, consider the TAs in alphabetic order, then choose a student to match with the first, then one of the remaining to match with the second and so on.)
Step 2: Pair up the remaining 92 students. Consider an alphabetic ordering of the students. Pick the first in the order.They have \(91\) choices for a partner. Take the next remaining student from the alphabetical ordering. They have \(89\) choices for a partner. Continue this process. The total number of ways to pair the remaining students is \(91 \cdot 89 \cdot 87 \cdots 3 \cdot 1\).

By the Product Rule, we multiply the number of choices for each step: \(\binom {100}{8} \cdot 8! \cdot 91 \cdot 89 \cdots 3 \cdot 1\) Check using the Sleuth’s Criterion!

8 Photographs

Suppose that \(8\) people, including you and a friend, line up for a picture. In how many ways can the photographer organize the line if she wants to have fewer than \(2\) people between you and your friend?

We use the Sum Rule across two disjoint cases: 0 people between you (adjacent), or exactly 1 person between you.

Case 1: 0 people between you. Treat you and your friend as a single "unit". There are now 7 units to arrange (\(7!\) ways). Within the unit, you and your friend can be arranged in 2 ways. By the Product Rule, there are \(7! \cdot 2\) ways for this case.
Case 2: Exactly 1 person between you.
- Step 1: Choose the 1 person to stand between you out of the 6 other people (6 choices).
- Step 2: Treat the trio (you, the middle person, your friend) as a single "unit". There are now 6 units to arrange (the trio + the remaining 5 people), giving \(6!\) ways.
- Step 3: Choose which of you and your friend is the left versus the right end of the trio (2 ways).
By the Product Rule, there are \(6 \cdot 6! \cdot 2\) ways for this case.

By the Sum Rule, we add the disjoint cases together: \((7! \cdot 2) + (6 \cdot 6! \cdot 2) = (14 \cdot 6!) + (12 \cdot 6!) = \) \(26 \cdot 6!\)

9 Rabbits!

Rabbits Peter and Pauline have three offspring: Flopsie, Mopsie, and Cotton-tail. These five rabbits are to be distributed to four different pet stores so that no store gets both a parent and a child. It is not required that every store gets a rabbit. In how many different ways can this be done?

We use the Sum Rule based on two disjoint cases regarding the parents’ placement.

Case 1: Peter and Pauline go to the same store.
- Step 1: Choose the store for the parents (4 choices).
- Step 2: Place the 3 offspring. Because they cannot be in the parent store, each offspring has 3 store choices. By the Product Rule, there are \(3^3\) ways.
Total for Case 1: \(4 \cdot 3^3\).
Case 2: Peter and Pauline go to different stores.
- Step 1: Choose 2 distinct stores for the parents. Since order matters (Peter’s store vs Pauline’s store), there are \(P(4,2) = 4 \cdot 3 = 12\) choices.
- Step 2: Place the 3 offspring. Because they cannot be in either of the two parent stores, each offspring has 2 store choices. By the Product Rule, there are \(2^3\) ways.
Total for Case 2: \(12 \cdot 2^3\).

Using the Sum Rule, we add the cases together: \(4 \cdot 3^3 + 12 \cdot 2^3\)

10 Extended Family Portrait

A group of \(n\) families, each with \(m\) members, are to be lined up for a photograph. In how many ways can the \(nm\) people be arranged if members of a family must stay together?

We apply the Product Rule.

Step 1: Treat each family as a single block. Order the \(n\) family blocks in the line. There are \(n!\) ways to do this.
Step 2: Within each family block, order the \(m\) members. Each family can be ordered in \(m!\) ways. Since there are \(n\) families, this gives \((m!)^n\) possible arrangements.

By the Product Rule, the total number of arrangements is: \(n!(m!)^n\)

11 Subsubset

Let \([n]=\{1,2,...,n\}\) denote the first \(n\) natural numbers. How many (ordered) pairs of subsets \((A,B)\) are there such that \(A\subseteq B\subseteq [n]\)?

There are two distinct methods to solve this question:

Method 1: Sum Rule and Product Rule We sum over all possible sizes of subset \(B\), from \(k=0\) to \(k=n\). For a specific size \(k\), we first choose the \(k\) elements for \(B\) (\(\binom {n}{k}\) ways). Then, since \(A \subseteq B\), every element in \(B\) can independently either be in \(A\) or not in \(A\) (\(2^k\) ways). By the Sum Rule, we add the possibilities for all \(k\): \[\sum _{k=0}^n{\binom {n}{k}2^k}=\sum _{k=0}^n{\binom {n}{k}2^k1^{n-k}}= 3^n, \] where in the final step, we applied the Binomial Theore).

Method 2: Product Rule on Elements Consider each element \(i \in \{1,...,n\}\) independently. A priori are four logical possibilities for an element: 1) In \(A\) only. 2) In \(B\) only. 3) In both \(A\) and \(B\). 4) In neither \(A\) nor \(B\). Because we require \(A \subseteq B\), the condition "In \(A\) only" (which means \(A\) but not \(B\)) is invalid. This leaves exactly 3 valid choices for each of the \(n\) elements. By the Product Rule, multiplying the 3 choices across all \(n\) elements yields: \(3^n\)

12 Divide Me

How many numbers in \([360]\) are divisible by:

a): \(4\), \(6\), and \(9\)?
To be divisible by 4, 6, AND 9, a number must be a multiple of their least common multiple (LCM). \(\text {lcm}(4,6,9)=36\). There are \(\frac {360}{36}=10\) such multiples in the range \([360]\).
b): \(4\), \(6\), or \(9\)?
Let \(A_k\) denote the set of numbers in \([360]\) divisible by \(k\). We want to find \(|A_4 \cup A_6 \cup A_9|\). We use the Principle of Inclusion-Exclusion (PIE): \[|A_4 \cup A_6 \cup A_9| = |A_4| + |A_6| + |A_9| - |A_4 \cap A_6| - |A_4 \cap A_9| - |A_6 \cap A_9| + |A_4 \cap A_6 \cap A_9|\] Recall that the intersection of two sets of multiples is the set of multiples of their LCM. Applying this: \(\frac {360}{4}+\frac {360}{6}+\frac {360}{9}-\frac {360}{\text {lcm}(4,6)}-\frac {360}{\text {lcm}(4,9)}-\frac {360}{\text {lcm}(6,9)}+\frac {360}{\text {lcm}(4,6,9)}\).
c): Neither \(4\), \(6\), nor \(9\)?
We use Complementary Counting. The total number of integers is \(360\). We want the numbers that are NOT divisible by 4, 6, or 9. We subtract the answer from part (b) (the numbers that ARE divisible by at least one of them) from the total: \(360 - \text {Answer to (b)}\)

13 Practice with Sets

a)

For each one of the following sets, give its cardinality, i.e., indicate how many elements it contains:

\(A = \emptyset \)
\(B = \{\emptyset \}\)
\(C = \{\{\emptyset \}\}\)
\(D = \{\emptyset , \{\emptyset \}\}\)

\(|A|= 0\) (The empty set contains no elements).
\(|B|= 1\) (The set contains one element: the empty set).
\(|C|= 1\) (The set contains one element: a set containing the empty set).
\(|D| = 2\) (The set contains two distinct elements: the empty set, and a set containing the empty set).

b)

Let \(S = \{a, b, c\}\) and \(T = \{c, d\}\). Compute:

\(S \cup T\)
\(S \cap T\)
\(S \setminus T\)
\(2^{S\setminus T}\)
\(S\times T\)

\(S \cup T = \{a,b,c,d\}\) (Elements in \(S\) OR \(T\) OR both).
\(S \cap T = \{c\}\) (Elements in both \(S\) AND \(T\)).
\(S \setminus T = \{a,b\}\) (Elements in \(S\) that are NOT in \(T\)).
\(2^{S\setminus T} = \{\emptyset , \{a\}, \{b\}, \{a,b\}\}\) (The power set: all possible subsets of \(\{a,b\}\)).
\(S\times T = \{(a,c),(a,d),(b,c),(b,d),(c,c),(c,d)\}\) (The Cartesian product: all ordered pairs where the first element is from \(S\) and the second is from \(T\)).

c)

Is it always true that \(|A \setminus B| = |A| - |B|\)?

No. Here is a counterexample. Let \(A = \emptyset \) and \(B = \{1\}\). \(|A \setminus B| = 0\), whereas \(|A| - |B| = 0 - 1 = -1\). Cardinality must be non-negative.

14 Basic Counting

a)

Credit-card numbers are made of 15 decimal digits, and a 16th checksum digit (which is uniquely determined by the first 15 digits). How many credit-card numbers are there?

We use the Product Rule.

Step 1: Choose the first 15 digits. Each decimal digit has 10 options (0-9), giving \(10^{15}\) possibilities.
Step 2: Choose the 16th digit. Since it is uniquely determined by the first 15, there is only 1 option.

By the Product Rule: \(10^{15} \cdot 1 = 10^{15}\)

b)

How many positive divisors does \(1440 = 2^5 3^2 5\) have?

We use the Product Rule. Every positive divisor of \(1440\) can be uniquely written as a product of primes \(2^i 3^j 5^k\), where \(i\), \(j\), and \(k\) are bounded by the powers in the factorization of 1440.

Step 1: Choose the power \(i \in \{0, 1, 2, 3, 4, 5\}\) (6 options).
Step 2: Choose the power \(j \in \{0, 1, 2\}\) (3 options).
Step 3: Choose the power \(k \in \{0, 1\}\) (2 options).

By the Product Rule, we multiply the choices: \(6 \cdot 3 \cdot 2 = 36\)

c)

How many ways are there to arrange the CSE 311 staff on a line (11 TAs, two professors) for a group picture?

There are \(11 + 2 = 13\) people total. We want to arrange all 13 distinct people in a single sequence. This is just a standard permutation: \(13!\)

d)

How many ways are there to arrange the CSE 311 staff on a line so that Professors Tessaro and Beame are at the two ends of the line?

We use the Product Rule.

Step 1: Place the two professors at the two ends of the line. There are \(2! = 2\) ways to do this (Tessaro on left/Beame on right, or vice versa).
Step 2: Arrange the 11 TAs in the remaining 11 middle spots. There are \(11!\) ways to do this.

By the Product Rule: \(2 \cdot 11!\)

15 Binomial Theorem

What is the coefficient of \(z^{36}\) in \((-2x^2yz^3+5uv)^{312}\)?

By the Binomial Theorem: \[(A+B)^n = \sum _{k=0}^{n}\binom {n}{k} A^k B^{n-k}\] Letting \(A = -2x^2yz^3\), \(B = 5uv\), and \(n = 312\): \[(-2x^2yz^3+5uv)^{312} = \sum _{k=0}^{312}\binom {312 }{ k} (-2x^2yz^3)^k (5uv)^{312-k}\] \[= \sum _{k=0}^{312} \binom {312 }{ k}(-2)^k x^{2k} y^k z^{3k} (5uv)^{312-k}\] We want the coefficient of the term containing \(z^{36}\). Looking at the exponent of \(z\), we set \(3k = 36\), which means \(k=12\). Plugging in \(k=12\), the specific term is: \(\binom {312}{12} (-2)^{12} x^{24} y^{12} z^{36} (5uv)^{300}\) Therefore, the coefficient (the entire multiplier of \(z^{36}\)) is: \(\binom {312}{12}(-2x^2y)^{12}(5uv)^{300}\)

16 Multinomial Coefficients

How many ways can we arrange the letters in ‘TEDDYBEAR’?

There are \(n=9\) total letters in the word. Let’s count the frequencies of each distinct letter: E appears 2 times (\(n_1 = 2\)). D appears 2 times (\(n_2 = 2\)). T, Y, B, A, R each appear 1 time (\(n_3, \dots , n_7 = 1\)). Using multinomial coefficients to account for indistinguishable arrangements of identical letters, the number of unique arrangements is: \[ \binom {9}{2,2,1,1,1,1,1} = \frac {9!}{2! \cdot 2! \cdot 1! \cdot 1! \cdot 1! \cdot 1! \cdot 1!} = \boxed {\frac {9!}{2! \cdot 2!}} \]