Stirling Numbers of the First Kind and $S_n$.

478 Views Asked by At

I know that, on the one hand, if $s(n, p)$ denotes the unsigned Stirling Numbers of the First Kind, then $(x)_n=\displaystyle\sum_{p=0}^n s(n, p)x^p$, where $(x)_n=x(x-1)\cdots(x-n+1)$. It follows that $n!=\displaystyle\sum_{p=0}^n s(n, p)n^p$.

But I also know that $s(n, p)$ counts the number of permutations in $S_n$ that can be written as the product of $p$ disjoint cycles, so shouldn't $n!=\displaystyle\sum_{p=0}^n s(n, p)$, instead?

2

There are 2 best solutions below

1
On

The Stirling numbers of the first kind, $s(n,p)$, count the number of permutations in $S_n$ that are a product of $p$ disjoint cycles, but you are forgetting about sign! The relevant identities are:

$$n!=\sum_{p=0}^n s(n,p)n^p$$ and $$n!=\sum_{p=0}^n |s(n,p)|.$$ Often the symbol $\left[{n\atop p}\right]$ is used to denote $|s(n,p)|$, the unsigned Stirling numbers of the first kind. The reason why we define the Stirling numbers of the first kind $s(n,k)$ to be signed is because then the infinite matrices $(s(n,k))_{k,n\in\mathbb N}$ and $(S(n,k))_{n,k\in\mathbb{N}}$ (where $S(n,k)$ are the Stirling numbers of the second kind) which are lower and upper triangular respectively, form a change of basis matrix pair (they are inverses of each other) that allow us to move from the power series basis of polynomials $1,x,x^2,\dots$ to umbral calculus basis $(x)_0,(x)_1,(x)_2,\dots$.

0
On

You've got the sum wrong. It is: $$ x^{\overline{n}} = \sum_{0 \le p \le} \genfrac{[}{]}{0pt}{}{n}{p} x^p $$ (i.e., on the left hand side you have $x (x + 1) \ldots (x + n - 1)$).