Stirling Numbers of the First Kind

What patterns hide within a simple shuffle of objects? While a permutation describes a complete rearrangement, the Stirling numbers of the first kind offer a deeper level of insight, allowing us to count the fundamental "dances" or cycles that form the building blocks of any permutation. This article demystifies these important combinatorial numbers, revealing how they are far more than a mere counting tool. It explores the surprising unity they bring to disparate fields, bridging abstract combinatorics with algebra, probability, and even the physical sciences. First, in "Principles and Mechanisms," we will explore the dual identity of these numbers, born from both counting cycles and expanding polynomials, and see how powerful tools like generating functions unlock their properties. Following this, "Applications and Interdisciplinary Connections" will journey into the real world, uncovering the role of Stirling numbers in describing genetic diversity, ecological models, and the very nature of entropy.

Imagine you have a set of distinct objects—say, a collection of four colourful marbles. If you were to shuffle them, you're creating what mathematicians call a ​​permutation​​. But what does a "shuffle" truly mean? It's not just a random jumble. A permutation is a precise rule that says where each marble goes. For instance, marble 1 might go to where 2 was, 2 to where 3 was, 3 back to where 1 was, and marble 4 stays put.

Let's visualize this shuffle. We can see a little "dance" forming. Marbles 1, 2, and 3 are in a ring, chasing each other: $1 \to 2 \to 3 \to 1$. Marble 4, meanwhile, is dancing by itself: $4 \to 4$. These closed loops are the fundamental components of any permutation, and they are called ​​disjoint cycles​​. Every possible shuffle of any number of items can be broken down, uniquely, into a set of these circular dances.

This brings us to a natural and fascinating question: if you have $n$ items, in how many ways can you shuffle them so that they form exactly $k$ separate dances? The answer to this question is a number so fundamental that it has its own name: the ​​(unsigned) Stirling number of the first kind​​, denoted by $c(n,k)$ or $\genfrac{[}{]}{0pt}{}{n}{k}$.

Let's try to get a feel for this. How many ways can we arrange our four marbles into exactly two dances? As explored in a simple combinatorial exercise ****, we have two possibilities for the dance formations. We could have one dance of three marbles and one dance of a single marble (a "fixed point"). Or, we could have two dances of two marbles each. By carefully counting the ways to assign the specific marbles to these dance patterns, we find there are 8 ways for the first case and 3 for the second. In total, there are $8+3=11$ ways. Thus, we say $c(4,2) = 11$. These numbers provide a precise language to describe the structure of permutations.

So far, we've viewed these numbers as a result of counting arrangements—a purely combinatorial idea. But remarkably, they appear in a completely different context: algebra.

Consider the polynomial $(x)_n = x(x-1)(x-2)\cdots(x-n+1)$. This is known as the ​​falling factorial​​. It's a natural cousin to the standard power $x^n$ and plays a central role in the "calculus of differences," a discrete version of ordinary calculus. Just as any well-behaved function can be written as a sum of powers $x^k$ (a Taylor series), we can express the falling factorial $(x)_n$ as a sum of powers of $x$. The coefficients in this expansion are, astonishingly, the Stirling numbers of the first kind! $(x)_n = \sum_{k=0}^{n} s(n,k) x^k$ Here, we use $s(n,k)$, the ​​signed Stirling numbers of the first kind​​ ​​. The sign is no accident; it carries profound information. The minus signs in the falling factorial, $(x-1), (x-2)$, etc., introduce signs into the coefficients, and it turns out that the sign is determined by the parity of $n-k$. Specifically, $s(n,k) = (-1)^{n-k} c(n,k)$. This links back to the cycles! The sign of a permutation $\sigma$ with $k$ cycles is defined in group theory as $\text{sgn}(\sigma) = (-1)^{n-k}$ ​​. The algebraic definition automatically encodes this fundamental property of permutations.

