Section 1: Counting and Enumeration

1.1: The Basics

Permutations

A permutation on an $n$ -element set is an arrangement of the elements in a specific order. A $k$ -permutation is an arragement of $k$ elements from the set.

We assume that all elements are distinct, by property of sets.

The total number of $k$ -permutations on an $n$ element set is given as

P (n, k) = \frac{n !}{( n - k )!} = n (n - 1) \dots (n - k + 1)

This is also known as the $k^{t h}$ falling factorial of $n$ . Let $n \geq k$ be positive integers. Then, the $k^{t h}$ falling factorial is given as

(n)_{k} = n (n - 1) \dots (n - k + 1)

Example: Permutations with Repetition

How many rearrangements of $AAAA B C D E E E$ are there?

Note the repetition. If they were all distinct, we would have $10!$ combinations!

If we treat our $A$ ‘s as 4 distinct letters, there are $4! = 24$ ways to permute them. Similarly, for $E$ , there are $3! = 6$ ways to permute them. These cases should only be counted one in the original question, so we need to divide them out.

So, we find that our answer is
$\frac{10 !}{4 ! \cdot 3 !}$

This result (and intuition) can be generalized to a theorem.

Theorem: Multinomial Coefficient

Suppose object 1 occurs $a_{1}$ times, object 2 occurs $a_{2}$ times, $\dots$ object k occurs $a_{k}$ times, to give us $n = a_{1} + a_{2} + \dots a_{k}$ objects.

Then, the total number of arrangements of the $n$ objects is
$\frac{n !}{a _{1} ! a _{2} ! \dots a _{k} !} = (a _{1} a _{2} \dots a _{k} n)$
Called the multinomial coefficient.

Combinations

The total number of ways to create a $k$ -element subset from $[n] = {1, 2, \dots n}$ , n choose k, is denoted

(k n) = C (n, k) = \frac{n !}{k ! ( n - k )!}

and called a combination of binomial coefficient.

Note that this is essentially a permutation without the ordering! This is why we divide by $k!$ - we’re removing all cases that have the same ordering!

Example: Combinations

There are 5 cats, 4 dogs, 5 mice. Three are chosen.

What are the total ways to get exactly 2 cats, 1 dog? Well, out of our 5 cats we choose 2, and out of our 4 dogs we choose 1! This gives us
$(2 5) (1 4)$
What are the total ways to get at least 1 cat (3 animals total)? Note that in this case, we can’t simply do $(1 5) (2 13)$ , as this double counts some cases! Instead, we want to make our cases mutually exclusive.

First, say we choose 1 cat. We have $(1 5) (2 9)$ options (choose 2 from the other non-cats to make 3).

Next, say we choose 2 cats. We have $(2 5) (1 9)$ options (choose 1 from the other non-cats to make 3).

Finally, say we choose 3 cats. We have $(3 5)$ options.
This gives us

$(1 5) (2 9) + (2 5) (1 9) + (3 5)$
options.

Binomial Theorem

For a positive integer $n$ , we have
$(x + y)^{n} = k = 0 \sum n (k n) x^{k} y^{n - k}$

The proof for above is omitted. However, intuitively, you can think of it as expanding $(x + y)^{n} = (x + y) (x + y) \dots$

Then, for any $x^{k} y^{n - k}$ , we can find its coefficient by choosing $k$ $(x + y)$ terms to contribute to the x, and choosing the remaining $n - k$ terms to contribute to the way. We find all ways we can do this (leading to the binomial coefficient you see!)

Example: Binomial Theorem Intuition, Extended

Suppose we are interested in the coefficient of $x_{1}^{3} x_{3} x_{4}$ from $(x_{1} + x_{2} + x_{3} + x_{4})^{5}$ !

Well, of the 5 $(x_{1} + x_{2} + x_{3} + x_{4})$ terms, we choose 3 to multiply the $x_{1}$ , 1 to multiply the $x_{3}$ , and 1 to multiply the $x_{4}$ . This gives us
$(3 5) (1 2) (1 1)$

This is essentially permutations with repetition!

Multinomial Theorem

$(x_{1} + \dots x_{k})^{n} = a_{1} + a_{2} + \dots a_{k} = n \sum (a _{1} a _{2} \dots a _{k} n) x_{1}^{a_{1}} x_{2}^{a_{2}} \dots x_{k}^{a_{k}}$

