Number of all cycles in permutations is equal to n!

Question

It might be a well known fact, but I wanted to clarify if it is correct to state that the number of all possible n-permutation cycles (unsigned Stirling numbers of first kind) is factorial of n?

$$ \sum_{k=1}^{n} c(n,k) = n! $$

If correct, I assume that one could prove the statement by looking at canonical cycle notation of each permutation and argue that there exists a unique way to put parentheses to form cycles.*.

*by the lemma given in my textbook (Bona, A Walk Through Combinatorics, p130):

Lemma 6.15 (Transition Lemma). Let p : [n] → [n] be a permutation written in canonical cycle notation. Let g(p) be the permutation obtained from p by removing the parentheses and reading the entries as a permutation in the one-line notation. Then g is a bijection from the set Sn of all permutations on [n] onto Sn.

I apologize if it is an obvious statement, I just wanted to clarify that it is correct.

Answer 1

Here is the proof, from Bolker and Gleason, Counting Permuations.

It is well known that any permutation of A can be written as a product of disjoint cycles. This representation is not strictly unique because of ambiguities of order (e.g., (ab)(cd) and (dc)(ab) represent the same permutation). However, if a linear order relation is imposed on A, then we can pick out a canonical way to write a permutation of A as a product of cycles by observing the following rules :

(a) Even trivial cycles of length one are written.

(b) Each cycle is written so that its least member occurs at the end.

(c) The cycles are written so that their least members increase.

Hence, if A = {a, b, c, d, e, f g} with alphabetical order, the permutation (a c e) (g d f) has the canonical form (c e a) (b) (f g d). Now in this canonical form the parentheses marking the cycle boundaries can be dispensed with; there is no loss of information if we write the above permutation simply as the arrangement c e a b f g d, because a cycle closes whenever we come to an element which precedes in the ordering of A all the elements that follow it in the arrangement. We obtain in this way a one-to-one correspondence between the arrangements of A and the permutations of A.

Answer 2

Think about it like this: If I knew the digits in your 5-digit laptop password but did not know the exact order they came in, how many guesses can I attempt to make, assuming I'm lazy and that first step itself took a lot of effort?

So I must type in a first digit. I have five options for this. Consider one of the options, like $4$ maybe. I have four more options left for the second digit. Let's say $3$. I'll then have 3 choices for the third digit and so on. Obviously, after four digits I only have one choice for the fifth digit.

Thus consider this: I have $5$ options for digit $1$, each of which branch out into $4$ possibilities for the second digit, $3$ for the third and so on.

By the way these are permutations because order matters. I won't gain access if I write the digits in the wrong way, otherwise I would have never bothered with this story in the first place.

Consider the branching then. $5$ into $4$ on and on it $1$. This maps our possibility space which becomes: $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

Look familiar?