There's a beautiful symmetry here. If we instead expand the ​​rising factorial​​, $x^{(n)} = x(x+1)\cdots(x+n-1)$, we get the unsigned numbers directly ****: $x^{(n)} = \sum_{k=0}^{n} c(n,k) x^k$ So, Stirling numbers of the first kind form a natural bridge, a change of basis, between the world of standard powers $\{x^k\}$ and the world of factorial powers $\{(x)_n\}$ or $\{x^{(n)}\}$. They are fundamental transformation coefficients, born from algebra, that also happen to count circular dances. This is the kind of unexpected unity that makes mathematics so beautiful.

Counting $c(n,k)$ by hand, as we did for $c(4,2)$, quickly becomes an impossible task. For $c(20,5)$, the number is astronomically large. How can we possibly handle such complexity? Mathematicians have developed a wonderfully clever device: the ​​generating function​​.

Think of a generating function as a "magic box" or a clothesline on which we hang an entire infinite sequence of numbers. The box itself is a single function, often written as a power series, where our numbers are the coefficients. By manipulating the box—differentiating it, multiplying it by another function—we perform operations on all the numbers in the sequence at once.

For a fixed number of cycles $k$, the sequence of Stirling numbers $c(n,k)$ for $n=k, k+1, \dots$ can be packed into an ​​exponential generating function​​ (EGF). The result is breathtakingly simple and elegant ****: $\sum_{n=k}^{\infty} c(n,k) \frac{z^n}{n!} = \frac{(-\ln(1-z))^k}{k!}$ The logarithm, a function from calculus, is generating a sequence of integers that count combinatorial objects! Let's see this magic in action. Suppose we ask: what is the total number of cycles, summed over all $8!$ possible permutations of 8 items? This is equivalent to calculating $\sum_{k=1}^{8} k \cdot c(8,k)$ ****. A brute-force calculation would be a nightmare. But by using the magic box of generating functions, one can derive a general formula for any $n$: the total number of cycles is $n! \cdot H_n$, where $H_n = 1 + \frac{1}{2} + \dots + \frac{1}{n}$ is the famous harmonic number. For $n=8$, this gives the formidable-looking answer $109584$ with surprising ease. The generating function allowed us to solve an entire family of hard counting problems with one elegant swoop.

These numbers are not just a tool for combinatorialists; they appear all over the scientific landscape, especially in probability theory.

What is the average number of cycles in a random shuffle of $n$ cards? We just found that the total number of cycles over all $n!$ permutations is $n! H_n$. To get the average, we simply divide by the number of permutations, $n!$. The average number of cycles is just $H_n$! **** For large $n$, $H_n$ is very close to $\ln(n)$. This means a random shuffle of a 52-card deck has, on average, about $\ln(52) \approx 3.95$ cycles. A simple question, a beautiful answer.

This connection runs even deeper. If you have a collection of independent random events that follow a specific pattern called the ​​logarithmic series distribution​​, the probability of their sum being a certain value $k$ is given by a formula involving the Stirling number $c(k,n)$ ****. This shows that Stirling numbers are not just a descriptive tool; they are part of the very fabric of certain random processes.

The algebraic properties of Stirling numbers also reveal deep symmetries. We know that permutations can be classified as "even" or "odd" based on their cycle structure. Is there a balance between them? For any set of $n \ge 2$ items, it turns out that the number of permutations with an even number of cycles is exactly equal to the number of permutations with an odd number of cycles. This implies that the total number of ways to arrange $n$ items into an even number of circular groups is precisely half of all possible permutations, which is $n!/2$ ****. This profound symmetry can be proven in a single line using the rising factorial generating function, by simply plugging in $x=-1$.

We've seen that the average number of cycles for a permutation of $n$ items is about $\ln(n)$. This is a powerful statement, but it doesn't tell the whole story. What does the distribution of cycle counts look like? If we shuffle a million items, we expect about $\ln(10^6) \approx 13.8$ cycles, but could we get 5, or 50?

It turns out that as $n$ gets very large, the distribution of the number of cycles becomes incredibly predictable. It approaches the classic bell curve, or ​​Normal distribution​​. This is a version of the Central Limit Theorem applied to permutations. The mean is about $\ln(n)$, and the variance—a measure of the "spread" of the distribution—is also about $\ln(n)$ ****. This means that for large shuffles, it's extremely unlikely to get a number of cycles that is far from the average, $\ln(n)$. The chaos of individual permutations gives way to a beautiful, predictable pattern when viewed in aggregate.

