Stirling numbers with fixed n and k

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Hi everyone!

In combinatorics, you often need to compute Stirling numbers for various reason. Stirling numbers of the first kind count the number of permutations of $$$n$$$ elements with $$$k$$$ disjoint cycles, while Stirling numbers of the second kind count the number of ways to partition a set of $$$n$$$ elements into $$$k$$$ nonempty subsets. Besides that, they're often arise when you need to change between powers of $$$x$$$ and rising/falling factorials. There are three problems on Library Checker that go as follows:

Library Checker — Stirling Number of the First Kind. Given $$$N$$$, find $$$s(N, k)$$$ for $$$0 \leq k \leq N$$$.

Library Checker — Stirling Number of the Second Kind. Given $$$N$$$, find $$$S(N, k)$$$ for $$$0 \leq k \leq N$$$.

Library Checker — Stirling Number of the First Kind (Fixed K). Given $$$N$$$ and $$$K$$$, find $$$s(n, K)$$$ for $$$K \leq n \leq N$$$.

Here $$$s(n, k)$$$ are Stirling numbers of the first kind, and $$$S(n, k)$$$ are Stirling numbers of the second kind. Let's solve them!

Definitions

There are various ways to define Stirling numbers. In this blog, we will follow the algebraic approach to highlight their connection.

Def.: The falling factorial is the polynomial $$$(x)_n$$$ defined as

$$$ \boxed{(x)_n = \overbrace{x (x-1) \dots (x-n+1)}^{n\text{ factors}} = \prod\limits_{i=0}^{n-1} (x-i)} $$$

Def.: The rising factorial is the polynomial $$$x^{(n)}$$$ defined as

$$$ \boxed{x^{(n)} = \overbrace{x (x+1) \dots (x+n-1)}^{n\text{ factors}} = \prod\limits_{i=0}^{n-1} (x+i)} $$$

Note: From the definitions above, it follows that $$$x^{(n)} = (x+n-1)_n = (-1)^n (-x)_n$$$.

We will start with Stirling numbers of the second kind, as the proof is simpler for them.

Def.: Stirling numbers of the second kind are the coefficients $$$S(n, k)$$$ in the expansion of $$$x^n$$$ into falling factorials:

$$$ \boxed{x^n = \sum\limits_{k=0}^n S(n, k) (x)_k} $$$

Claim: The value $$$S(n, k)$$$ equates to $$$C(n, k)$$$ the number of ways to partition $$$n$$$ distinct elements into $$$k$$$ non-empty sets.

Note: We assume that there is a unique way to partition a set of $$$0$$$ elements into $$$0$$$ non-empty sets.

Proof

Def.: Stirling numbers of the first kind are the coefficients $$$s(n, k)$$$ in the expansion of $$$(x)_n$$$ into powers of $$$x$$$:

$$$ \boxed{(x)_n = \sum\limits_{k=0}^{n} s(n, k) x^k} $$$

Note: From the definition above, and the fact that $$$x^{(n)} = (-1)^n (-x)_n$$$, it follows that

$$$ x^{(n)} = \sum\limits_{k=0}^n (-1)^{n-k} s(n, k) x^k = \sum\limits_{k=0}^n |s(n, k)| x^k. $$$

Claim: The absolute value $$$|s(n, k)|$$$ equates to $$$c(n, k)$$$, is the number of permutations of length $$$n$$$ with $$$k$$$ disjoint cycles.

Proof

Standard, possibly simpler, approaches here typically involve either of the following:

Proving that $$$|s(n, k)|$$$ and the number of permutations with $$$k$$$ cycles satisfy the same recurrence (see here),
Showing a bijection between ways to expand $$$x^{(n)}$$$ and ways to construct a permutation with a specific cycle structure (see here).

We will use a different approach, which is a bit more involved, but is consistent with the proof for Stirling numbers of the second kind.

Assume that we're coloring the set of $$$n$$$ indistinguishable objects into $$$x$$$ colors. How many ways are there to do it?

On one hand, it is $$$\binom{n+x-1}{n} = \frac{x^{(n)}}{n!}$$$, as can be derived with the help of stars and bars (theorem 2).

On the other hand, let's consider all colorings of $$$n$$$ distinct objects and group them in equivalence classes in such way that each class unites colorings that can be obtained from one another with a permutation. We essentially need to compute the total amount of such classes, as each class uniquely corresponds to a coloring of indistinguishable objects.

