Sum rules for permutations with fixed points involving Stirling numbers of the first kind

This paper proposes sum rules for the moments of permutations with a fixed number of fixed points involving Stirling numbers of the first kind, while also deriving related identities for binomial coefficients and outlining connections to Bell numbers.

The Gist

Imagine you have a deck of $n$ cards, numbered 1 to $n$. You shuffle them. Sometimes, a card ends up in the exact same spot it started in (e.g., the "5" is still in the 5th position). In mathematics, we call this a fixed point.

This paper is a mathematical detective story about counting these shuffles. The author, Jean-Christophe Pain, is trying to find hidden patterns (called "sum rules") in how often these fixed points appear. He connects this to some very old, very famous number families: Stirling numbers and Bell numbers.

Here is the breakdown of the paper using simple analogies:

1. The Main Characters: The Shuffle and the Fixed Points

Think of a permutation as a dance where everyone swaps partners.

• The Goal: Count how many times a dancer ends up standing in their original spot (a fixed point).
• The Problem: We know how to count dances where no one stays put (called "derangements"). But what if we want to know about dances where exactly 1 person stays put, or 2, or 3?
• The Formula: The paper starts with a simple recipe: To find the number of dances with $k$ fixed points, you choose which $k$ people stay put, and then scramble the rest so none of them stay put.

2. The "Magic Generator" (Generating Functions)

To solve this, the author uses a tool called a Generating Function.

• The Analogy: Imagine a magical vending machine. You put in a variable (like $x$), and it spits out a long list of numbers representing all possible shuffles.
• What the author did: He built a specific machine that tracks not just the total number of shuffles, but specifically how many fixed points they have. By tweaking the machine (using calculus, specifically derivatives), he could "extract" the total count of fixed points across all possible shuffles.

3. The Hidden Connection: Stirling Numbers

This is where the paper gets its "secret sauce."

• Stirling Numbers of the First Kind: Think of these as a special code or a dictionary that translates between two different ways of counting.
  • Way A: Counting how many ways you can arrange items into cycles (loops).
  • Way B: Counting powers of numbers (like $k^2$, $k^3$).
• The Discovery: The author found that if you take the number of fixed points in a shuffle, raise it to a power, and add them all up, the result is always a clean, simple number (specifically, $n!$, which is the total number of ways to arrange $n$ items).
• The "Sum Rule": It's like saying, "If you add up the squares of the number of fixed points for every possible shuffle, the total is exactly $n!$." The paper proves this works for cubes, fourth powers, and so on, using the Stirling code to translate the math.

4. The Side Quest: Binomial Coefficients and Bell Numbers

The paper doesn't stop there. It uses the Stirling code to solve other puzzles.

• Binomial Coefficients: These are the numbers you see in Pascal's Triangle (like the coefficients in $(a+b)^n$). The author found new, weird-looking formulas for these numbers by mixing the Stirling code with a formula from another mathematician (Vassilev-Missana).
• Bell Numbers: These count how many ways you can split a group of people into different teams. The paper shows that these Bell numbers are secretly related to the "moments" (the sums of powers) of our fixed-point shuffles.
  • Analogy: It's like discovering that the total number of ways to organize a party into groups is mathematically identical to a specific sum of how many people stayed in their seats during a chaotic game of musical chairs.

5. Why Does This Matter?

You might ask, "Who cares about shuffling cards?"

• The Big Picture: In probability and statistics, understanding how "random" things behave is crucial. The number of fixed points in a random shuffle follows a famous pattern called the Poisson distribution (the same pattern that describes how many raindrops hit a window or how many customers arrive at a store).
• The Benefit: By finding these exact "sum rules," the author provides a way to check calculations, estimate bounds (how big or small these numbers can get), and understand the deep structure of randomness. It's like finding the perfect balance point on a seesaw; once you know the rule, you can predict the outcome without counting every single time.

Summary

In short, this paper is a bridge. It connects:

1. Shuffling cards (Permutations with fixed points).
2. Old number codes (Stirling numbers).
3. Grouping people (Bell numbers).

The author uses a "magic machine" (generating functions) to show that these seemingly different concepts are actually different sides of the same coin, revealing elegant mathematical laws that govern how things are arranged and rearranged.

Technical Summary

Here is a detailed technical summary of the paper "Sum rules for permutations with fixed points involving Stirling numbers of the first kind" by Jean-Christophe Pain.

1. Problem Statement

The paper addresses the combinatorial problem of analyzing permutations of the set $\{1, 2, \dots, n\}$ that possess exactly $k$ fixed points. Let $p_n(k)$ denote the number of such permutations. While identities involving permutations with fixed points often rely on Stirling numbers of the second kind or Bell numbers, this work seeks to establish new sum rules (identities) involving Stirling numbers of the first kind, denoted as $s(q, r)$.

The specific objectives are:

• To derive identities relating the moments of the distribution of fixed points ($\sum k^m p_n(k)$) to factorials and Stirling numbers of the first kind.
• To utilize these identities, combined with specific formulas (Vassilev-Missana and Schlömlich), to generate new sum rules for binomial coefficients.
• To explore connections with Bell numbers ($B_n$) and provide alternative expressions for them.

2. Methodology