We can even find an approximate formula for the Stirling number $c(n,k)$ itself. Using the powerful tools of complex analysis, one can derive an asymptotic formula for large $n$ when $k$ is near its most likely value, $\ln(n)$. The result is a jewel of mathematics ****: $c(n, \ln n) \approx \frac{n!}{\sqrt{2\pi \ln n}}$ Look at this formula! It connects $c(n,k)$, a number for counting discrete arrangements, to $n!$, the number of all permutations, and ties them together with $\pi$ and the logarithm. It shows how a smooth, continuous behavior emerges from a discrete, combinatorial world. From a simple question about a dance of marbles, we have journeyed through algebra, calculus, and probability, arriving at a vista that reveals the profound and unexpected unity of the mathematical world.

We have seen that the Stirling numbers of the first kind, which we will denote by $c(n,k)$ (also written as $\begin{bmatrix} n \\ k \end{bmatrix}$), arise from a simple combinatorial question: in how many ways can we arrange $n$ people around $k$ circular tables? At first glance, this might seem like a quaint puzzle, a mathematical curiosity confined to the world of abstract counting. But the truly remarkable thing about mathematics, and a theme we shall explore now, is how such a simple, elegant idea can ripple outwards, appearing in the most unexpected corners of the scientific universe. The cycle structure of permutations, which these numbers so beautifully count, turns out to be a fundamental pattern that nature itself seems to love to repeat. Our journey into the applications of Stirling numbers is a journey into the unity of scientific thought, from the shuffling of cards to the evolution of species and the very concept of entropy.

Perhaps the most natural place to find our numbers at work is in the study of chance. A random permutation is like a well-shuffled deck of cards. One fascinating question we can ask is about its "records," or left-to-right maxima. Imagine dealing cards one by one; a card is a record if it's higher than any card dealt before it. The first card is always a record. How many records do we expect to see? What is the probability of seeing exactly $k$ records in a permutation of $n$ items?

Amazingly, the answer is given by the Stirling numbers of the first kind. The number of permutations of $n$ elements that have exactly $k$ left-to-right maxima is precisely $c(n,k)$. This is a stunning correspondence! Why should arranging items in cycles have anything to do with a sequence of records? The connection is a beautiful piece of combinatorial magic. One can construct a direct mapping between a permutation's cycle decomposition and a permutation with a specific set of left-to-right maxima. In essence, the structure of the cycles encodes the structure of the records. This reveals a deep and hidden symmetry in the world of permutations, where two entirely different ways of seeing order turn out to be one and the same.

This connection is more than just a curiosity; it's the gateway to profound applications in population genetics and ecology. One of the most important results in this area is the ​​Ewens sampling formula​​. Imagine you are a biologist sampling $n$ genes from a large population. You want to know the probability of finding $k$ distinct types of genes (alleles) in your sample. Under a standard "neutral" model of evolution, where no gene has an advantage over another, the probability distribution for the number of distinct types, $K_n$, is given by: $P(K_n = k) = \frac{c(n,k) \theta^k}{\theta^{(n)}}$ Here, $\theta$ is the "fundamental biodiversity number," which measures the population's genetic diversity, and $\theta^{(n)}$ is the rising factorial. The Stirling numbers are not just related to this formula; they form its very core. This formula is a cornerstone of modern evolutionary theory. It allows scientists to analyze gene sequences and infer population histories. Using the mathematical properties of Stirling numbers, we can calculate theoretical quantities like the moment generating function of this distribution to understand its properties, or we can use it to build statistical tools for real-world data analysis.