Claim: Let $$$I(c)$$$ be the number of permutations that translate a coloring $$$c$$$ into itself. Then the size of $$$c$$$'s class is $$$\frac{n!}{I(c)}$$$.

Proof

From the claim above it follows that we can count the number of equivalence classes by summing up $$$\frac{I(c)}{n!}$$$ over all colorings of distinct objects. In this way, the summands within each individual class will sum up to $$$1$$$, so the whole sum is the number of such classes. On the other hand, the sum $$$I(c)$$$ of "stabilizing" permutations over individual colorings can be substituted with a sum of "fixed points" (i.e. colorings that stay the same) over all permutations.

For a permutation with $$$k$$$ cycles, the number of fixed points is $$$x^k$$$, which corresponds to the number of ways to color all elements on each cycle in the same color. Thus, the number of the colorings expresses as

$$$ \frac{x^{(n)}}{n!} = \frac{1}{n!} \sum\limits_{k=0}^n c(n, k) x^k. $$$

LHS and RHS are the same for any integer $$$x$$$, but since they're both polynomials in $$$x$$$, it must mean that they're identical.

Note: The proof essentially repeats the proof of Burnside's lemma, but adjusted to this particular setting.

Generating functions

Finding Stirling numbers with fixed $$$n$$$ or $$$k$$$ will most certainly involve working with polynomials. As it's usually most convenient to explain polynomial operations in the framework of generating functions, let's find them for Stirling numbers.

Stirling numbers of the second kind

As we already mentioned, $$$S(n, k)$$$ is the number of ways to partition a set of $$$n$$$ distinct objects into $$$k$$$ non-empty sets. The exponential formula tells us that if $$$F(x)$$$ is the exponential generating function for objects of some kind, then $$$\exp F(x)$$$ is the generating function for sets of such objects, also meaning that $$$\exp F(x) - 1$$$ is the generating function for non-empty sets of such objects.

As things enumerated by $$$S(n, k)$$$ can be described as "sets of $$$k$$$ non-empty sets of objects", the exponential generating function should look roughly as $$$e^{e^{x} - 1}$$$, where $$$x$$$ is a formal variable keeping track of "base" objects. However, for Stirling numbers we need to keep track of the base objects (their total amount sums to $$$n$$$), and of the non-empty sets, in which we split them (their amount sums to $$$k$$$).

To account for non-empty sets, we will introduce another variable $$$y$$$, and use the generating function

$$$ F(x, y) = e^{y(e^x-1)} $$$

instead. In this way, when the external exponent is expanded into powers of $$$(e^x-1)$$$, each summand $$$\frac{(e^x-1)^k}{k!}$$$, corresponding to sets of $$$k$$$ non-empty sets will be additionally multiplied by $$$y^k$$$. Thus, we get the expansion into generating function as

$$$ \boxed{\sum\limits_{n=0}^\infty \sum\limits_{k=0}^n S(n, k) \frac{x^n}{n!} y^k = e^{y(e^x-1)}} $$$

Fixed $$$k$$$

Using the power series definition of exponent, we can then expand it as

$$$ e^{y(e^x-1)} = \sum\limits_{k=0}^\infty \frac{y^k (e^x-1)^k}{k!}, $$$

from which we get the exponential generating function with a fixed $$$k$$$:

$$$ \boxed{S(n, k) = \left[\frac{x^n}{n!}\right] \frac{(e^x-1)^k}{k!}} $$$

Fixed $$$n$$$

Library Checker — Stirling Number of the Second Kind. Given $$$N$$$, find $$$S(N, k)$$$ for $$$0 \leq k \leq N$$$.

But what if we want to expand with fixed $$$n$$$? No worries! Let $$$F(y)$$$ be the ordinary generating function of $$$S(n, k)$$$ with fixed $$$n$$$.

From the definition of Stirling numbers, considering $$$t=0, 1, \dots$$$ we get

$$$ t^n = \sum\limits_{k=0}^n S(n, k) \frac{t!}{(t-k)!}. $$$

Right-hand side can be perceived as a convolution of $$$F(y)$$$ and $$$e^y$$$, as the later expands into sum of $$$\frac{y^{t-k}}{(t-k)!}$$$. Thus,

$$$ \sum\limits_{t=0}^\infty \frac{t^n y^t}{t!} = e^y F(y), $$$

from which follows the generating function with a fixed $$$n$$$:

