# 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 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

This is an example in some notes that I worked on. It's a bit involved, and I don't know how to simplify the approach further, so let me just offer a sketch (in particular, I want to try to ignore a bunch of boundary cases which result in awkward constructions that I don't know how to explain well at the moment), which at first glance, looks similar to the approaches sketched above. If a more detailed version is useful, please feel free to contact me by email.

Consider the category $C$ of ordered nonempty finite sets and where $Hom_C(S,T)$ is the set of surjections $f \colon T \to S$ such that $\min f^{-1}(i) < \min f^{-1}(j)$ whenever $i<j$. The idea behind this definition: we might want to work with all surjections but "kill" the bijections, and this is one such way to do it which is closed under composition.

Now consider the category of functors from $C$ to $k$-vector spaces (call these functors $C$-modules), where $k$ is a field. The basic projective $C$-modules $P_n$ are given by

$P_n(S) = k[Hom_C([n],S)]$

where $k[X]$ is the vector space with basis $X$ and $[n] = \{1,\dots,n\}$. Let $k_n$ be the simple $C$-module which assigns $k$ to all sets of size $n$ and $0$ otherwise. We can consider the minimal projective resolution of $k_m$. I claim that it looks like this:

$\cdots \to P_{m+2}^{\oplus c(m+2,m)} \to P_{m+1}^{\oplus c(m+1,m)} \to P_m \to k_m \to 0.$

If you evaluate this sequence on a set of size $n>m$, you will get the desired complex because $\dim_k P_i([n]) = S(n,i)$.

How do we construct such a projective resolution? It is enough to calculate the Ext groups between the different $k_m$ since $Hom(P_n,k_m)$ is $1$-dimensional if and only if $n=m$ and is $0$ otherwise. To do this calculation, we can reduce to calculating the homology of certain simplicial complexes: given $n<m$, define a simplicial complex whose $i-1$ simplices ($i>0$) are chains of morphisms

$[n] \to S_1 \to \cdots \to S_i \to [m]$

and a simplex contains another if it can be obtained by composing morphisms (this is related to the nerve construction of a category except I fix the endpoints). I want to consider the augmented simplicial cochain complex of this, but with a weird caveat: when $i=0$, I want to allow "multiple" empty simplices, which are indexed by the set $Hom_C([n],[m])$. (This is defined this weird way just to incorporate boundary cases correctly.) Anyway, let $H^i$ be the cohomology of this weird complex with coefficients in $k$. Then the claim is that

$Ext^i(k_n, k_m) = H^{i-2}$ for $i>0$.

This follows from modifying an argument of Cibils in

http://dx.doi.org/10.1016/0022-4049(89)90058-3

(the relevant result is Proposition 2.1).

Anyway, the final punchline: these nerve-like things I've introduced are order complexes of truncations of the partition lattice. Specifically, we look at set partitions of the set $[m]$ which have at least $n$ parts and less than $m$ parts. It can be shown that this poset (with a min and max adjoined) is EL-shellable and hence its order complex is homotopy equivalent to a wedge of spheres of maximal dimension (in this case $m - n - 2$ -- let me ignore discussing the case $m-n$ being small). One can calculate the number of spheres from general poset topology tools -- but instead we could appeal to the fact this wedge of spheres fact implies that a complex like I mentioned exists (i.e., a linear resolution and modulo calculating the ranks) and that the ranks have to be the cycle numbers $c$ in order for the Euler characteristic to work out.

-

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.

-