1.2: Counting in Two Ways

Many combinatorial identities can be interpreted in multiple ways.

For example, consider

(k - 1 n - 1) + (k n - 1) = (k n)

This describes the same count, but we can see it in 2 different ways!

The right hand side describes the number of ways to create a $k$ -size subset from $[n]$ .
The left hand side describes $k$ -size subsets that do or do not contain element $n$ .
- If we do contain $n$ , then we choose $k - 1$ elements from the remaining $n - 1$ elements. $(k - 1 n - 1)$
- If we do not contain $n$ , then we choose $k$ elements from the remaining $n - 1$ elements. $(k n - 1)$

Another example:

k = 0 \sum n k (k n) = n 2^{n - 1}

This describes the total number of possible ways we can form a team with a leader among $n$ people.

In the right hand side, we choose a leader from a group of $n$ people, and for the remaining people, they choose to “include” or “not include” them in the team.
In the left hand side, we choose a team of $k$ people from $n$ total ( $0 \leq k \leq n$ ), and among those $k$ people, choose a leader.

Another example:

i = 1 \sum n i (n - i + 1) = (3 n + 2)

In the RHS, we describe all ways to create a 3-size subset from $[n + 2]$ .
In the LHS, let ${a, b, c} \in [n + 2]$ . We assign all of the elements to $a$ , $b$ , or $c$ , and find the number of ways we can create a 3-size subset, choosing 1 from each ${a, b, c}$ . First, let the first $i$ elements be in $a$ . Then, let the next element be in $b$ , and let the remaining be in $c$ . Choose 1 from each group $a, b, c$ , and find the number of ways we can do this. Thus, for any iteration, we have $i$ choices for $a$ , 1 choice for $b$ , and $n + 2 - i - 1$ choices for $c$ .

1.3: Pigeonhole Principle

In its simplest form, the Pigeonhole Principle states that if $n + 1$ pigeons into $n$ pigeonholes, there exists at least 1 pigeonhole with at least 2 pigeons. This is because you can fill in $n$ holes with 1 pigeon each, and are left with one extra pigeon that must go with one of the already filled holes.

More generally, if we have $n$ pigeons and $k$ pigeonholes, there exists a pigeonhole with at least $⌈ \frac{n}{k} ⌉$ pigeons (or, more than $⌊ \frac{n - 1}{k} ⌋$ pigeons).

Example: Pigeonhole Principle

Prove that in a group of 40 poeple, at least 4 people have a birthday in the same month.

Here, let pigeons be people, and pigeonholes be months. We have 12 pigeonholes, and 40 pigeons.

By the pigeonhole principle, there exists at least 1 month with at least $⌈ \frac{40}{12} ⌉ = 4$ people.

Example: Pigeonhole Principle (2)

Prove that if 6 distinct numbers are chosen from $[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9}$ , then two of the numbers will sum to 10.

Here, let pigeonholes be pairs of numbers summing to 10: ${1, 9}, {2, 8}, {3, 7}, {4, 6}, {5}$ , and let pigeons be our “choice” of number in our 6-number set.

By the pigeonhole principle, there exists at least 1 pair with at least $⌈ \frac{6}{5} ⌉ = 2$ choices, i.e. both numbers in the pair are selected. Note that we cannot have chosen ${5}$ twice, as the numbers are distinct.

Example: Pigeonhole Principle (3)

An athlete works out in blocks of hours. He plans to work out a total of 45 hours in a 30-day month. Assume he works out at least 1 hour each day. Prove that there is a period of consecutive days (2 or more) where the cumulative hours he has worked out is a total of exactly 14 hours.

Let $a_{i}$ be the accumulated hours up to the day $i$ . This gives us the sequence $a_{1}, a_{2}, \dots a_{30} = 45$ . Because we are doing at least 1 hour a day, this is a strictly increasing sequence- each number is distinct.

Consider the sequence $b_{1} = a_{1} + 14, b_{2} = a_{2} + 14, \dots b_{30} = a_{30} + 14$ . Note that the $b_{i}$ ‘s are distinct by our earlier assumption. We know that because $a_{30} = 45$ , $b_{30} = 45 + 14 = 59$ .