$$$ \boxed{S(n, k) = [y^k] e^{-y} \sum\limits_{t=0}^\infty \frac{t^n y^t}{t!}} $$$

Defined this way, the generating function on the right-hand side is also known as the $$$n$$$-th Touchard polynomial.

Expanded, the expression above transforms into the well-known explicit formula

$$$ \boxed{S(n, k) = \frac{1}{k!}\sum\limits_{t=0}^k (-1)^{k-t} \binom{k}{t} t^n = \sum\limits_{t=0}^k \frac{(-1)^{k-t} t^n}{t!(k-t)!}} $$$

which can also be obtained through the principle of inclusion and exclusion. The formula above can also be used to compute a specific $$$S(n, k)$$$ in $$$O(k \log_k n)$$$ without Fourier transform or other complicated algorithms.

Stirling numbers of the first kind

Generally, a permutation can be represented as a set of cycles. The exponential generating function for cycles is known to be

$$$ \log \frac{1}{1-x} = \sum\limits_{k=1}^\infty \frac{x^k}{k}. $$$

Now, we can mark each cycle by an additional formal variable $$$y$$$ and apply exponential formula. However, we should note that for signed Stirling numbers, we should multiply the coefficient near $$$x^n y^k$$$ with $$$(-1)^{n-k}$$$, which is done by substituting $$$x$$$ and $$$y$$$ with $$$-x$$$ and $$$-y$$$:

$$$ F(x, y) = e^{-y \log \frac{1}{1+x}} = e^{y \log (1+x)} = (1+x)^y. $$$

So, similarly to Stirling numbers of the second kind, we get the expansion

$$$ \boxed{\sum\limits_{n=0}^\infty \sum\limits_{k=0}^n s(n, k) \frac{x^n}{n!} y^k = (1+x)^y } $$$

Unlike generating functions for the Stirling numbers of the second kind, this one can be checked in a very straightforward way:

$$$ (1+x)^y = \sum\limits_{n=0}^\infty \binom{y}{n} x^n = \sum\limits_{n=0}^\infty \frac{x^n}{n!}(y)_n = \sum\limits_{n=0}^\infty \frac{x^n}{n!} \sum\limits_{k=0}^n s(n, k) y^k. $$$

Fixed $$$k$$$

Library Checker — Stirling Number of the First Kind (Fixed K). Given $$$N$$$ and $$$K$$$, find $$$s(n, K)$$$ for $$$K \leq n \leq N$$$.

One obvious way to find the generating function with fixed $$$k$$$ is to expand

$$$ e^{y \log(1+x)} = \sum\limits_{k=0}^\infty \frac{\log(1+x)^k}{k!}y^k, $$$

so we get the exponential generating function with a fixed $$$k$$$:

$$$ \boxed{s(n, k) = \left[\frac{x^n}{n!}\right] \frac{\log(1+x)^k}{k!}} $$$

Fixed $$$n$$$

Library Checker — Stirling Number of the First Kind. Given $$$N$$$, find $$$s(N, k)$$$ for $$$0 \leq k \leq N$$$.

Sasha and the Swaps II. Given $$$n$$$, find the number of distinct permutations obtainable with exactly $$$k$$$ swaps for each $$$k$$$ from $$$1$$$ to $$$n-1$$$.

For a fixed $$$n$$$, we already know that the generating function would be

$$$ (y)_n = y(y-1)\dots(y-n+1). $$$

Computing it as is with divide and conquer approach, we would get $$$O(n \log^2 n)$$$. Can we do better? Sure thing! We can represent it as

$$$ (y)_{2n} = (y)_{n} (y-n)_{n}, $$$

therefore we can first compute $$$(y)_n$$$, then do a Taylor shift to find $$$(y-n)_n$$$ and multiply them in $$$O(n \log n)$$$. The overall time is

$$$ T(n) = T\left(\frac{n}{2}\right) + O(n \log n) = O(n \log n). $$$

Комментарии (8)

Написать комментарий?

granadierfc

16 месяцев назад, # |

wow thats great. I had thought that we could calculate Stirling number in O(n^2).

→ Ответить

Papercut

12 месяцев назад, # |

← Rev. 4 →

