1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Oh, I see. So for the first equation you wrote, does it follow from Burnside's Lemma? If so, how? Where do the signs come in? $\endgroup$ – Nishant Apr 17 '14 at 21:52
-1
$\begingroup$

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)$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.