2

I've seen that $n!=\displaystyle\sum_{p=0}^n s(n, p)n^p$, where $s(n, p)$ are the signed Stirling Numbers of the First Kind, whose absolute values count the number of permutations in $S_n$ which have $p$ cycles in their cycle decomposition. Of course, this means that $n!=\displaystyle\sum_{p=0}^n \lvert s(n, p)\rvert $. So how do the signs and the $n^p$ come in for the second formula? It strongly resembles something that would come from Burnside's Lemma and the Polya Enumeration Theorem, but I'm not exactly sure how those apply, since there are usually not negative numbers in the sum when you use those Theorems.

RobPratt
  • 45,619
Nishant
  • 9,155
  • 2
    It might be more insightful to consider showing $(x)n=\sum{k=0}^n s(n,k)x^k$. – Pedro Apr 18 '14 at 20:04
  • I actually got my identity by letting $x=n$. Does the formula not have anything to do with Polya/Burnside, then? – Nishant Apr 18 '14 at 20:41
  • 2
    I don't see any obvious relation (but that doesn't mean there isn't one). My first instinct is it might be more of an inclusion/exclusion type of deal. – Alexander Gruber Apr 18 '14 at 22:55
  • I believe it would be difficult to get an argument via burnside's lemma for $(x)n=\sum{k=0}^ns(n,k)x^k$. Instead, we have a combinatorial argument for the equivalent $(x+n-1)n=\sum{k=0}^nc(n,k)x^k$ (where $c(n,k)$ is the unsigned stirling number of the first kind) . The latter equation can be obtained from the former by replacing $x$ by $-x$ and dividing by $(-1)^n$. http://math.stackexchange.com/questions/162151/stirling-numbers-of-the-first-kind-a-direct-derivation – talegari Apr 20 '14 at 11:54
  • You ask how signs and $n^p$s come into play in the second formula, but ... I don't see signs or $n^p$s anywhere in the second formula? – anon Jun 23 '14 at 06:57
  • Sorry, I think what I actually meant to ask was how moving from the $2$nd to the $1$st formula picks up signs and $n^p$. – Nishant Jun 23 '14 at 14:05

2 Answers2

2

EDIT: exponential formula vs Burnside.

Marko Riedel
  • 61,317
0

Consider how $S_n$ acts on the set of colorings of $\{1,\dots, n\}$ in $x$ colors.

The orbit of a coloring corresponds to the unordered set of colors in the coloring, thus the number of orbits, counted directly, is

$$ \binom{x+n-1}{n}=\frac{1}{n!}(x)^n, $$

which is also known as the number of $n$-combinations with repetitions.

On the other hand, due to Burnside lemma, the number of orbits is the average number of fixed points:

$$ \frac{1}{n!} \sum\limits_{k=1}^n |s(n, k)| x^k, $$

as the number of fixed points for a permutation with $k$ cycles is $x^k$. From this, we get

$$ (x)^n = \sum\limits_{k=1}^n |s(n, k)|x^k, $$ which is the property that we needed to show for unsigned Stirling numbers. Then, changing $(x+k)$ to $(x-k)$ in the product fixes the signs for signed Stirling numbers. I'm not sure how to get signed version from the Burnside's lemma directly though...

Oleksandr Kulkov
  • 843