Nice technique! I have one question: can it be generalized for the arbitrary(?) exponential families?
Let's suppose we have an exponential family $$$F$$$ and we know it's deck enumerator $$$D(x)$$$, and we are asked: what is the number of hands of weight $$$n$$$ and $$$k$$$ cards (with fixed $$$n$$$)?
For example, in this problem we have to find the number of functional graphs with $$$n$$$ vertices and $$$k$$$ components for $$$1 <= k <= n$$$.
Surely, functional graphs can be thought as an exponential family, where cards are connected functional graphs, decks are standard cards (so, basically, $$$[\frac{x^n}{n!}]D(x)$$$ is a number of connected functional graphs with $$$n$$$ vertices), and hands are all functional graphs (not necessarily connected).
We know that $$$H(x) = \sum\limits_{i=1}^\infty \frac{i^i}{i!}x^i$$$, and know that $$$D(x) = \ln H(x)$$$.
So, we are able to solve for fixed $$$k$$$ in $$$O(n log n)$$$, because $$$h(n, k) = [\frac{x^n}{n!}]{\frac{{D(x)^k}}{k!}}$$$, but how can we find $$$G(y) = \sum\limits_{k=1}^\infty h(n, k){y}^{k}$$$?
Everything i tried was not successful...

adamant

12 месяцев назад, # ^ |

Uhhh, I'm not sure I understand what you mean here. What is an exponential family? What is a deck enumerator?

My bad — taking into account an enormous amount of your blogs about combinatorics and generating functions, I had no doubt you've read Herbert S Wilf's "gfology2" (These definitions are given in section "Cards, Decks and Hands: The exponential formula").

From exponential formula we know that if we EGF of some combinatorial objects, say $$$D(x)$$$, s.t. $$$[\frac{x^n}{n!}]{D(x)} = d_{n}$$$ is a number of these objects of weight $$$n$$$, then $$$H(x) = e^{D(x)}$$$ is the EGF of sets of these objects, and, in particular, number of sets of weight $$$n$$$ and $$$k$$$ objects is $$$h(n, k) = [\frac{x^n}{n!}]({\frac{{D(x)^k}}{k!}})$$$.

So, the initial question can be formed like that: if we have EGF of some combinatorial objects $$$D(x)$$$, can we somehow find $$$G(y) = \sum\limits_{k=1}^\infty h(n, k){y}^{k}$$$ (that is, find $$$h(n, k)$$$ for fixed $$$n$$$ and $$$1 <= k <= n$$$)?

In your blog you have done the particular case with cycles and permutations, my example in comment above is about connected functional graphs and arbitrary functional graphs (it is just another example of relation "block" — "set of blocks").

Ok, so, as I understand, your question is essentially as follows:

Let $$$F(x, y) = e^{y D(x)} = H(x)^y$$$. Then, $$$[y^k] F(x, y) = \frac{D(x)^k}{k!}$$$, but what about $$$G(y) = \left[\frac{x^n}{n!}\right] F(x, y)$$$?

That's indeed an interesting generalization, and the blog doesn't offer any direct solutions. And I don't know any solution to it yet, unfortunately. Given that the problem has $$$n \leq 5000$$$ constraint, it also likely expects some quadratic, DP-based solution. But I will think of how to do it.

Yeah, you're right — that is exactly what I wanted to ask! Coming back to the CSES problem: yes, intended solution is hardly related to generating functions, I've just tried the straightforward exponential formula approach and came to the question of existance of some general methods of computing $$$h(n, k)$$$ for fixed $$$n$$$ or fixed $$$k$$$, that is why I'm here :)

I asked this on Mathoverflow (here), and was told that the problem is essentially equivalent to computing a particular polynomial in a binomial type sequence.

I also noted that we can find the value of $$$G(k)$$$ in any particular $$$k$$$ point by computing $$$[x^n] H(x)^k$$$, from which we could interpolate it in $$$O(n \log^2 n)$$$.

Well, the problem with this is that, apparently, finding $$$[x^n] H(x)^k$$$ for $$$k=1..n$$$ is a transposed problem to polynomial composition, for which best known algorithms are somewhere in $$$O(n \sqrt n \log n)$$$ range, meaning that there might be no efficient general-case algorithm.

Thanks a lot for your efforts!

This problem is a great example of case when one should give the straightforward generating functions approach up — the computational part of the solution is neither simple, nor fast enough.

Блог пользователя adamant

Definitions

Generating functions

Stirling numbers of the second kind

Fixed $$$k$$$

Fixed $$$n$$$

Stirling numbers of the first kind

Fixed $$$k$$$

Fixed $$$n$$$