Unsigned Stirling Numbers of the First Kind

In the vast landscape of mathematics, some concepts serve as bridges, connecting seemingly disparate islands of thought. The unsigned Stirling numbers of the first kind are one such remarkable concept. At first glance, they answer a simple combinatorial question: how many ways can you seat people at a set of round tables? Yet, this simple puzzle is the gateway to a rich and interconnected world of permutations, polynomials, and probability. This article embarks on a journey to uncover the multifaceted nature of these numbers. In the first part, "Principles and Mechanisms," we will explore their fundamental definitions—from the visual arrangement of cycles to their algebraic role as polynomial coefficients. We will also uncover the elegant recurrence relation that governs their structure. In the second part, "Applications and Interdisciplinary Connections," we will venture beyond pure mathematics to witness these numbers at work in fields like statistics, machine learning, and mathematical analysis, revealing their surprising and profound utility.

Imagine you are standing before a grand canvas. At first, you see a simple, charming picture: a group of people being arranged at round tables. As you look closer, this simple scene begins to shift and transform. The people and tables dissolve into abstract symbols, revealing themselves as a fundamental concept in the world of permutations. Then, a hidden engine of logic appears, a simple rule that can generate the entire picture from a single starting point. Finally, the whole canvas reveals its true nature: it's not just a picture, but a page from an algebraic dictionary, where combinatorial arrangements are translated into the language of polynomials. This journey, from a concrete picture to a unified algebraic theory, is the story of the unsigned Stirling numbers of the first kind.

Let's start with that first charming picture. A choreographer is planning a performance with $6$ distinct dancers and wants to split them into exactly $3$ non-empty circular formations. The formations themselves are identical, so it doesn't matter which group is "formation 1" or "formation 2". Within each circle, all that matters is the relative position of the dancers—who is to their left and who is to their right. How many ways can the choreographer do this?

This is not a simple question of choosing groups. Once a group is chosen, say dancers A, B, and C, arranging them in a circle is different from arranging them in a line. In a line, ABC, ACB, BAC, BCA, CAB, and CBA are all different. But in a circle, the arrangements ABC, BCA, and CAB are identical because you can just rotate the table to get from one to the other. For $3$ dancers, there are only $(3-1)! = 2$ distinct circular arrangements: ABC (same as BCA, CAB) and ACB (same as BAC, CBA).

To solve the choreographer's problem, we'd have to consider all the ways to partition the $6$ dancers into $3$ groups (e.g., groups of sizes 4, 1, 1; or 3, 2, 1; or 2, 2, 2), and for each partition, count the number of ways to form the circles. It's a bit of work, but for $6$ dancers and $3$ circles, the answer turns out to be $225$.

This very question is what gives rise to the ​​unsigned Stirling numbers of the first kind​​. We denote the number of ways to arrange $n$ distinct objects into $k$ non-empty, indistinguishable circles as $c(n,k)$, or sometimes as $\genfrac{[}{]}{0pt}{}{n}{k}$. So, the answer to the choreographer's problem is $c(6,3) = 225$. This is our foundational, combinatorial definition. It's tangible, visual, and you can get a feel for it by drawing circles and arranging letters on a piece of paper.

Now, let's step closer to the canvas. What do these circular arrangements really represent? Consider a peculiar annual gift exchange in an office: every employee gives a gift to exactly one person, and every employee receives a gift from exactly one person. You can trace the path of the gifts: A gives to B, B gives to C, and C gives back to A. This forms a cycle! Another group might have D giving to E and E giving back to D. That's another cycle. Someone, say F, might even be assigned to give a gift to themselves—a cycle of one.

This "gift exchange" is nothing more than a ​​permutation​​. A permutation is simply a rearrangement of a set of objects. Any permutation of $n$ objects can be uniquely broken down into a set of disjoint cycles. For example, if we have 5 objects labeled $\{1, 2, 3, 4, 5\}$, the permutation that sends $1 \to 3$, $3 \to 4$, $4 \to 1$, and swaps $2 \leftrightarrow 5$ can be written in cycle notation as $(1, 3, 4)(2, 5)$. This permutation has two cycles.

Here is the grand reveal: arranging $n$ people at $k$ round tables is exactly the same problem as finding a permutation of $n$ people that consists of exactly $k$ disjoint cycles. Each table corresponds to a cycle.

This new perspective is incredibly powerful. For instance, what happens if you want to seat $n=5$ guests, but you are free to use any number of tables from $1$ to $7$? How many total arrangements are possible? In other words, what is the value of $\sum_{k=1}^{7} c(5,k)$?

