Question

Let \(\left[\begin{array}{l}n \\ k\end{array}\right]\) denote the number of permutations on \(\\{1, \ldots, n\\}\) with exactly \(k\) cycles, for all nonnegative integers. These numbers are the Stirling numbers of the first kind. We have the boundary conditions \(\left[\begin{array}{l}0 \\\ 0\end{array}\right]=1,\left[\begin{array}{l}n \\ 0\end{array}\right]=0\) if \(n>0\), and \(\left[\begin{array}{l}n \\ k\end{array}\right]=0\) if \(k>n\). (i) Give all permutations on \(\\{1, \ldots, n)\) having \(k\) cycles, for \(1 \leq k \leq n \leq 4\). (ii) Prove that \(\left[\begin{array}{l}n \\\ n\end{array}\right]=1,\left[\begin{array}{c}n \\\ n-1\end{array}\right]=\left(\begin{array}{c}n \\ 2\end{array}\right)\), and \(\left[\begin{array}{l}n \\ 1\end{array}\right]=(n-1) !\) for all \(n \in \mathbb{N}_{>0}\). (iii) Find and prove a recursion formula for \(\left[\begin{array}{l}n \\\ k\end{array}\right]\) for \(1 \leq k \leq n\). Hint: Distinguish the two cases whether \(n\) is a fixed point (a cycle of length 1) or not. (iv) Prove that \(x^m=\Sigma_{0 \leq i \leq m}(-1)^{m-i}\left[\begin{array}{c}m \\\ i\end{array}\right] x^i\) for \(m \in \mathbb{N}\). What is the corresponding formula for \(x^{\bar{m}}\) ? (v) Conclude that $$ \sum_{i \leq m \leq n}(-1)^{m-i}\left[\begin{array}{c} m \\ i \end{array}\right]\left\\{\begin{array}{l} n \\ m \end{array}\right\\}=\delta_{n-i}=\sum_{i \leq m \leq n}(-1)^{n-m}\left\\{\begin{array}{l} m \\ i \end{array}\right\\}\left[\begin{array}{l} n \\ m \end{array}\right] $$ for all \(i, n \in \mathbb{N}\) such that \(i \leq n\), where \(\delta_{n-i}\) is 1 if \(n=i\) and 0 otherwise.

Short answer

Permutations with cycles are listed for \( n \leq 4 \) using Stirling numbers. Special cases prove specific Stirling numbers values. Recursion and relations to binomial powers are established.

Step-by-step solution

Understanding Stirling Numbers of the First Kind

Stirling numbers of the first kind, denoted by \( \left[\begin{array}{l}n \ k\end{array}\right] \), count the permutations of a set \( \{1, 2, \ldots, n\} \) with exactly \( k \) cycles. The boundary conditions are key to simplifying problems involving these permutations: \( \left[\begin{array}{l}0 \ 0\end{array}\right] = 1 \), \( \left[\begin{array}{l}n \ 0\end{array}\right] = 0 \) if \( n>0 \), and \( \left[\begin{array}{l}n \ k\end{array}\right] = 0 \) if \( k>n \).

Enumerating Permutations with Cycles

For non-empty sets with \( 1 \leq k \leq n \leq 4 \), we can list permutations by analyzing each n value. For example, when \( n = 3 \), permutations include \((123)\) for one cycle, and \((12)(3), (13)(2), (23)(1)\) for two cycles.

Proving Special Cases

The number \( \left[\begin{array}{l}n \ n\end{array}\right] = 1 \) because there is exactly one permutation with n cycles where each element is in its own cycle. For \( \left[\begin{array}{c}n \ n-1\end{array}\right] = \binom{n}{2} \), this results from choosing two elements to combine into a two-element cycle. Finally, \( \left[\begin{array}{l}n \ 1\end{array}\right] = (n-1)! \) because it corresponds to a single cycle of all n elements, equivalent to permutations of \( n-1 \) elements.

Finding a Recursion Formula

