http://akc.is http://akc.is/feed.atom Anders Claesson anders.claesson@gmail.com 2017-02-18T00:00:00Z akc.is/blog http://akc.is/blog/2017-02-18-Inverse-species-and-sign-reversing-involutions.html 2017-02-18T00:00:00Z 2017-02-18T00:00:00Z Inverse species and sign-reversing involutions

Given a finite set $$U$$ with $$n\geq 1$$ elements, how would you prove that there are as many subsets of $$S$$ with even cardinality as there are with odd cardinality? One way is to use the binomial theorem: $0^n = (1-1)^n = \sum_{k=0}^n{n \choose k}(-1)^k = \sum_{\text{k even}}{n \choose k} - \sum_{\text{k odd}}{n \choose k}.$ This identity also holds when $$n=0$$, for $$0^0=1$$ and there is exactly one subset of the empty set, and its cardinality is even. So that’s a neat proof, but not very combinatorial. For a more combinatorial proof we can use a so called sign-reversing involution.

A function $$f:X\to X$$ is an involution if it is its own inverse, or, in symbols, $$f(f(x))=x$$. Assume that a function $$\epsilon:X\to\{-1,1\}$$ is given. We refer to $$\epsilon(x)$$ as the sign of $$x$$. Now, $$f$$ is a sign-reversing involution if for each non fixed point $$x$$ in $$X$$ the sign of $$x$$ is reversed by $$f$$; that is, $$\epsilon(f(x))=-\epsilon(x)$$. If $$f$$ is a sign-reversing involution of $$X$$, then $\newcommand{Fix}{\mathrm{Fix}} \sum_{x\in X}\epsilon(x) = \!\!\sum_{x\in \Fix(f)}\!\!\!\epsilon(x),$ where $$\Fix(f)=\{x\in X: f(x)=x\}$$ denotes the set of fixed points of $$f$$. This is because, under $$f$$, each negative non fixed point is paired with a unique positive non fixed point, and vice versa. For counting purposes we usually also require that all fixed points of $$f$$ have the same sign, and then the right hand sum is $$\pm|\Fix(f)|.$$

When counting subsets $$S$$ of $$U$$ with respect to parity, a natural sign function is $$\epsilon(S) = (-1)^{|S|}$$. Assuming $$U$$ is equipped with a total order and that $$\hat 0$$ denotes the smallest element of $$U$$, a sign reversing involution is given by $f(S) = \begin{cases} S \setminus \{\hat 0\} & \text{if \hat 0\in S}, \\ S \cup \{\hat 0\} & \text{if \hat 0\notin S }. \end{cases}$ For instance, if $$U=\{1,2\}$$ then $$f(\emptyset)=\{1\}$$, $$f(\{1\})=\emptyset$$, $$f(\{2\})=\{1,2\}$$, and $$f(\{1,2\})=\{2\}$$. Note that $$f$$ is fixed point free; thus $$\Fix(f)=\emptyset$$ and $\#\{S\subseteq U: \text{|S| even}\} - \#\{S\subseteq U: \text{|S| odd}\} = |\Fix(f)| = 0.$ Now, that’s a simple and beautiful proof, but is there a more general and “natural” combinatorial proof? E.g. do we have to assume a total order on $$U$$ and do we have to mention special elements, such as $$\hat 0$$? Before proceeding to the next paragraph you might want to take a moment and try to come up with such a proof.

Let $$E$$ be the combinatorial species of sets, defined by $$E[U]=\{U\}$$. Its exponential generating function is $$E(x)=e^x$$, and its multiplicative inverse is the virtual species $$E^{-1}$$ such that $$E\cdot E^{-1}=1$$, where $$1[U]=\{U\}$$ if $$U=\emptyset$$ and $$1[U]=\emptyset$$ otherwise. Note that $E^{-1} = (1+E_+)^{-1} = \sum_{k\geq 0} (-1)^k(E_+)^k,$ where $$E_+$$ denotes the species of nonempty sets. Thus, $$E^{-1}$$ is the species of signed ballots (also called ordered set partitions), where the sign of a ballot $$B_1 B_2\dots B_k$$ is $$(-1)^k$$; that is, the parity of the number of blocks. For instance, $$\{d\}\{a,c,e\}\{b\}$$ is a ballot of $$U=\{a,b,c,d,e\}$$ and its sign is $$(-1)^3=-1$$.

