Saturday, 17 October 2009

co.combinatorics - Highbrow interpretations of Stirling number reciprocity

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?

No comments:

Post a Comment