# Stirling number identity via homology?

This is a question about the well-known formula involving both types of Stirling numbers: $\sum_{k=1}^{\infty}(-1)^{k}S(n,k)c(k,m)=0$, where $S(n,k)$ is the number of partitions of an $n$-element set into $k$ blocks, and $c(k,m)$ is the number of permutations of a $k$-element set having $m$ cycles. I assume that $n \neq m$. The question is whether there is a known proof of the formula of the following nature: (1) there is a complex of vector spaces with ranks $S(n,k)\cdot c(k,m)$, (2) the complex is exact. I would be interested in a general answer or, if it makes the situation simpler, just an answer that applies in case $m=1$.

The context is this: I am trying to work out, in algebraic geometry, an effective method of computing the Severi degrees for plane curves of specified genus and number of nodes. The method depends on constructing an analogous homological argument for which the Stirling number argument (if it exists) would provide a prototype.

-
Can every alternating sum be computed by a homological argument? –  Igor Rivin Oct 27 '11 at 20:18
Igor, if a finite alteranting sum of integers has value zero, you can find an exact complex $X$ of finite dimensional vector spaces which turns that equality to zero into the statement «the Euler characteristic of $X$ is zero». –  Mariano Suárez-Alvarez Oct 27 '11 at 20:24
(...a finite alternating sum of positive integers...) –  Mariano Suárez-Alvarez Oct 27 '11 at 20:25
Apropos I.Rivin's comment: a test case is $\sum_{i=0}^n (-1)^i {n \choose i}^3$. The sum is known in closed form, and quite nontrivial for $n$ even. Is there a proof via an Euler-characteristic interpretation? –  Noam D. Elkies Nov 9 '11 at 20:46
@Mariano Suárez-Alvarez What about 1-5+1-5+13-5=0? These don't seem to fit into an exact sequence. –  John Wiltshire-Gordon Jul 6 '12 at 20:30

Let $X = S^1 \sqcup S^1 \sqcup S^1 \sqcup \cdots \sqcup S^1$, where there are $m$ disjoint circles. Let $Y \subset X^n$ be the set of $n$ ordered points on $X$ such that there is at least one point on each component. Note that each connected component of $Y$ is isomorphic to $(S^1)^n$. Let the group $G = (S^1)^m$ act on $X$, where the $k$-th factor of $G$ rotates the $k$-th component of $X$. So $G$ acts on $Y$. Also, let $S_m$ act by permuting the factors. Let $Z = S_m\backslash Y/G$. Each component of $Y/G$ is isomorphic to $(S^1)^{n-m}$. The $S_m$ action permutes the components, so the quotient is the union of a smaller number of copies of $(S^1)^{n-m}$. So we see that $\chi(Z)=0$ for $n-m>0$.

I now present a regular CW structure on $Z$ so that the number of $k-m$ cells is $S(n,k) c(k,m)$, proving your identity. A given cell of $Z$ will correspond to those arrangements of points on $X$ which lie in a given cyclic order. So, to specify a cell of $Z$, we need to say (1) which points are equal to each other and (2) how to arrange those piles of points around circles. The number of ways to group $n$ points into $k$ equality classes is $S(n,k)$ and the number of ways to arrange those $k$ classes around $m$ circles is $c(k,m)$. We now need to see that this is a triangulation.

So, fix a partition of $[n]$ into $k$ blocks, and an arrangement of those blocks around $m$ circles. Let $U^{\circ}$ be the set of points in $Z$ with that configuration, and let $U$ be the closure of $U$. We need to see that $U^{\circ}$ is the interior of a ball and there is a continuous map from the closed ball to $Z$ extending the inclusion of $U^{\circ}$.

Choose coordinates on $U^{\circ}$ to be the angles between the blocks. Let the number of blocks on the $i$-th circle be $c_i$, so we'll write $\theta_1^i$, $\theta_2^i$, ..., $\theta_{c_i}^i$ for the coordinates coming from the $i$-th circle. So $\sum_{i=1}^m c_i = k$ and $\sum_{r=1}^{c_i} \theta_r^i = 2 \pi$ for each $i$.

