CSE 312 – Section 1


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?
b)
…anyone can sit anywhere, except that one couple insists on not sitting in adjacent seats?

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?

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?

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?

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?

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?

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?

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?

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?

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?

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]\)?

12  Divide Me

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

a)
\(4\), \(6\), and \(9\)?
b)
\(4\), \(6\), or \(9\)?
c)
Neither \(4\), \(6\), nor \(9\)?

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 \}\}\)
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\)
c)
Is it always true that \(|A \setminus B| = |A| - |B|\)?

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?
b)
How many positive divisors does \(1440 = 2^5 3^2 5\) have?
c)
How many ways are there to arrange the CSE 311 staff on a line (11 TAs, two professors) for a group picture?
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?

15  Binomial Theorem

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

16  Multinomial Coefficients

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