What's a formal definition of cycles that will allow me to prove this identity?

Question

On page 261 of chapter 6 in Concrete Mathematics, the authors gesture towards the following proof of the identity $$\sum_{k = 0}^n \left[\begin{array}{l} n \\ k \end{array}\right] = n!$$ where the $\left[\begin{array}{l} n \\ k \end{array}\right]$s are the Stirling numbers of the first kind. They argue that the sum on the left-hand-side counts the number of partitions of an $n$ element set $S$ into disjoint cycles, and the $n!$ on the right-hand-side counts the number of permutations of $S$. Thus, if the set of all partitions of $S$ into disjoint cycles is in bijection with the set of all permutations of $S$, then the identity will follow. They then give an informal argument for the bijection and illustrate it with an example.

I want to prove more formally that the bijection holds, but I'm having trouble because the authors don't give a formal definition of the "cycles" that the Stirling numbers count. What's a good formal definition of these cycles that will allow me to prove this? If you could be as explicit and clear as possible, that would especially helpful as I'm very new to math.

Edit: The closest thing to a definition that the authors give is

Answer 1

I can give a rigorous definition of cycles, but first, I want to point out that the equation $\sum_{k=0}^n {n \brack k}=n!$ can be understood even without precisely knowing what cycles are. All you need is this:

• $n!$ is the number of permutations of $\{1,\dots,n\}$.

• For each $k\in \{0,\dots,n\}$, ${n \brack k}$ is the number of permutations of $\{1,\dots,n\}$ with $k$ cycles.

• Every permutation of $\{1,\dots,n\}$ has between $0$ and $n$ cycles.

Therefore, $\sum_{k=0}^n {n \brack k}=n!$ just expresses the fact that if you add up the number of permutations with each possible cycle number, you get the total number of permutations.

You do not need a bijection to prove this equality. It is a just a consequence of the basic addition principle in combinatorics; if a set $A$ is written as the disjoint union of sets $A_1,\dots,A_n$, then $|A|=|A_1|+\dots+|A_n|$. In this case, $A$ is the set of all permutations, and $A_k$ is the set of permutations with $k$ cycles.

---

A cycle in a permutation can be defined in a number of ways:

• We say that a list of elements $[x_1,x_2,\dots,x_\ell]$ is a cycle of $\pi$ if $\pi(x_i)=x_{i+1}$ for each $i\in \{1,\dots,\ell-1\}$, and if $\pi(x_\ell)=x_1.$

• The cycles are the connected components of the graph on the vertex set $\{1,\dots,n\}$, whose edges are of the form $\{x,\pi(x)\}$.

• Define an equivalence relation on $\{1,\dots,n\}$ by saying $x\sim_\pi y$ when there exists $n\in \mathbb N$ for which $\pi^n(x)=y$. Then the equivalence classes of this relation are the cycles of $\pi$.

Answer 2

Thanks for quoting the definition from the book. A slightly more formal way of describing the notion of cycle is to say that it's a finite set $X$ enumerated as $\{x_1, x_2, \ldots, x_k\}$ where we think of $x_{i+1}$ coming "next" after $x_i$ and also think of $x_1$ as coming next after $x_k$. In the same way as $1$ o'clock comes after $12$ o'clock and we don't distinguish between $\{x_1, x_2, \ldots, x_k\}$ and $\{x_2, x_3, \ldots, x_k, x_1\}$. A rigorous definition is best given in terms of the theory of permutations and the notion of cyclic permutation (allowing us to view the cycle as a special kind of permutation rather than as a set of equivalent ways of listing the elements of a set). However, that may make the proof in the book seem a little "circular": it's probably best to learn about permutations before you learn about Stirling numbers.

Answer 3

Take an element in $[n]=\{1,2,\cdots ,n\}$, say $\ell$. Lets say that you are studying a permutation $\pi$. Consider now the set $A_{\ell}=\{\pi ^k (\ell):k\in \mathbb{Z}^{\geq 0}\}$, where the $\pi ^k$ means composing your permutation $k$ times. Show that this set is always finite. What happens if not? Show that if you take two elements, say $\ell _1,\ell _2 \in [n]$ then either $A_{\ell _1}=A_{\ell _2}$ or $A_{\ell _1}\bigcap A_{\ell _1}=\emptyset$. Conclude that this sets partition $[n]$.

Show that you can always represent a permutation by this sets when you impose an order to them (like in the drawing) think that the natural ordering is induced by the normal integer ordering of the $k'$s . The amount of different sets that you can construct is what the identity call $k$. Define now the Stirling numbers as the number of permutations with exactly $k$ distinct $A_{\ell}'$s for $\ell \in [n]$. The bijection then would be mapping permutations to their "ordered sets" and filtering by the number of such sets.