Other natural operations on functions have combinatorial interpretations: composition of functions, taking exponentials or logarithms, differentiation, integration, etc. Even subtraction has an interpretation, although one has to be careful: this is the "virtual species". (A virtual species is a pair of ordinary species (F, G), written as F-G, where (F, G) = (H, K) if F + K = G + H. Replacing species with integers and addition with multiplication, this looks like the construction of the rational numbers from the integers.)
But is there a natural quotient operation? If there is, I can't find a mention of it in Flajolet and Sedgewick, and Marko Petkovsek (who I was just talking about this with) tells me it's not in Bergeron et al. either; this is one of the sources he's using for our current topics course in combinatorics. Let F be a species with 1 structure on the set of size 0, and let Fn be its restriction to size n. Let F+ be its restriction to all positive sizes. Then
where 1 is the multiplicative identity species (hence the name); it has one structure on a set of size 0. We can of course write this as
and we collect the "positive" and "negative" terms to get
So the inverse of the species F exists, and it's a virtual species in which the positive part is even-length tuples of nonempty F-structures, and the negative part is odd-length tuples of nonempty F-structures. This doesn't quite seem like a "combinatorially natural" operation -- but on the other hand I was able to describe it in a single sentence, so it seems plausible that it could be a natural thing to occur somewhere.
Notice that this also proves that if
and F(z)G(z) = 1, f0 = 1, then all the gn are integers, since the generating function G(z) actually counts something! (Well, a virtual something -- but that's close enough. It won't surprise you to learn that for two species H and K, the generating function corresponding to the virtual species H-K is H(z) - K(z). G here is a virtual species, so the gn are (possibly negative) integers. Of course, there are other ways to prove this, but I think this is a cute "combinatorial proof".
4 comments:
As you're surely learning in those lecture notes of Baez', generating functions naturally live in $\mathbb{N}[X]$ -- the rig of power series with natural number coefficients. It's possible to adjoin negatives (moving to $\mathbb{Z}$) and get a ring, but it's really hard to turn this ring into a field in a natural way. That, to me, explains the difficulty of interpreting division.
You mean "as you surely will learn in those lecture notes of Baez' when you have time to read them". (I keep looking for references to various things online and keep coming across them, though, so they're moving higher and higher on the list.)
But that did occur to me on the walk home tonight. The obvious way to try to turn the ring into a field is to just start dividing power series formally, but unless all your power series have constant term 1 then one starts getting rational coefficients which aren't integers. But the power series with constant term 1 aren't closed under addition.
There's a notion of "weighted species" that comes up here in the theory of combinatorial species -- basically instead of counting each species once we count it with a weight drawn from some ring. (The weights don't have to be numbers -- often the weight of some structure s is t^{f(s)} where t is just another formal variable and f is some statistic on structures.) One could probably form a field of weighted species with weights in the rationals -- but that just seems too artificial to me. (And it may not actually be possible; defining subtraction on species is surprisingly nontrivial.)
Natural numbers have obvious interpretations as cardinalities. Negative numbers have a less-obvious interpretation that you mentioned in the post. But if you're going to divide like that, then what the hell does a rational cardinality mean?
Not saying the question doesn't have an answer, but that's the hard conceptual nut here.
The usual way to get rational-like objects is to look at G-sets: a set X which carries an action of the finite group G can be productively thought of as having cardinality |X| / |G| even if the action of G is not nice. For example, it is pretty reasonable to think of [-1,1] mod negation as an interval with a "half point" on the right end. The Euler characteristic of the quotient is (1/2 + 1) - 1 = 1/2, reflecting the fact that it is covered 2-1 by a space of Euler characteristic 1.
Post a Comment