From our new perspective, we are asking for the total number of permutations of $5$ guests, grouped by how many cycles they have. If we sum over all possible numbers of cycles ($k=1, 2, 3, 4, 5$), we are simply counting all possible permutations of $5$ elements. The number of permutations of $n$ elements is, of course, $n!$. It's also clear that you can't have more cycles than elements, so $c(n,k) = 0$ if $k > n$. Therefore, the answer to the planner's question is simply $5! = 120$. This beautiful and simple result, $\sum_{k=1}^n c(n,k) = n!$, connects our new numbers to one of the most fundamental quantities in mathematics. It's our first glimpse of the unifying power behind these numbers.

So, we have these fascinating numbers. But how do we calculate them without painstakingly drawing circles or listing permutations? Manually calculating $c(8, 4)$, for example, would be a nightmare. We need a machine, an algorithm, that can generate them for us. This machine is the ​​recurrence relation​​.

Let's go back to the image of seating $n$ people at $k$ tables. Imagine $n-1$ people are already seated according to some arrangement. Now, the $n$-th person arrives. Where can they sit to create a final arrangement with $k$ tables? There are two possibilities:

1. ​​They start a new table.​​ The $n$-th person sits alone at a new, $k$-th table. This means the original $n-1$ people must have been arranged in exactly $k-1$ tables. The number of ways to do that is $c(n-1, k-1)$.

2. ​​They join an existing table.​​ The original $n-1$ people are already sitting at $k$ tables, which can be done in $c(n-1, k)$ ways. Our new person can join any of these tables. Where can they sit? They can't just take a seat; they must insert themselves into the circle. In a circle of people, there is a space to the "left" of every person. Since there are $n-1$ people already seated, there are $n-1$ places where the new person can be inserted. So, for each of the $c(n-1, k)$ initial arrangements, there are $n-1$ ways to add the new person. This gives $(n-1)c(n-1, k)$ possibilities.

Adding these two disjoint cases gives us the beautiful recurrence relation: $c(n,k) = (n-1)c(n-1,k) + c(n-1,k-1)$ With a few starting values, like $c(n,n)=1$ (everyone at their own table) and $c(n,1)=(n-1)!$ (everyone at one big table), we can use this formula to compute any Stirling number we want. For instance, starting with known values for $n=6$, we can systematically compute values for $n=7$ and then $n=8$, ultimately finding that $c(8,4) = 6769$. This recurrence is the engine that builds the entire world of Stirling numbers.

Thus far, our journey has been purely combinatorial—we've been counting things. Now, we make a dramatic turn into the world of algebra, and what we find will be startling.

Consider a type of polynomial called the ​​rising factorial​​, defined as: $x^{\overline{n}} = x(x+1)(x+2)\cdots(x+n-1)$ Let's look at a small example, for $n=3$: $x^{\overline{3}} = x(x+1)(x+2) = x(x^2 + 3x + 2) = x^3 + 3x^2 + 2x$ The coefficients are 1, 3, 2. Now let's compute the Stirling numbers for $n=3$:

• $c(3,1) = (3-1)! = 2$
• $c(3,2) = 3$ (The partitions are (2,1), and there are $\binom{3}{2}$ ways to choose the pair for the 2-cycle. $\binom{3}{2}(2-1)!(1-1)! = 3$)
• $c(3,3) = 1$

Wait a moment! The coefficients of the polynomial $x^{\overline{3}}$ are precisely $c(3,3)=1$, $c(3,2)=3$, and $c(3,1)=2$. This is not a coincidence. It is a fundamental identity: $x^{\overline{n}} = \sum_{k=0}^n c(n,k) x^k$ The unsigned Stirling numbers of the first kind are precisely the coefficients that connect the basis of rising factorials to the standard basis of powers of $x$. This is our algebraic definition, and it's a bombshell. The numbers we discovered by arranging dancers in circles are the building blocks of these fundamental polynomials.

This connection is a two-way street. Not only does algebra give us a new way to think about Stirling numbers, but our combinatorial intuition gives us a new way to understand polynomials. For example, what can we say about the roots of the "Stirling Cycle Polynomial" $P_n(x) = \sum_{k=0}^n c(n,k) x^k$? Finding the roots of a high-degree polynomial is generally a formidable task. But we know this polynomial is just the rising factorial $x(x+1)\cdots(x+n-1)$. Its roots are, by simple inspection, $0, -1, -2, \ldots, -(n-1)$. They are all real, non-positive integers! This profound property, which is totally obscure from the combinatorial definition, becomes laughably obvious from the algebraic one.

This algebraic viewpoint also elegantly unites the unsigned Stirling numbers with their cousins, the ​​signed Stirling numbers of the first kind​​, $s(n,k)$. These are the coefficients of the ​​falling factorial​​, $x^{\underline{n}} = x(x-1)\cdots(x-n+1)$. A simple algebraic manipulation, noting that $x^{\underline{n}} = (-1)^n (-x)^{\overline{n}}$, reveals the simple, sign-alternating relationship between them: $s(n,k) = (-1)^{n-k}c(n,k)$.