The species of subsets $$\newcommand{\Pow}{\mathfrak{P}}\Pow$$ is defined by $$\Pow[U]=\{(S,U\setminus S): S\subseteq U\}$$. Note that $(E \cdot E)[U] = \bigcup_{S\subseteq U} E[S] \times E[U\setminus S] = \bigcup_{S\subseteq U} \{S\} \times \{U\setminus S\} = \Pow[U].$ That is, $$\Pow=E^2$$ and its exponential generating function is $\Pow(x)=E(x)^2 = e^{2x}=\sum_{n\geq 0}2^n \frac{x^n}{n!}.$ Further, counting subsets with respect to the sign $$(-1)^{|S|}$$ we get $E(x)E(-x) = e^{x}e^{-x} = e^0 = 1.$ Thus, the species interpretation of there being as many subsets of even cardinality as of odd cardinality is $$E\cdot E^{-1}=1$$, where the $$1$$ on the right hand side stems from the case when the underlying set is empty. We will give a combinatorial proof of this species identity using a sign-reversing involution. The objects of $$E\cdot E^{-1}$$ are pairs $$(S, \beta)$$ such that $$S\subseteq U$$ and $$\beta=B_1 B_2\dots B_k$$ is a signed ballot of $$U\setminus S$$. For example, $$(E\cdot E^{-1})[\{a,b,c\}]$$ consists of the pairs $\begin{array}{c|c} \text{positive pairs} & \text{negative pairs} \\ (\{a,b,c\}, \emptyset) & (\emptyset,\{a,b,c\}) \\ (\emptyset, \{a\}\{b,c\}) & (\{a\}, \{b,c\}) \\ (\emptyset, \{b\}\{a,c\}) & (\{b\}, \{a,c\}) \\ (\emptyset, \{c\}\{a,b\}) & (\{c\}, \{a,b\}) \\ (\emptyset, \{a,b\}\{c\}) & (\{a,b\}, \{c\}) \\ (\emptyset, \{a,c\}\{b\}) & (\{a,c\}, \{b\}) \\ (\emptyset, \{b,c\}\{a\}) & (\{b,c\}, \{a\}) \\ (\{a\}, \{b\}\{c\}) & (\emptyset, \{a\}\{b\}\{c\}) \\ (\{a\}, \{c\}\{b\}) & (\emptyset, \{a\}\{c\}\{b\}) \\ (\{b\}, \{a\}\{c\}) & (\emptyset, \{b\}\{a\}\{c\}) \\ (\{b\}, \{c\}\{a\}) & (\emptyset, \{b\}\{c\}\{a\}) \\ (\{c\}, \{a\}\{b\}) & (\emptyset, \{c\}\{a\}\{b\}) \\ (\{c\}, \{b\}\{a\}) & (\emptyset, \{c\}\{b\}\{a\}) \\ \end{array}$ This suggests the natural sign-reversing involution $f(S,B_1 B_2 \dots B_k) = \begin{cases} (B_1, B_2 B_3 \dots B_k) &\text{if S=\emptyset,}\\ (\emptyset, SB_1 B_2 \dots B_k) &\text{if S\neq\emptyset.} \end{cases}$ The table above is arranged so that pairs on the same row are images of each other under $$f$$.

More generally, if $$F$$ is a species such that $$|F[\emptyset]|=1$$ then the multiplicative inverse, $$F^{-1}$$, is the virtual species of lists $$\alpha_1\alpha_2\dots\alpha_k$$ of nonempty $$F$$-structures in which the sign is $$(-1)^k$$. A proof of $$F\cdot F^{-1}=1$$ is given by the sign-reversing involution $f(\alpha,\alpha_1 \alpha_2 \dots \alpha_k) = \begin{cases} (\alpha_1, \alpha_2 \alpha_3 \dots \alpha_k) &\text{if \alpha\in F[\emptyset],}\\ (\emptyset, \alpha \alpha_1 \alpha_2 \dots \alpha_k) &\text{if \alpha\notin F[\emptyset].} \end{cases}$ It has exactly one fixed point, namely $$(\emptyset, \emptyset)$$.

For more examples of the use of sign-reversing involutions the reader might want to have a look at my paper with Stuart Hannah.

Finally I’d like to thank my friend Bjarki for suggesting that I write this post.

Addendum: Brent Yorgey has pointed out that, while it is true that $$E(-X)=E^{-1}(X)$$, the intuition that $$E(-X)$$ is the species of signed sets only holds in the presence of a linear order on the underlying set. Thus my claim that the sign-reversing involution $$f$$ above constitutes a “natural” proof of the fact that here are as many subsets of a given set $$S$$ with even cardinality as there are subsets of $$S$$ with odd cardinality is wrong. For more details see Brent’s excellent three-part series of posts: part 1, part 2, part 3.

]]>