We find that our sequences ${a_{i}}, {b_{i}}$ take on at most 59 different values, but there are 60 total values, with $a_{i}$ ‘s and $b_{i}$ ‘s distinct! Thus, letting the $a_{i}$ ‘s and $b_{i}$ ‘s be pigeons, 1 - 60 be pigeonholes, by the pigeonhole principle, there must exist some value where the sequences overlap- $a_{j} = b_{k} = a_{k} + 14$ .

So, $a_{j} - a_{k} = 14$ - in other ways, from day $k$ to $j$ , the athlete worked out exactly 14 hours.

1.4: Compositions and Set Partitions

Compositions

Let $a_{1}, \dots a_{k}$ be non-negative integers such that

i = 1 \sum k a_{i} = n

Then the ordered $k$ -tuple $(a_{1}, \dots a_{k})$ is a weak composition of $n$ into $k$ parts.

This can be seen as a way to give $n$ dollars to $k$ people, where some people may get none!

How many weak compositions of $n$ into $k$ are possible?

Theorem: Stars and Bars

There are
$(k - 1 n + k - 1)$
Possible weak compositions of $n$ into $k$ .

Proof

Consider $n$ stars, and $k$ bars. We define a model where all stars to the right of the first bar (before the second bar) is the value of $a_{1}$ , all stars to the right of the second (before the third) is the value of $a_{2}$ , and so on and so forth for $a_{3}, \dots a_{k}$ .
$∣ ⋆ ⋆ ⋆ ∣ ⋆ ∣ ⋆ ⋆ \dots$
Observe that the first object must be a bar. This leaves $n + k - 1$ objects that are not used. However we choose to place the remaining $k - 1$ bars gives us a unique weak composition of $n$ into $k$ parts! So, we have
$(k - 1 n + k - 1)$
Possible compositions.

Example: Stars and Bars

How many non-negative integer solutions are there to $x_{1} + x_{2} + x_{3} = 12$ ?

By the theorem, we have
$(3 - 1 12 + 3 - 1) = (2 14)$

Example: Stars and Bars (2)

There are 5 cokes, 7 sprites, and 6 Dr. Peppers. How many ways can we choose 4 sodas?

We can see this as $x_{1}$ being cokes, $x_{2}$ being sprites, $x_{3}$ being Dr. Peppers, and rephrase the problem as
$x_{1} + x_{2} + x_{3} = 4$
Finding the total number of non-negative integer solutions.
$(3 - 1 4 + 3 - 1)$

What if a weak composition $(a_{1}, a_{2}, \dots a_{k})$ requires $a_{1}, a_{2}, \dots a_{k} \geq 1$ ? Well, we can simply give each $a_{1}, \dots a_{k}$ 1, and then perform a weak composition on the $n - k$ remaining! This way, it doesn’t matter if the weak composition yields that someone got nothing, as they already have at least 1. We formalize this below.

The total $k$ -tuples $(a_{1}, \dots a_{k})$ satisfying $\sum_{i = 1}^{k} a_{i} = n$ , where each $a_{i}$ is a positive integer ( $a_{i} \geq 1$ ) is

(k - 1 n - k + k - 1) = (k - 1 n - 1)

Called a composition of $n$ into $k$ parts.

Partitions

Let $X$ be a finite set, and $A_{1}, A_{2}, \dots A_{k}$ be non-empty subsets of $X$ . A partition of $X$ ${A_{1}, \dots A_{k}}$ satisfies the following:

$i = 1 ⋃ k A_{i} = x$
Their union makes up $X$
$A_{i} \cap A_{j} = \emptyset \forall1 \leq i \neq = j \leq k$
The subsets are disjoint.

For a given $k$ , we say $X$ is partitioned into $k$ blocks.

Example: Partitions

Let $X = [3]$ .

We have 5 possible partitions:
${1, 2, 3} {1, 2}, {3} {1, 3}, {2} {2, 3}, {1} {1}, {2}, {3}$
Above, you can see that there are 3 cases of “2 blocks”.

A Stirling number of the second kind, denoted $S (n, k)$ is the total number of partitions of $[n]$ into exactly $k$ blocks. By convention, $S (0, 0) = 1$ .

There’s no easy formula for all $S (n, k)$ ! However, we have some formulas for subsets of the stirling numbers.

Example: Stirling Numbers

What is $S (n, 2)$ ?

For $n$ , assign each number to 1 of 2 teams: $2^{n}$ . Subtract the cases where all are only in 1 team: $2$ .

Finally, divide by 2 because sets have no ordering.
$\frac{2 ^{n} - 2}{2} = 2^{n - 1} - 1$