The author employs a combination of generating functions, combinatorial recurrence relations, and algebraic manipulation of known identities.

A. Generating Function Approach

The core of the derivation relies on the generating function for the sequence $p_n(k)$.

1. Definition: The author defines $f_n(t) = \sum_{k=0}^n t^k p_n(k)$ and constructs the exponential generating function $G(x) = \sum_{n=0}^\infty \frac{f_n(t)}{n!} x^n$.
2. Derivation: Using the relation $p_n(k) = \binom{n}{k} d_{n-k}$ (where $d_m$ is the number of derangements of $m$ elements), the generating function is simplified to:
   $$G(x) = \frac{e^{x(t-1)}}{1-x}$$
   This is identified as the product of the generating function for derangements ($e^{-x}/(1-x)$) and the term $e^{xt}$.
3. Coefficient Extraction: By expanding $G(x)$ and identifying the coefficient of $x^n$, the author derives a relationship between the moments of $p_n(k)$ and the falling factorials.

B. Connection to Stirling Numbers of the First Kind

The falling factorial $(x)_r = x(x-1)\cdots(x-r+1)$ is expanded using signed Stirling numbers of the first kind:
$$(x)_r = \sum_{k=0}^r s(r, k) x^k$$
By taking derivatives of the generating function with respect to $t$ at $t=0$, the author links the sum of falling factorials of fixed points to $n!$. This is then converted into a sum involving powers $k^i$ via the Stirling number expansion.

C. Integration of Advanced Identities

To derive rules for binomial coefficients, the paper integrates:

• Vassilev-Missana Identity (2005): An expression for powers $k^i$ as a finite sum involving binomial coefficients.
• Schlömlich Expression: A specific formula for Stirling numbers of the first kind involving nested sums and binomial coefficients.
• Worpitzky Identity: Used as an alternative method involving Eulerian numbers.

3. Key Contributions and Results

A. Main Theorem (Sum Rules for Moments)

The primary result is Theorem 1, which establishes a family of sum rules for any natural numbers $n$ and $m$ (where $1 \le r < n-1$):
$$\sum_{k=0}^n \left( \sum_{i=0}^{r+1} s(r+1, i) k^i \right) p_n(k) = n!$$
This identity states that a weighted sum of the moments of the number of fixed points, weighted by Stirling numbers of the first kind, equals $n!$.

• Specific Cases: The paper explicitly lists values for low-order moments:
  • $\sum k p_n(k) = n!$
  • $\sum k^2 p_n(k) = 2 n!$
  • $\sum k^3 p_n(k) = 5 n!$
  • $\sum k^4 p_n(k) = 15 n!$

B. Binomial Sum Rules

By substituting the Vassilev-Missana formula for $k^i$ and the Schlömlich formula for $s(r+1, i)$ into the main theorem, the author derives complex but exact identities for sums of binomial coefficients.

• The resulting expressions involve nested sums with alternating signs and multiple binomial coefficients, equating to $n!$ (or 1 when normalized).
• Example structure:
  $$\sum_{k=0}^n \sum_{i=0}^{r+1} \sum_{l=0}^{\lfloor \dots \rfloor} \sum_{j,h} (\dots) \binom{\dots}{\dots} p_n(k) = n!$$

C. Alternative Expressions for Bell Numbers

The paper demonstrates that the derived sum rules can be inverted or manipulated to provide new representations for Bell numbers ($B_q$).

• It re-derives the known relation $B_q = \frac{1}{n!} \sum_{k=0}^n k^q p_n(k)$ (valid for $n \ge q$).
• By substituting the binomial expansions of $k^q$ and $p_n(k)$, the author provides a new, complex binomial sum representation for $B_q$:
  $$B_q = \sum_{k=0}^n \sum_{l=0}^{\lfloor \frac{(k-1)q}{k} \rfloor} \sum_{i=0}^{n-k} (-1)^{l+i} \frac{1}{k! i!} \binom{q}{l} \binom{k(q-l)}{q}$$

D. Bounds and Asymptotics

The paper includes an appendix deriving upper bounds for the sums involving Stirling numbers using known bounds for $|s(n, m)|$. It also discusses the asymptotic behavior of Bell numbers using the Lambert $W$ function, linking the combinatorial sums to analytic number theory.

4. Significance and Future Work

Significance:

• Bridging Combinatorics: The work successfully bridges the gap between permutations with fixed points (often associated with derangements and Stirling numbers of the second kind) and Stirling numbers of the first kind.
• New Identities: It provides a systematic method to generate infinite families of identities for binomial coefficients, which are often difficult to derive directly.
• Unification: It unifies the treatment of moments of fixed points, Bell numbers, and Stirling numbers under a single generating function framework.

Future Directions:
The author proposes extending this methodology to involutions (permutations where $\sigma^2 = id$) with $k$ fixed points, suggesting that similar sum rules involving Stirling numbers may exist for this specific subset of permutations.

Conclusion

Jean-Christophe Pain's paper offers a rigorous algebraic framework for analyzing the distribution of fixed points in permutations. By leveraging generating functions and advanced combinatorial identities, the author derives novel sum rules that connect the moments of fixed points to Stirling numbers of the first kind, yielding new insights into binomial sums and Bell numbers.