To establish a recursion for \( \left[\begin{array}{l}n \ k\end{array}\right] \), consider cases where \( n \) is (a) fixed in a 1-cycle, contributing \( \left[\begin{array}{l}n-1 \ k-1\end{array}\right] \), or (b) part of a larger cycle, contributing \( (n-1) \left[\begin{array}{l}n-1 \ k\end{array}\right] \), giving: \[ \left[\begin{array}{l}n \ k\end{array}\right] = \left[\begin{array}{l}n-1 \ k-1\end{array}\right] + (n-1) \left[\begin{array}{l}n-1 \ k\end{array}\right]. \]

Proving Related Equation for Powers

To establish \( x^m = \sum_{0 \leq i \leq m} (-1)^{m-i} \left[\begin{array}{c}m \ i\end{array}\right] x^i \), expand and reorganize the expression based on cycle structure. The formula associates cycle decomposition with power sums.

Connecting Negative Binomial Coefficients

The resulting identity shows that sums of Stirling numbers, corrected by sign changes, relate to cycles. Conclude: \[ \sum_{i \leq m \leq n}(-1)^{m-i}\left[\begin{array}{c}m \ i\end{array}\right]\left\{\begin{array}{l}n \ m\end{array}\right\} = \delta_{n-i}\] with respective symmetry for partition sums, demonstrating their important algebraic duality.

Key concepts

Permutations with cycles

Permutations are arrangements of elements where the order matters. When talking about permutations with cycles, we focus on how these elements can be arranged in circular sequences within the permutation. A permutation cycle is a subset of a permutation where the order of elements wraps back to the beginning.For example, in the permutation \((1 o2 o3) o1\), the sequence forms a single cycle that includes all elements. If you have a permutation like \((1 o2)(3)\), it involves one cycle \((1 o2)\) and an independent cycle contain just \((3)\). Cycles show how elements "rotate" positions, and understanding this helps in counting the cycles in a permutation precisely. Especially, in Stirling numbers, knowing how many cycles fit within a permutation is crucial.

Recursion formulas

Recursion formulas are mathematical relations that express elements in terms of other elements of the same type. For Stirling numbers of the first kind, to determine the number of permutations \( \left[\begin{array}{c}n \ k\end{array}\right] \), we use a recursion formula by distinguishing between two cases:

• **Fixed point case**: Here \(n\) stands as a cycle of length 1, affecting permutations with \(k-1\) cycles. This leads to the term \( \left[\begin{array}{c}n-1 \ k-1\end{array}\right] \).
• **Non-fixed point case**: Here \(n\) is part of a larger cycle. This involves choosing any one of the previous \(n-1\) elements to fix and arrange \(k\) cycles, leading to \((n-1) \left[\begin{array}{c}n-1 \ k\end{array}\right] \).

Thus, the recursion formula is\[ \left[\begin{array}{c}n \ k\end{array}\right] = \left[\begin{array}{c}n-1 \ k-1\end{array}\right] + (n-1) \left[\begin{array}{c}n-1 \ k\end{array}\right]\] which beautifully combines both cases into a harmonious mathematical structure.

Binomial coefficients

Binomial coefficients, represented as \( \binom{n}{k} \), play a fundamental role in combinatorics, particularly with their applications in counting combinations and arrangements. These coefficients denote how many ways you can choose \(k\) elements from a total of \(n\) without considering the order.Within Stirling numbers of the first kind, binomial coefficients appear when permuting to create fewer cycles. For instance, \( \left[\begin{array}{c}n \ n-1\end{array}\right] = \binom{n}{2} \) expresses choosing two of \(n\) elements to form a cycle, leaving the rest as single-element cycles. These coefficients bridge permutations and Stirling numbers, allowing the exploration of deeper relationships between partial permutations and combinations.

Cycle structures in permutations

Cycle structures describe how elements within a permutation are grouped into cycles. This structure is important, not just for counting permutations but for understanding their deeper properties.For any permutation, the cycle structure identifies how many disjoint cycles consist of the elements. Each number in the setup indicates an element involved in a specific cycle, and together, they convey the permutation's signature.For example, a permutation on \( \{1,2,3\} \) could feature the cycle structure \((1)(2)(3)\), indicating all elements are separate, or \((1,2)(3)\), showing a two-element cycle and an isolated element. These structures often influence how algorithms and formulas interact with permutations, providing insight into deriving results like Stirling numbers and more.