Theorem: Stirling Numbers (Recurrence Relation)

For all non-negative integers $n \geq k$ ,
$S (n, k) = S (n - 1, k - 1) + k S (n - 1, k)$

Proof

The LHS is the total number of partitions of $[n]$ into exactly $k$ blocks.

In the RHS, we consider partitions of $n$ where element “n” is a singleton block or not. If it is a singleton block, then we find the remaining $k - 1$ blocks from the $n - 1$ remaining. If it is not a singleton block, then we can create $k$ blocks from $n - 1$ , and then put $n$ in any of the $k$ blocks ( $k$ choices).

Theorem: Stirling Numbers (Summation)

We have
$S (n, k) = \frac{1}{k !} i = 0 \sum k (- 1)^{i} (i k) (k - i)^{n}$

The proof will be covered later!

What if we didn’t want to be limited by $k$ blocks?

The total number of partitions of $[n]$ into any # of blocks is the Bell number, denoted $B (n)$ . By convention, $B (0) = 1$ .

Example: Bell Numbers

From an earlier example, let $X = [3]$ .

We have 5 possible partitions:
${1, 2, 3} {1, 2}, {3} {1, 3}, {2} {2, 3}, {1} {1}, {2}, {3}$
So, $B (3) = 5$ .

Theorem: Bell Numbers (Summation)

We have
$B (n) = i = 1 \sum n (i - 1 n - 1) B (n - i)$

Proof

The LHS describes all ways to partition $[n]$ .

In the RHS, we look at partitions depending on some element “n”, lying in a subset of size $i$ .

First, create one subset of size $1 + (i - 1)$ (1 element is always taken out before the choosing, hence the -1). Then, of the remaining $n - i$ elements, we find the number of ways to partition it.

Example: Partitions

Let $f : A \to B, ∣ A ∣ = n, ∣ B ∣ = k$ .

Recall that $f$ is surjective / onto if for every $b \in B$ , there exists an $a \in A$ such that $f (a) = b$ .

How many surjective functions are there?

Here, we want to partition our domain values into $k$ blocks, where each block will be associated with one output. We multiply by $k!$ , the total number of ways to associate one combination of blocks with the outputs.

1.5: Integer Partitions

A partition of integer $n$ is a positive sequence of integers $a_{1}, a_{2}, \dots a_{k}$ , where $a_{1} \geq a_{2} \geq \dots \geq a_{k}$ , such that

a_{1} + a_{2} + \dots + a_{k} = n

So, $1 + 3$ is the same as $3 + 1$ . What matters is not what’s inside of the blocks, but the sizes of the blocks relative to one another!

We denote the total number of partitions of $n$ by $p (n)$ . By convention, $p (0) = 1$ .

The formula for this is extremely complex!

Example: $n = 4$ Case

We find that
$3 + 1 = 2 + 2 = 2 + 1 = 1 + 1 + 1 + 1 = 4$
There are 5 total partitions of 4! $p (4) = 5$ .

A Ferrers diagram (or Young Diagram) of an integer partition is a partial rectangular grid whose $i^{t h}$ row contains $a_{i}$ dots (rectangles).

These diagrams can illustrate some very interesting relationships! One diagram representing $4 + 3 + 1 + 1 + 1$ is given below.

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆

Interestingly, the conjugate of a partition on a diagram is a new grid whose $i^{t h}$ column is now $a_{i}$ . Here, the conjugate would yield

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆

Basically, we flip the entire thing along a diagonal!

We can use this to establish some interesting identities!

Theorem: Integer Partitions Identity

The total number of integer partitions of $n$ such that $a_{1} = a_{2} \geq a_{3} \geq \dots$ equals the total number satisfying
$a_{1} \geq a_{2} \geq \dots \geq 2$

Each partition has a size of at least 2!

Proof

Consider a partition such that $a_{1} = a_{2}$ .

If we were to draw a Ferrers diagram, we would find that the conjugate of the diagram corresponds to a diagram whose first two columns are always the same length, telling us that there are at least two dots in each row.
$⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ a_{1} a_{2} ⟹ ⋆ ⋆ ⋆ ⋆ ⋆ a_{1} ⋆ ⋆ ⋆ ⋆ ⋆ a_{2} ⋆ ⋆ ⋆ ⋆$
Thus, each $a_{i}$ must take on at least 2.