The true power of this algebraic connection is its ability to solve complex combinatorial problems with stunning simplicity. Imagine a scenario in a data processing unit where $n$ packets are organized into some number of processing loops, and then an administrator flags exactly $m$ of these loops for priority. What is the total number of ways this can be done?

To count this directly, we'd have to consider cases. If there are $k$ loops formed (which can happen in $c(n,k)$ ways), we then choose $m$ of them to flag (in $\binom{k}{m}$ ways). We then have to sum this over all possible values of $k$: $\text{Total Ways} = \sum_{k=m}^{n} c(n,k) \binom{k}{m}$ For $n=10$ packets and $m=3$ flagged loops, this sum looks truly horrible to compute. But the algebraic machinery of generating functions, which we will not detail here, performs a miracle. It proves that this entire complex sum is equal to a single, elegant term: $\sum_{k=m}^{n} c(n,k) \binom{k}{m} = c(n+1, m+1)$ The seemingly unrelated problem of arranging $n+1$ packets into $m+1$ loops gives the answer! Our intimidating problem for $n=10$ and $m=3$ collapses to computing $c(11, 4)$, which is a large but manageable number (it's 8,409,500). This is a prime example of mathematical beauty: a complex, messy summation is revealed to have a simple, structured, and meaningful equivalent.

This is just the beginning. Even more powerful generating functions exist, like the magnificent expression $F(z, u) = (1-z)^{-u}$. When expanded as a power series in two variables, the coefficients of this single function contain all of the unsigned Stirling numbers of the first kind. In the language of modern combinatorics, the term $\ln(1/(1-z))$ represents the "gene" for a single cycle, and the exponential function acts as a machine to assemble any number of these cycles into a full permutation.

From dancers at a ball to the coefficients of polynomials and the DNA of permutations, the unsigned Stirling numbers of the first kind show us how a single idea can wear many different hats. Understanding them is not just about learning a new mathematical object; it's about appreciating the deep, surprising, and beautiful unity that runs through the heart of mathematics.

In our previous discussion, we carefully took apart the intricate machinery of the unsigned Stirling numbers, understanding them as the answer to the question: "In how many ways can we arrange $n$ people into $k$ non-empty circles?" It is a perfectly reasonable and self-contained combinatorial puzzle. But if that were the end of the story, these numbers would remain a charming, if somewhat niche, mathematical curiosity. The true magic, the real heart of the adventure, begins when we discover that the universe of science and mathematics seems to have an uncanny fondness for precisely this counting problem.

These numbers, born from a simple question about cycles and permutations, appear with surprising frequency in the most unexpected places. They are not merely abstract artifacts; they are fundamental building blocks in the language we use to describe randomness, to analyze complex functions, and to model phenomena from the distribution of genes in a population to the very structure of information. Let us now embark on a journey to see where these numbers live and what work they do, to appreciate their "unreasonable effectiveness" across the scientific landscape.

The most intuitive home for Stirling numbers is, of course, the world of permutations. By their very definition, the number $c(n,k)$ counts the permutations of $n$ elements that decompose into exactly $k$ disjoint cycles. This is their birthplace, but even here, they have more to tell us than we might first imagine.

For instance, consider all $n!$ possible ways to shuffle a deck of $n$ cards. If we pick one of these shuffles at random, what does it "look like"? How many cycles will it typically have? One might guess it's something on the order of $n$, or perhaps $n/2$. The actual answer is far more subtle and elegant. The expected, or average, number of cycles in a random permutation of $n$ elements is none other than the $n$-th Harmonic number, $H_n = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$. This is a beautiful result. The Harmonic series grows incredibly slowly, roughly as the natural logarithm $\ln(n)$. This means that for a permutation of a million items, we shouldn't expect to see half a million cycles, but rather a mere 14 or so! Stirling numbers form the backbone of this calculation, as they provide the complete distribution of cycle counts from which this average is derived.

The influence of Stirling numbers within combinatorics extends even further, appearing in problems that seem, at first glance, to have little to do with cycles. Consider the concept of "left-to-right maxima" in a sequence of numbers. In the permutation $(3, 5, 1, 6, 2, 4)$, the left-to-right maxima are 3, 5, and 6, because each is larger than any number that came before it. How many permutations of $n$ elements have exactly $k$ such maxima? Astonishingly, the answer is again the Stirling number, $c(n,k)$! That the same numbers should count two such different-looking structures—arrangements in cycles and sequences with record highs—is a classic example of the deep and often hidden unity within mathematics. It suggests a fundamental structural equivalence, a hidden "bijection," between these two concepts.