Then $$U^{\circ} = \prod_{i=1}^m {\Large \{} (\theta_1^i, \theta_2^i, \ldots, \theta_{c_i}^i) : \sum_r \theta_r^i = 2 \pi, \ \theta_r^i >0 {\Large \}}$$. Clearly, $U^{\circ}$ is the interior of the ball $$U := \prod_{i=1}^m {\Large \{} (\theta_1^i, \theta_2^i, \ldots, \theta_{c_i}^i) : \sum_r \theta_r^i = 2 \pi, \ \theta_r^i \geq 0 {\Large \}}$$

It is also easy to build a map $U \to Z$ extending the inclusion of $U^{\circ}$. It is not quite an injection: Whenever there is an $i$ such that every $\theta^i_r$ is either $0$ or $2 \pi$, the various points which are formed by moving the position of the $2 \pi$ will be identified.

-
Edited because the complex isn't quite regular. –  David Speyer Jul 3 '12 at 23:02
Don't we also need the symmetric group on m elements to act? For example, if n=3 and m=2 then we're supposed to have 3 zero-cells rather than 6. –  Gary Kennedy Jul 12 '12 at 20:38
You are right. Which is sad, because now it is less obvious that $\chi=0$. I'll note in my defense that the original post said I only had to give a proof for $m=1$ :). –  David Speyer Jul 13 '12 at 0:02

This should also be a comment. Most combinatorialists (for example, Enumerative Combinatorics, v.1, by R.P. Stanley, page 18) define the Stirling numbers of the first kind to be $s(k,m) := (-1)^{(k-m)}c(k,m)$. With that definition, you have the identity $\sum_{k \geq 0} S(n,k)s(k,m) = \delta_{n,m}$ (ibid., p. 35). The sum you give does not always yield 0. When $n=2$ and $m=1$, for example, it equals 2.

-

This should be a comment, mostly because I have not checked...

Fix $n$ and consider only $m=1$. For a natural number $\ell$ let $[\ell]=\lbrace 1,\dots,\ell\rbrace$.

Let $X_k(n)$, for each $k\geq0$, be the vector space with basis the set of all functions surjective $[n]\to[k+1]$. Then $X_\flat(n)$ is a simplicial vector space (with simplicial operations acting on $[k+1]$). We can do better: for each $k\geq0$, there is an endomorphism $t_k:X_k(n)\to X_k(n)$ such that $t_k^{k+1}=\mathrm{id}$, given simply by rotation in $[k+1]$. The map $t_k$ plays nicely with the simplicial structure and I think that in this way $X_\flat(n)$ becomes a cyclic vector space (a cyclic object in the category of vector spaces) in the sense of Alain Connes; see Jean-Louis Loday's book on cyclic homology.

Now if the underlying field is of characteristic zero, the Connes' complex $C^\lambda$ corresponding to the cyclic vector space $X_\flat(n)$ has $C^\lambda_k=X_k(n)/(1-t_k)$; i other words, we identify things with their image under $t_k$. Elements of this vector space are functions $[n]\to[k+1]$ up to a rotation in $[k+1]$, which is the same thing as a partition of $[n]$ in $k+1$ labeled parts, up to a cyclic rotation of the labeling. There are $S(n,k+1)(k+1)!$ labeled partitions of $[n]$ into $k+1$ parts, and when we look at them up to rotation in $[k+1]$ we get $S(n,k+1) k!$. Now $c(k+1,1)=k!$, so in the end $$\dim C^\lambda_k=S(n,k+1)c(k+1,1).$$

It follows that you are almost trying to compute the Euler characeristic of the complex $C^\lambda$.

I don't have paper at hand (and this margin &c) so I cannot try now: but one knows that the homology of $C^\lambda$ can be obtained from a different complex, Connes' cyclic bicomplex or his triangular complex. Maybe the homology of those complexes can be readily computed, and that would do pretty much what you want.

-
In any case, very nice question! –  Mariano Suárez-Alvarez Oct 27 '11 at 20:31
(I may have defined a co cyclic object, but the cyclic category is isomorphic to its dual.) –  Mariano Suárez-Alvarez Oct 27 '11 at 20:36
I haven't absorbed your answer yet, but wow: I'm really impressed with how MathOverflow works! This was my first time to dip my toes in the water here. –  Gary Kennedy Oct 27 '11 at 23:22
'margin' - nice one :) –  David Roberts Jul 3 '12 at 23:29