The converse also holds, with a similar proof.

The total partitions of $n$ into exactly $k$ parts is denoted $P_{k} (n)$ .

Note that the previous definition did not establish this $k$ part requirement.

Theorem: Integer Partitions into Exactly $k$ Parts

For $1 < k < n$ ,
$P_{k} (n) = P_{k - 1} (n - 1) + P_{k} (n - k)$

Proof

The LHS describes the ways to partition $n$ into exactly $k$ parts.

The RHS considers partitions into $k$ parts for either $a_{k} = 1$ or $a_{k} > 1$ . If $a_{k} = 1$ , we take one and partition the remaining $n - 1$ into $k - 1$ parts for a total of $k$ . If $a_{k} > 1$ , we first give 1 to all parts, then partition the remaining into $k$ parts to guarantee that all numbers have at least 2.

1.6: The Twelvefold Way

We throw $n$ balls into $k$ bins. We consider the cases of the balls and bins being labeled (distinguishable) or not, and if each bin has no restriction, each bin has at least 1 ball, or each bin has at most 1 ball.

This forms 12 cases total, which can be solved with the methods described previously.

Labeled balls to labeled bins
1. No restriction: For every ball, we can put it in $k$ possible bins.
$k^{n}$
1. At least 1 ball: We find the number of ways to partition $n$ into $k$ , and then permute what bin each group goes into.
$k! S (n, k)$
1. At most 1 ball (obvioulsly, $k \leq n$ ): Choose $n$ of the $k$ bins to place the balls into. Then, permute the ordering of how we place the balls.
$(n k) n!$
Unlabeled balls to labeled bins
1. No restriction: Perform weak composition to decompose $n$ into $k$ (labeled) parts.
$(k - 1 n + k - 1)$
1. At least 1 ball: First give each bin 1 dollar, then perform weak composition on the remaining $n - k$ parts.
$(k - 1 n - 1)$
1. At most 1 ball: Choose $n$ bins of the $k$ to place a ball into.
$(n k)$
Labeled balls to unlabeled bins.
1. No restriction: We partition the set of balls $[n]$ into $i$ , from $1 \leq i \leq k$ . We do a sum instead of Bell numbers, as bell numbers will overcount (we cannot count higher than $k$ ).
$i = 1 \sum k S (n, i)$
1. At least 1 ball: We partition the set of balls $[n]$ into $k$ parts.
$S (n, k)$
1. At most 1 ball: Just one way, as the bins are labeled!
$1$
Unlabeled balls to unlabeled bins.
1. No restriction: Some bins can be empty, so this is integer partitions into 1 bin, then 2 bins, and so forth until $k$ bins. Simple integer partitions assume the integers (bins) can never be empty, which is not true here.
$P_{1} (n) + P_{2} (n) + \dots + P_{k} (n)$
1. At least 1 ball: Each bin must have at least 1 ball, so this is integer partitions into $k$ parts.
$P_{k} (n)$
1. At most 1 ball: If $n \leq k$ , since nothing is labeled, we’ll just have $k$ bins filled with 1 ball. So, there is only 1 way.
$1$

Examples: The Twelvefold Way

A multiset is a set such that elements can be repeated. How many multisets of size 5 can be created using $[7] = {1, 2, \dots, 7}$ ?

We can convert this into one of the 12 ways. Consider 5 unlabeled balls to 7 labeled bins. Each ball is used as a counter to how many times the element occurs in the multiset.
$(7 - 1 5 + 7 - 1)$

Twenty students split into exactly 4 study groups to prepare for an exam (groups with 1 person are fine). However, brothers Bobs and Carl must be in the same group. Also, sisters Alice and Diane want to be in the same group. What are the possible number of groups?

First, as Bob / Carl, Alice / Diane must always be together, let’s group them into 1 entity each. So, we have 18 labeled balls into 4 unlabeled boxes, where each box must have at least 1 ball.
$S (18, 4)$

How many injective / one-to-one functions are there for $f : [n] \to [k]$ ?

For each element in our range, we know that there is at most 1 value in our domain mapping to it. This is the same as $n$ labeled bins, $k$ labeled balls, where each bin can only have at most 1 ball.
$(k)_{n} = k (k - 1) \dots (k - n + 1)$