In fact, this framework is powerful enough to be the engine for complex ecological models. The ​​Unified Neutral Theory of Biodiversity​​ attempts to explain the distribution of species in an ecosystem, like a tropical rainforest. A sophisticated version of this theory, the Etienne sampling model, provides a likelihood function—a way to calculate the probability of observing a specific set of species counts—that is built directly upon the Ewens formula and, therefore, on the Stirling numbers of the first kind. Ecologists can take their field data, plug it into this function, and estimate fundamental parameters like the region's biodiversity and the rate of migration between habitats. These numbers, born from a simple counting problem, are now helping us understand the rich tapestry of life on Earth. The same mathematical structure connects the distribution of gene types in a population to the distribution of species in an ecosystem, and even to the properties of abstract random variables like the Logarithmic series distribution used in statistical modeling.

The reach of Stirling numbers extends beyond the life sciences and into the fundamental laws of physics. One of the grand ideas of Ludwig Boltzmann was to connect the macroscopic properties of matter, like temperature and entropy, to the microscopic behavior of atoms and molecules. A macrostate (e.g., a gas at a certain pressure) can be realized by a vast number of different microscopic arrangements of its atoms (microstates). Boltzmann's great insight was that entropy, a measure of disorder, is simply proportional to the logarithm of the number of accessible microstates, $\Omega$: $S = k_B \ln \Omega$.

Now, let's imagine an abstract physical system of $N$ distinguishable particles. A microstate of this system is a specific permutation of these particles. We can then define a macrostate by a single property: the number of disjoint cycles, $k$, in the permutation. How many microstates correspond to this macrostate? We already know the answer: it is exactly $c(N,k)$. Therefore, the configurational entropy of this macrostate is simply $S(N,k) = k_B \ln c(N,k)$. This is a breathtaking connection. A purely combinatorial number, counting arrangements at tables, directly quantifies a fundamental physical property—entropy. The more ways there are to arrange $N$ elements into $k$ cycles, the higher the entropy of that state.

But what if the system is not static? What if particles can change their arrangement, with cycles splitting or merging? This can be described by a Markov chain, where the state of the system evolves randomly over time. A central concept here is the stationary distribution—the state of equilibrium the system eventually settles into. For many such "split-merge" processes, the stationary distribution is none other than the Ewens sampling formula we met in genetics! The system reaches an equilibrium where the probability of finding it in a state with $k$ blocks (cycles) is proportional to $c(N,k)$.

Furthermore, the principle of detailed balance, which ensures this equilibrium, requires that the rate of flow from one macrostate to another is balanced by the flow in the reverse direction. This means the ratio of the effective rate constants for, say, merging from two blocks to one versus splitting from one to two, must be equal to the ratio of the total probabilities of being in those states. These probabilities are sums over Stirling numbers, and so the very dynamics of the physical system are governed by these combinatorial quantities.

Finally, it is worth seeing how these numbers, which seem so tied to discrete counting, also live within the smooth, continuous world of calculus and analysis. Their role here is more subtle but just as fundamental. The Stirling numbers of the first kind are the coefficients that connect two different types of polynomials: standard powers $x^k$ and the so-called "rising factorials" $x^{(n)} = x(x+1)\cdots(x+n-1)$. Specifically, we have: $x^{(n)} = \sum_{k=0}^n c(n,k) x^k$ This identity makes them a kind of mathematical translator, allowing us to switch between two different algebraic languages. This "translation" service is surprisingly useful. Consider a function like $f(z) = \cos(\log(1-z))$. If we want to find its Maclaurin series expansion, we are asking for the coefficients of $z^n$. This looks like a formidable task. But the series for the logarithm brings in terms related to factorials, and the series for cosine uses simple powers. To combine them, one needs to translate between these forms, and it is precisely the Stirling numbers of the first kind that emerge to do the job, giving us the final coefficients in a beautifully structured way. Their appearance here is not an accident; it is a consequence of their deep algebraic role as the bridge between powers and factorials.

From a deck of cards to the entropy of a physical system, from the diversity of genes to the fabric of mathematical functions, the Stirling numbers of the first kind appear again and again. They are a testament to the profound and often surprising unity of science and mathematics. What begins as a simple question about seating arrangements becomes a key that unlocks a deeper understanding of randomness, evolution, and physical law. It shows us that the patterns we find in our abstract thoughts can echo in the workings of the universe itself.