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)!}\). (Note that order matters.)
e)
Subsets. The number of ways to choose a \(k\)-element subset of a set of \(n\) elements (where order does not matter) 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\).
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. \[ \begin {aligned}|{A \cup B}| &=|A| + |B| \\ &\quad - |A \cap B|.\\ &\\ |{A \cup B \cup C}| &=|A| + |B| + |C|\\ &\quad - |A \cap B| - |A \cap C| - |B \cap C| \\ &\quad + | A \cap B \cap C|\\ &\\ |{A \cup B \cup C\cup D}|& =|A| + |B| + |C| + |D|\\ &\quad - |A \cap B| - |A \cap C| - |A \cap D|- |B \cap C| - |B \cap D|- |C \cap D|\\ &\quad + | A \cap B \cap C| + | A \cap B \cap D|+ | A\cap C \cap D| + | B \cap C \cap D| \\ & \quad -| A \cap B \cap C \cap D| \end {aligned}\] and so on!
i)
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!}.\]

Plan for section

Administrivia + Introductions

Questions about material covered so far?

Problems to be covered in section

We may not get through all of these.

Be sure to check out all the remaining problems before you do your homework.

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.

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.

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:

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.

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.

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.

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.

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.

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.

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:

If we treat each of the E’s as different and each of the D’s as different, there are 9! ways to order the letters. But since the E’s (and respectively the D’s) are not actually distinguishable, given any particular one of the 9! orders we selected, permutations of the E’s within their assigned slots and permutations of the D’s within their assigned slots give the same outcome. Therefore we have overcounted by a factor of

2! ⋅2!.

Therefore the number of unique arrangements is \[ \boxed {\frac {9!}{2! \cdot 2!}} \]

A second way to see this is by considering following the sequence of choices: first choose where the E’s go (\(\binom {9}{2}\) choices), then where the D’s go (\(\binom {7}{2}\) choices), then where the rest go (\(5!\) choices). This gives \[\binom {9}{2}\binom {7}{2}\cdot 5! = \left (\frac {9!}{2!7!}\right ) \left (\frac {7!}{2!5!}\right ) \cdot 5! = \boxed {\frac {9!}{2! \cdot 2!}}\]

Thirdly, we can directly apply multinomial coefficients to account for indistinguishable arrangements of identical letters, and that gives us that 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!}} \]