Let $n \geq k$ . A function $f : [n] \to [k]$ is monotone if $f (x) \geq f (y)$ whenever $x > y$ . How many monotonic functions $f : [n] \to [k]$ are there?

Let us have $k$ labeled bins for the output, and $n$ unlabeled balls for the domain values. Note that these can be unlabeled, as the monotone constraint forces an order (the $i$ balls in bin 1 must correspond to the first $i$ values in the domain, and so forth). This is weak compositions! Thus, we have
$(k - 1 n + k - 1)$

1.7: Inclusion-Exclusion Principle

Theorem

Let $A_{1}, \dots A_{n} \subseteq X$ , where $X$ is finite. Assume that the $A_{i}$ ‘s are non-empty.

Let $I \subseteq [n]$ , and denote $A_{I} = ⋂_{i \in I} A_{i}$ . Define $A_{\emptyset} = X$ .

Then,
$i = 1 ⋃ n A_{i} = ∣ X ∣ - I \subseteq [n] \sum (- 1)^{∣ I ∣} ∣ A_{I} ∣$
In other words, the union of all sets is the set minus the intersection of all subset combinations.

Applying Demorgan’s Law on this, we obtain
$i = 1 ⋂ n \overset{ˉ}{A}_{i} = I \subseteq [n] \sum (- 1)^{∣ I ∣} ∣ A_{I} ∣$
Where $\overset{ˉ}{A}_{i}$ is the complement of $A_{i}$ .

Basically, sometimes when we want to find something, we can find it by considering its complements (which can be easer to solve)!

Example: $n = 2$ Case

In the $n = 2$ case, we have
$i = 1 ⋃ 2 A_{i} = ∣ A_{1} \cup A_{2} ∣ = ∣ X ∣ - ((- 1)^{0} ∣ A_{\emptyset} ∣ + (- 1)^{1} ∣ A_{{1}} ∣ + (- 1)^{1} ∣ A_{{2}} ∣ + (- 1)^{2} ∣ A_{{1, 2}} ∣) = ∣ X ∣ - (∣ X ∣ - ∣ A_{1} ∣ - ∣ A_{2} ∣ + ∣ A_{1} \cap A_{2} ∣) = ∣ A_{1} ∣ + ∣ A_{2} ∣ - ∣ A_{1} \cap A_{2} ∣$
This is commonly used everywhere in probability theory!

This principle is very useful in simplifying problems that may be quite complex, into simpler sub-problems that can be combined to yield our solution.

Example: Inclusion-Exclusion Principle

How many non-negative integer solutions are there to $x_{1} + x_{2} + x_{3} = 35$ , where
$0 \leq x_{1} \leq 15, 0 \leq x_{2} \leq 15, 0 \leq x_{3} \leq 15$
Here, we have a max on our integers, which is really difficult to solve! However, it may be easier to solve using the inclusion-exclusion principle.

Here, we could perform weak compositions when $x_{1}, x_{2}, x_{3} \geq 0$ , but we also have upper bounds.

Let
$A_{1} = {Weak Compositions of x_{1} + x_{2} + x_{3} = 35, x_{1} \geq 16} A_{2} = {Weak Compositions of x_{1} + x_{2} + x_{3} = 35, x_{2} \geq 16} A_{3} = {Weak Compositions of x_{1} + x_{2} + x_{3} = 35, x_{3} \geq 16}$
Note that $A_{\emptyset}$ , is all weak compositions.

We want
$∣ \overset{ˉ}{A}_{1} \cap \overset{ˉ}{A}_{2} \cap \overset{ˉ}{A} ∣ = I \subseteq [3] \sum (- 1)^{∣ I ∣} ∣ A_{I} ∣ = ∣ A_{\emptyset} ∣ + (- 1)^{1} (∣ A_{1} ∣ + ∣ A_{2} ∣ + ∣ A_{3} ∣) + (- 1)^{2} (∣ A_{1} \cap A_{2} ∣ + ∣ A_{2} \cap A_{3} ∣ + ∣ A_{1} \cap A_{3} ∣) + (- 1)^{3} ∣ A_{1} \cap A_{2} \cap A_{3} ∣ = (3 - 1 35 + 3 - 1) + 3 * (- 1)^{1} (3 - 1 19 + 3 - 1) + 3 * (- 1)^{2} (3 - 1 3 + 3 - 1) + (- 1)^{3} 0$

Example: Inclusion-Exclusion (2)

