The number ${n \choose k}$ of $k$-element subsets of an $n$-element set and the number $\left( {n \choose k} \right)$ of $k$-element multisets of an $n$-element set satisfy the reciprocity formula

$\displaystyle {-n \choose k} = (-1)^k \left( {n \choose k} \right)$

when extended to negative integer indices, for example by applying the usual recurrence relations to all integers. There's an interesting way to think about the "negative cardinalities" involved here using Euler characteristic, which is due to Schanuel; see, for example, this paper of Jim Propp. Another (related?) way to think about this relationship is in terms of the symmetric and exterior algebras; see, for example, this blog post.

The number $S(n, k)$ of $k$-block partitions of a set with $n$ elements and the number $c(n, k)$ of permutations of a set with $n$ elements with $k$ cycles satisfy a well-known inverse matrix relationship, but they also satisfy the reciprocity formula

$c(n, k) = S(-k, -n)$

when extended to negative integer indices, again by applying the usual recurrence relations.

Question: Are there any known highbrow interpretations of this reciprocity formula?


Supplementary Exercise 3.2(d,e) on page 313 of my book Enumerative Combinatorics, vol. 1, second printing, shows that this Stirling number reciprocity is a special case of the reciprocity theorem for order polynomials (Exercise 3.61(a)). Thus it is related to a lot of "highbrow" math, such as the reciprocity between a Cohen-Macaulay ring and its canonical module. (For the basic properties of canonical modules, see Section I.12 of my other book Combinatorics and Commutative Algebra, second ed.)

  • 5
    $\begingroup$ I think I would have answered this question "well, it's probably in Volume 1 of Stanley". But I see I don't have to do that. $\endgroup$ – Michael Lugo Dec 25 '09 at 18:56

Another interpretation (which is essentially the same as Richard's example of order polynomials if uses order polytopes) is via Ehrhart reciprocity (Stanley Enumerative Combinatorics 1, Section 4.6). This says that if P is an integral polytope, the number of integer points in tP for positive integers t is a polynomial $L_P(t)$, and its we have the identity $L_P(-t) = (-1)^d L_{P^\circ}(t)$ where $d = \dim P$ and $P^\circ$ denotes the interior of P. Now apply this result to the standard k-simplex $\Delta$ to get the identity

$\left( \binom{-t+1}{k} \right) = L_\Delta(-t) = (-1)^d L_{\Delta^\circ}(t) = (-1)^k \binom{t-1}{k}$,

and replace t by 1-n.

Thinking back to the exact sequence you have in your blog, my comment mentioned it as a special case of a "Schur complex." It's also a linear strand (pulling out some linear part) of the Koszul complex for a polynomial ring, which is a special case of "Priddy complexes" (for example, Eisenbud, Commutative Algebra, exercise 17.22, and the references therein). From a different point of view, it's a linear strand of the Chevalley-Eilenberg complex for an Abelian Lie algebra (Weibel, An Introduction to Homological Algebra, Section 7.7).


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.