Stirling number identity via homology? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T12:52:07Z http://mathoverflow.net/feeds/question/79302 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/79302/stirling-number-identity-via-homology Stirling number identity via homology? Gary Kennedy 2011-10-27T19:34:44Z 2012-07-13T00:05:26Z <p>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$.</p> <p>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.</p> http://mathoverflow.net/questions/79302/stirling-number-identity-via-homology/79305#79305 Answer by Mariano Suárez-Alvarez for Stirling number identity via homology? Mariano Suárez-Alvarez 2011-10-27T20:17:39Z 2011-10-27T21:12:07Z <p>This should be a comment, <strong>mostly</strong> because I have not checked...</p> <p>Fix $n$ and consider only $m=1$. For a natural number $\ell$ let $[\ell]=\lbrace 1,\dots,\ell\rbrace$.</p> <p>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 <strong>I think that</strong> in this way $X_\flat(n)$ becomes a <em>cyclic vector space</em> (a cyclic object in the category of vector spaces) in the sense of Alain Connes; see Jean-Louis Loday's book on cyclic homology.</p> <p>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).$$</p> <p>It follows that you are almost trying to compute the Euler characeristic of the complex $C^\lambda$.</p> <p>I don't have paper at hand (and this margin &amp;c) so I cannot try now: but one knows that the homology of $C^\lambda$ can be obtained from a different complex, Connes' <em>cyclic bicomplex</em> or his <em>triangular complex</em>. Maybe the homology of those complexes can be readily computed, and that would do pretty much what you want.</p> http://mathoverflow.net/questions/79302/stirling-number-identity-via-homology/80500#80500 Answer by Dimitrije Kostic for Stirling number identity via homology? Dimitrije Kostic 2011-11-09T17:47:07Z 2011-11-09T19:57:57Z <p>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.</p> http://mathoverflow.net/questions/79302/stirling-number-identity-via-homology/101255#101255 Answer by David Speyer for Stirling number identity via homology? David Speyer 2012-07-03T20:38:01Z 2012-07-13T00:05:26Z <p>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$.</p> <p>I now present a <strike>regular</strike> 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.</p> <p>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}$.</p> <p>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$.</p> <p>Then <code>$$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 &gt;0 {\Large \}}$$</code>. Clearly, $U^{\circ}$ is the interior of the ball <code>$$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 \}}$$</code></p> <p>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.</p>