• Contents.

Preface

Combinatorics to discrete mathematics is like analysis to continuous mathematics or calculus. In this note, I would like to walk through a great book named “A Walk through Combinatorics: an introduction to Enumeration and Graph Theory”. This book is used as the textbook of MIT’s combinatorics course. I like this book due to its clarity and its style of intuitive progression. Every chapter has a proper load of pages and workload, i.e. around 20 pages.

Structural Memos

This part will be like more structured knowledge spores, e.g. summarised with mind maps or other figurative objects.

Draft Notes

Ch1: The pigeon-Hole Principle

xxx

Ch3: Elementary Counting Problems

3.1 Permutations

Definition 3.1. (Permutation) The arrangement of different objects into a linear order using each object exactly once is called a permutation of these objects. The number $n \cdot (n-1) \cdot (n-2) \cdot \cdot \cdot 2 \cdot 1$ of all permutations of $n$ objects is called $n$ factorial, and is denoted by $n!$.

<aside> ❓

Q: Why by convention $0! = 1$?

A: The multiplication law of factorials, $n! \cdot m!$.

</aside>

<aside> ❓

Q: How large is $n!$?

A: $n! \sim \sqrt{2 \pi n} \large{(} \frac{n}{e} \large{)}^n$, where the symbol $n! \sim z(n)$ means that $\lim_{n \rightarrow \infty} \frac{n!}{z(n)} = 1$ . It is called the Stirling’s formula.

</aside>

Theorem 3.5. (Multiset Permutation) Let $n, k, a_1, a_2, \cdots, a_k$ be nonnegative integers satisfying $a_1 + a_2 + \cdots + a_k = n$. Consider a multiset of $n$ objects, in which $a_i$ objects are of type $i$, for all $i \in [k]$. Then the number of ways to linearly order these objects is:

$$ \frac{n!}{a_1! \cdot a_2! \cdots a_k!} $$

• How to understand?
  • It is important to read carefully and digest the meaning of the way to combine or arrange objects.
  • Say for an instance, $a_1$ is the number of 🐈, $a_2$ is the number of 🐕, $a_3$ is the number of 🦉; and $a_1 = 2, a_2 = 1, a_3 = 2$; we want to line them in a line at the beginning of an animal show:
    • there are $a_1 + a_2 + a_3 = 5$ positions to hold them, we can actually have $5!$ permutations of their arrangement,
    • however, to swap the positions within say 🐈 cannot form new arrangements, the same with other two animals
    • so we should divide $5!$ by the redundant calculations of the permutations of the same kind of animal, i.e. $2!$, $1!$ and $2!$.
• (2025.01.11) Update

Ch5: Divide and Conquer. Partitions

This chapter discusses distribution problems. That is:

• distribute $n$ objects (balls) into $k$ boxes, how many ways can this be done?