Use inclusion-exclusion to count the total surjective functions $f : [n] \to [k]$ . In other words, each $b \in [k]$ has at least 1 $a \in [n]$ such that $f (a) = b$ .

Define
$A_{1} = {Functions s.t f (j) \neq = 1, j \in [n] A_{2} = {Functions s.t f (j) \neq = 2, j \in [n] ⋮ A_{i} = {Functions s.t f (j) \neq = i, j \in [n]$
So, the number of surjective functions can be found as
$∣ i = 1 ⋂ k \overset{ˉ}{A}_{i} ∣ = I \subseteq [k] \sum (- 1)^{∣ I ∣} ∣ A_{I} ∣ = \sum (- 1)^{i} (i k) (k - i)^{n}$
Note that the first term describes the number of indices we DON’T want to map to. If we do not map to $i$ indices, then there are $k - i$ indices that we need to map to, and for each value in our domain it can map to any one of these indices (hence the $(k - i)^{n}$ .
$= k! S (n, k) ⟹ S (n, k) = \frac{1}{k !} i = 1 \sum k (- 1)^{k} (i k) (k - i)^{n}$
Which is a formula for Stirling numbers we found from earlier!

Example: Inclusion-Exclusion (3)

The Euler totient function is given as
$ϕ (n) = ∣ {i \in Z^{+} : GCD (i, n) = 1, 1 \leq i \leq n} ∣$
Which is equivalent to the total number of values in $[n]$ that are relatively prime to $n$ (meaning they have no common divisors besides 1).

Let the prime factorization of $n$ be $n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{t}^{e_{t}}, e_{i} \geq 1$ . Let
$A_{i} = {a \in [n] : p_{i} divides a}$
So, for example, if we have $p = 7$ , $n = 70$ , $∣ A_{1} ∣$ would be the number of numbers where 7 divides $a$ , $1 \leq a \leq 70$ . In other words, the number of multiples of 7!

So,
$ϕ (n) = ∣ i = 1 ⋂ t \overset{ˉ}{A}_{i} ∣ = I \subseteq [t] \sum (- 1)^{∣ I ∣} ∣ A_{I} ∣ = n - (\frac{n}{p _{1}} + \frac{n}{p _{2}} + \dots + \frac{n}{p _{t}}) + (\frac{n}{p _{1} p _{2}} + \dots + \frac{n}{p _{1} p _{3}} + \dots) + (\frac{n}{p _{1} p _{2} p _{3}} + \frac{n}{p _{1} p _{2} p _{4}} + \dots) = n 1 - i = 1 \sum t \frac{1}{p _{i}} + 1 \leq i < j \leq t \sum \frac{1}{p _{i} p _{j}} - 1 \leq i < j < k \leq t \sum \frac{1}{p _{i} p _{j} p _{k}} + \dots = n i = 1 \prod t (1 - \frac{1}{p _{i}})$
Between the last two steps, we find that this is equal to the ugly summations, as we’re basically choosing $p_{i}$ ‘s to find all possible combinations!

Example: Inclusion-Exclusion (4)

Twenty couples attend counseling. They sit at a circular, unlabeled table (exactly 40 chairs).

How many seatings assure no one sits next to their significant other?

Let $A_{i}$ denote the set where couple $1 \leq i \leq 20$ sits next to each other. We want
$i = 1 ⋂ 20 \overset{ˉ}{A}_{i} = I \subseteq [20] \sum (- 1)^{∣ I ∣} ∣ A_{I} ∣ = i = 0 \sum 20 (i 20) (- 1)^{i} \frac{( 40 - i )!}{40 - i}$
Note that what we are doing per term is selecting $i$ couples, then finding the number of orderings of our “40” people given that the $i$ couples are tied together ( $40 - i$ , because for each tied couple they’re 1 entity). Furthermore, we need to multiply by $2^{i}$ , as each couple pair could be swapped in order. Finaly, we divide by the number of rotations.

Note that we start at $i = 0$ to include the empty set.

Quartz 5

Explorer

Counting and Enumeration

Section 1: Counting and Enumeration

1.1: The Basics

Permutations

Combinations

1.2: Counting in Two Ways

1.3: Pigeonhole Principle

1.4: Compositions and Set Partitions

Compositions

Partitions

1.5: Integer Partitions

1.6: The Twelvefold Way

1.7: Inclusion-Exclusion Principle

Graph View

Backlinks