These numbers are also the essential components for solving more complex counting puzzles, where different combinatorial structures are layered on top of one another. Imagine a hypothetical corporate restructuring where departments are first grouped into an arbitrary number of divisions, and these divisions are then arranged into a fixed number of "collaboration circles." The total number of ways to achieve this is found by combining Stirling numbers of the second kind (for partitioning) with Stirling numbers of the first kind (for arranging into cycles). They can also be used, often with tools like the principle of inclusion-exclusion, to count permutations with very specific constraints, such as having an exact number of fixed points (cycles of length 1) alongside a given total number of cycles.

The connection between Stirling numbers and random permutations is our gateway into a much broader landscape: the world of probability and statistics. Here, these combinatorial numbers shed their purely discrete character and become indispensable parts of the machinery for modeling random processes.

A striking example comes from the ​​Logarithmic series distribution​​, a probability distribution used in fields like population genetics and ecology to model things like species abundance. If you take a collection of independent random variables, each following this specific distribution, and ask about the distribution of their sum, a remarkable thing happens. The probability that the sum of $n$ such variables equals a particular value $k$ is given by a formula in which the unsigned Stirling number $c(k,n)$ plays a starring role. Suddenly, our cycle-counting numbers are essential for describing the outcome of a cumulative random process.

This is not just a theoretical curiosity. In statistics, one of the central tasks is to estimate unknown parameters from observed data. If we have a sample from a population that follows a Logarithmic distribution, we might want to estimate the probability of observing a specific outcome. Using the powerful Rao-Blackwell theorem, statisticians can construct the "best possible" estimator for this probability based on the total sum of the observations. The formula for this optimal estimator explicitly involves a ratio of two Stirling numbers. Thus, these numbers move from being a descriptive feature of a probability distribution to a prescriptive tool in the very practice of statistical inference.

Perhaps the most fascinating and modern application in this domain is the ​​Chinese Restaurant Process (CRP)​​. This is a wonderfully intuitive model that describes a "rich get richer" phenomenon. Imagine customers entering a restaurant one by one. The first customer sits at a new table. The second customer can either sit with the first customer or start a new table. In general, the $n$-th customer joins an existing table with probability proportional to how many people are already there, or starts a new table with a certain fixed probability. The CRP is a cornerstone of modern Bayesian statistics and machine learning, used to model everything from how documents cluster into topics to how genes cluster into groups. And what, you might ask, is the probability that after $n$ customers have arrived, there are exactly $k$ occupied tables? The answer is a formula directly proportional to the unsigned Stirling number $c(n,k)$. The process of customers seating themselves at tables is, mathematically, a mirror of the process of elements being placed into cycles in a random permutation.

Beyond combinatorics and probability, Stirling numbers reveal their power as a formidable tool in the world of mathematical analysis—the study of continuous change and limits. This is made possible through the magic of ​​generating functions​​, which encode an entire infinite sequence of numbers into a single, smooth function.

The generating function for the Stirling numbers holds many secrets. For example, if one constructs a particular double summation involving Stirling numbers, a seemingly complicated mess of sums and powers, the entire construction miraculously collapses into the elegantly simple function $(1-z)^{-x}$. This reveals a deep and unexpected link between the Stirling numbers, which count discrete cycles, and the generalized binomial theorem, which describes the continuous powers of a function.

This analytical power allows us to perform feats that would otherwise seem impossible. Suppose we were asked to find the full Maclaurin series expansion of the rather intimidating function $f(z) = \cos(\ln(1-z))$. A brute-force approach of repeatedly taking derivatives would be a Herculean task. Yet, by combining the well-known series for cosine with the generating function for Stirling numbers, the coefficients of the series for $f(z)$ can be derived in a few elegant steps. The final expression for each coefficient turns out to be a tidy sum involving—you guessed it—unsigned Stirling numbers of the first kind. A tool forged for counting discrete objects becomes a key that unlocks the structure of a continuous, complex function.

Finally, we arrive at the frontier where the discrete meets the continuous: asymptotics. For very large $n$, the exact value of $c(n,k)$ becomes an astronomically large and unwieldy number. What is more useful is a good approximation. In the "central regime," where $k$ is close to its most likely value of about $\ln(n)$, we can ask for the approximate size of $c(n,k)$. Using the powerful ​​saddle-point method​​ from complex analysis, which is a staple of theoretical physics, one can derive a stunningly simple and accurate asymptotic formula. It turns out that for large $n$, $c(n, \ln n)$ is approximately equal to $\frac{n!}{\sqrt{2\pi \ln(n)}}$. The very large, discrete counting number is exquisitely approximated by a smooth formula involving fundamental constants and the logarithm.

From counting cycles to modeling random processes and analyzing complex functions, the unsigned Stirling numbers of the first kind demonstrate a remarkable versatility. They are a testament to the profound unity of mathematics, reminding us that the simple act of counting can lead us to the very heart of the methods we use to understand our world.