5. Sieving

5.1Mobius Inversion and Inclusion-Exclusion

在这一章中, 我们主要考虑一些会出现 " 减号 " 的组合问题. 准确来说, 我们会考虑组合中十分传统的容斥原理, 然后其组合物种的扩展. 同时, 我们还会考虑矩阵树定理的一些应用和棋盘多项式.

Definition 5.1.1. For poset $(P,\le )$, for $\alpha ,\beta \in P$ define interval $[\alpha ,\beta ]:=\{\gamma \in P:\alpha \le \gamma \le \beta \}$.

Definition 5.1.2. We say poset $(P,\le )$ is locally finite if all intervals are finite.

Remark 5.1.3. In this course we would assume the poset is always locally finite.

Example 5.1.4.

1.	$(\mathbb{N},\le )$ is locally finite.
2.	$({\mathbb{Z}}_{+},\mid )$ is locally finite where $\mid$ is divisibility, e.g. $3\mid 6$ and $3\nmid 5$.
3.	Consider $({\mathcal{P}}_f(X),\subseteq )$, where ${\mathcal{P}}_f(X)$ is the set of all finite subsets of $X$ with $X$ any fixed set.
4.	Consider $(\mathcal{P},\subseteq )$ where $\mathcal{P}$ is the set of all partitions, with $\subseteq$ the “diagram containment” relation. (Example deleted since I don’t want to include graphics)
5.	Consider $(\Gamma ,⇝)$, where $\Gamma$ is a directed acyclic graphs, and $u⇝v$ means there exists a directed path from $u$ to $v$.

Definition 5.1.5 (Mobius Function). Let $(P,\le )$ be a poset. Define $\mu :P\times P\to \mathbb{Z}$ recursively as follows:$$\mu (\alpha ,\beta ):=\{\begin{array}{l}1,\alpha =\beta \\ 0,\alpha \nleqq \beta \\ -{\sum }_{\gamma \in [\alpha ,\beta ]\backslash \{\beta \}}\mu (\alpha ,\gamma ),\alpha <\beta \end{array}$$

Example 5.1.6. Classical Mobius function $({\mathbb{Z}}_{+},\mid )$ given by$$\mu (d,n)=\{\begin{array}{l}(-1{)}^{\text{number of prime factors of }n/d},\text{ if }n/d\text{ is square-free integer}\\ 0,\text{otherwise}\end{array}$$Since the RHS depends only on $n/d$, we write $\mu (\frac{n}{d})=\mu (d,n)$.

Theorem 5.1.7. Let $(P_1,{\le }_1)$ and $(P_2,{\le }_2)$ be two posets, then we can define poset $(P_1\times P_2,\le )$ by $(a,b)\le (c,d)$ iff $a{\le }_{1}c,b{\le }_{2}d$. Then we have$${\mu }_{P_1\times P_2}((a,b),(c,d))={\mu }_{P_1}(a,c)\cdot {\mu }_{P_2}(b,d)$$

Theorem 5.1.8 (Mobius Inversion, Version I). Let $R$ be a ring, $f,g:P\to R$ with $(P,\le )$ a poset. The following are equivalent:

1.	$f(\alpha )={\sum }_{\alpha \le \beta }g(\beta )$ for all $\alpha \in P$.
2.	$g(\alpha )={\sum }_{\alpha \le \beta }\mu (\alpha ,\beta )f(\beta )$ for all $\alpha \in P$.

where we assume the sums are finite, or $R$ is a valuation ring and sums are convergent.

Proof. We are going to prove the case when $P$ is finite. Consider the poset incidence function $\zeta :P\times P\to \mathbb{Z}$ by$$\zeta (\alpha ,\beta )=\{\begin{array}{l}1,\alpha \le \beta \\ 0,\text{ otherwise}\end{array}$$Then we can think $\mu ,\zeta$ as matrices where the rows and columns are indexed by $P$. Then the definition of $\mu$ is equivalent to $\mu \zeta =\mathrm{I}\mathrm{d}$ is the identity matrix. Then we see $(1)$ if and only if $f=\zeta g$ and $(2)$ if and only if $g=\mu f$, where we consider $f,g$ are vectors. Thus the proof follows.

$\square$

Corollary 5.1.9 (Mobius Inversion, Version II). With the same setting as above, the following are equivalent:

1.	$f(\beta )={\sum }_{\alpha \le \beta }g(\alpha )$ for all $\beta \in P$.
2.	$g(\beta )={\sum }_{\alpha \le \beta }f(\alpha )\mu (\alpha ,\beta )$ for all $\beta \in P$.

where we assume the sums are finite or $R$ is valuation ring with sum convergent.

Proof. The same proof as above, where in this case we use ${\zeta }^T$ and ${\mu }^T$, i.e. $(1)$ iff $f={\zeta }^{T}g$ and $(2)$ iff $g={\mu }^{T}f$.

$\square$

Remark 5.1.10 (Inclusion-Exclusion). Now consider $({\mathcal{P}}_f(X),\subseteq )$, we want to compute the Mobius inversion on this poset. It is not hard to see$$\mu (\alpha ,\beta )=\{\begin{array}{l}(-1{)}^{|\alpha |-|\beta |},\alpha \subseteq \beta \\ 0,\text{ otherwise}\end{array}$$

Now we discuss the combinatorial set-up of this. Let $\mathcal{S}$ be a set of objects, $\mathcal{T}\subseteq \mathcal{S}$ be the set of “good” objects with $\mathcal{B}$ the set of “flaws” (that exclude an object from being “good”).

For $S\in \mathcal{S}$, we can define $Flaws(S)=\{b\in \mathcal{B}:S\text{ has flaw }b\}\in {\mathcal{P}}_f(\mathcal{B})$.

For $\alpha \in P_f(\mathcal{B})$, we can define ${\mathcal{F}}_{\alpha }:=\{S\in \mathcal{S}:Flaws(S)\supseteq \alpha \}$, which is the set of objects with flaws $\alpha$, and possibly others. We can also define ${\mathcal{G}}_{\alpha }$ as $\{S\in \mathcal{S}:Flaws(S)=\alpha \}$. We note ${\mathcal{F}}_{\varnothing }=\mathcal{S}$ and ${\mathcal{G}}_{\varnothing }=\mathcal{T}$.

Then the basic formulation with $\mathcal{S}$ finite is that, $f,g:{\mathcal{P}}_f(\mathcal{B})\to \mathbb{Z}$, with $f(\alpha )=|{\mathcal{F}}_{\alpha }|$, $g(\alpha )=|{\mathcal{G}}_{\alpha }|$. Then we have a theorem as follows:$$g(\alpha )=\sum _{\alpha \subseteq \beta }(-1{)}^{|\beta |-|\alpha |}f(\beta )$$

Indeed, by construction, $f(\alpha )={\sum }_{\alpha \subseteq \alpha }g(\beta )$ and so by Mobius inversion on $({\mathcal{P}}_f(\mathcal{B}),\subseteq )$ the result follows.

In particular, we see $|\mathcal{T}|=g(\varnothing )={\sum }_{\beta \subseteq B}(-1{)}^{|\beta |}f(\beta )$.

Example 5.1.11 (Derangements). Let $\mathcal{S}=S_n$ be permutations of $[n]$, $\mathcal{T}\subseteq \mathcal{S}$ be the set of derangements. Then the flaws are $\sigma (1)=1,\sigma (2)=2,...,\sigma (n)=n$. In other word, we can think the set $\mathcal{B}=\{1,...,n\}$. Then $Flaws(\sigma )=\{i\in [n]:\sigma (i)=i\}$. Then$${\mathcal{F}}_{\alpha }=\{\sigma \in S_n:\forall i\in \alpha ,\sigma (i)=i\}$$and hence $f(\alpha )=|{\mathcal{F}}_{\alpha }|=(n-|\alpha |)!$ Thus, we get$$|\mathcal{T}|=\sum _{\beta \subseteq [n]}(-1{)}^{|\beta |}(n-|\beta |)!=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})(-1{)}^k(n-k)!=n!\sum _{k=0}^n\frac{(-1{)}^k}{k!}$$

Example 5.1.12 (Rook Polynomials).

Consider $[n]\times [n]$ as the squares of a $n$ by $n$ chess board, then a permutation $\sigma \in S_n$ is a placement of $n$ non-attacking rooks on the chess board.

Now we want to look at rook placements with some blocks disallowed, for example,

where we want non-attacking rook placements with none of the rooks placed on the purple blocks.

Formally, let $B\subseteq [n]\times [n]$ be the set of disallowed squares, let ${\mathcal{D}}_B=\{\sigma \in S_n:\forall (i,j)\in B,\sigma (i)\ne j\}$ be the set of placements of non-attacking rooks avoiding $B$. Then we want to compute $|{\mathcal{D}}_B|$.

For this purpose, we define the rook polynomial $R_B(x)={\sum }_{k=0}^n{r}_k{x}^k$ where $r_k$ is the number of ways to place $k$ non-attacking rooks within squares of $B$. Then we have a theorem$$|{\mathcal{D}}_B|=[x^n]R_B(-x)\sum _{j\ge 0}j!x^j$$

To prove this, we apply inclusion-exclusion to $S_n$ with $B$ the set of “flaws”. For $\alpha \subseteq B$, let ${\mathcal{F}}_{\alpha }=\{\sigma \in S_n:\forall (i,j)\in \alpha ,\sigma (i)=j\}$. Then$$f(\alpha )=|{\mathcal{F}}_{\alpha }|=\{\begin{array}{l}(n-|\alpha |)!,\text{ if }\alpha \text{ is an arrangment of non-attacking rooks}\\ 0,\text{ otherwise}\end{array}$$Then we see$$|{\mathcal{D}}_B|=\sum _{\beta \subseteq B}(-1{)}^{|\beta |}f(\beta )=\sum _{k=0}^n(-1{)}^k{r}_k(n-k)!=[x^n]R_B(-x)\sum _{j\ge 0}j!x^j$$

Example 5.1.13 (Menage Problem). The set-up is:

1.	We have $n$ male-female couples.
2.	Seat them around a round table.
3.	No person is next to someone of the same sex.
4.	No person is next to their partner.

Then we want to compute the number of such seatings.

Fix a seating of men in every other seat. Then the number of ways to seat the women is equivalent to count $\sigma \in S_n$, such that $\sigma (i)\ne i,i+1(\mathrm{m}\mathrm{o}\mathrm{d}n)$. This is just the following disallowed squares configuration:

Then by elementary counting, we can show $r_k=\frac{2n}{2n-k}\left(\genfrac{}{}{0ex}{}{2n-k}{k}\right)$ and use the theorem about rook polynomial to get the answer.

Remark 5.1.14 (GF Formulation). Now consider the generating function formulation of the inclusion-exclusion principle. Let $\mathcal{S},\mathcal{T},\mathcal{B},{\mathcal{F}}_{\alpha },{\mathcal{G}}_{\alpha }$ as before.

We introduce a weight function on this set-up. Let $R$ be a ring, $Wt:\mathcal{S}\to R$ be a generalized weight function with $f(\alpha )=|{\mathcal{F}}_{\alpha }{|}_{Wt}={\sum }_{s\in {\mathcal{F}}_{\alpha }}Wt(s)$ and $g(\alpha )=|{\mathcal{G}}_{\alpha }{|}_{Wt}={\sum }_{s\in {\mathcal{G}}_{\alpha }}Wt(s)$. Then our usual goal is to compute $|\mathcal{T}{|}_{Wt}=g(\varnothing )$.

Then we consider the objects with “marked flaws”. Let $\mathcal{F}=\{(s,\alpha ):s\in {\mathcal{F}}_{\alpha }\}$ and $\mathcal{G}=\{(s,\alpha ):s\in {\mathcal{G}}_{\alpha }\}$. We can think of $(s,\alpha )$ as object with marked flaws, where not all flaws need to be marked. Then $\mathcal{G}\subseteq \mathcal{F}$ is the subset in which all flaws are marked. We note we have bijection $\mathcal{G}\iff \mathcal{S}$.

Then we have the inclusion-exclusion principle, full version, as follows: let $\underline{t}=\{t_b:b\in B\}$ be the set of variables. For $\alpha \in {\mathcal{P}}_f(\mathcal{B})$, we write ${\underline{t}}^{\alpha }={\prod }_{b\in \alpha }{t}_b$. Then we define$$\underline{F}(\underline{t}):=\sum _{(s,\alpha )\in \mathcal{F}}Wt(s){\underline{t}}^{\alpha }$$$$\underline{G}(\underline{t})=\sum _{(s,\alpha )\in \mathcal{G}}Wt(s){\underline{t}}^{\alpha }$$Then the theorem says$$\underline{F}(\underline{t}-\underline{1})=\underline{G}(\underline{t})$$where $\underline{t}-\underline{1}$ means substitute $t_b$ by $t_b-1$ for all $b\in B$.

Proof: We see $$\underline{F}(\underline{t})=\sum _{\alpha \in {\mathcal{P}}_f(\mathcal{B})}f(\alpha ){\underline{t}}^{\alpha }$$and$$\underline{G}(\underline{t})=\sum _{\alpha \in {\mathcal{P}}_f(\mathcal{B})}g(\alpha ){\underline{t}}^{\alpha }$$Then we see $$\begin{array}{rl}\underline{F}(\underline{t}-\underline{1})& =\sum _{\beta \in {\mathcal{P}}_f(\mathcal{B})}f(\beta )(\underline{t}-\underline{1}{)}^{\beta }\\ & =\sum _{b\in {\mathcal{P}}_f(\mathcal{B})}f(\beta )\sum _{\alpha \subseteq \beta }(-1{)}^{|\beta |-|\alpha |}{\underline{t}}^{\alpha }\\ & =\sum _{\alpha \in {\mathcal{P}}_f(\mathcal{B})}{\underline{t}}^{\alpha }\left(\sum _{\alpha \subseteq \beta }(-1{)}^{|\beta |-|\alpha |}f(\beta )\right)\\ & =\sum _{\alpha \in {\mathcal{P}}_f(\mathcal{B})}{\underline{t}}^{\alpha }g(\alpha )=\underline{G}(\underline{t})\end{array}$$

We also have the inclusion exclusion principle, simplified version. In this version, we just set all variables $t_b=t$. Then we get $F(t)={\sum }_{(s,\alpha )\in \mathcal{T}}Wt(s)t^{|\alpha |}$ and $G(t)={\sum }_{(s,\alpha )\in \mathcal{G}}Wt(s)t^{|\alpha |}$. Then we have $G(t)=F(t-1)$ and $|\mathcal{T}{|}_{Wt}=F(-1)$.

In some applications, $\mathcal{B}$ can be a set of “features” rather “flaws”. In this case, since $\mathcal{G}$ has bijection to $\mathcal{S}$, $G(t)$ is a generating function for $\mathcal{S}$, where $t$ marks the number of features.

Example 5.1.15. Let $\mathcal{J}$ be the set of $01$-strings where $011$ is not a substring. Then $\mathcal{S}$ is the set of all $01$-strings. Let $\mathcal{F}$ be the set of $01$-strings with $011$ as a substring, may be marked. For example, we have the following are distinct elements of $\mathcal{F}$: $$1(011)00111000$$$$10110(011)1000$$where $(011)$ indicates that part has been marked. Then we see $\mathcal{F}=\{0,1,(011){\}}^{\ast }$ where we use $(011)$ to mean $011$ is marked. Then $F(x,t)=\frac{1}{1-(2x+x^{3}t)}$ where $x$ is mark the length, and $t$ marks the number of marked $011$. Finally, by inclusion exclusion, we get$$T(x)=F(x,-1)=\frac{1}{1-2x+x^3}$$

Remark 5.1.16 (Matrix Tree Theorem). The inclusion-exclusion set-up:

1.	$V$ is a finite set.
2.	$\mathcal{S}$ is the set of all endofunctions from $V\to V$.
3.	$\mathcal{T}$ is the set of endofunctions from $V$ to $V$, where every recurrent element is fixed. In other word, if $\varphi \circ \varphi \circ ...\circ \varphi (v)=v$ then $\varphi (v)=v$. Equivalently, no cycles of length greater than or equal $2$.
4.	Then $\mathcal{F}$ contains $(\varphi ,\alpha )$, where $\varphi :V\to V$ is endofunction and $\alpha$ a set of “marked flaws”, i.e. cycles of length $\ge 2$. For example,
5.	Let $K_V$ be the complete graph with vertex set $V$. Then we consider variable $x_v$ for all $v\in V$, and $y_e$ for $e\in E(K_V)$. Then for $\varphi \in \mathcal{S}$, we define$$Wt(\varphi )=\prod _{v=\varphi (v)}{x}_v\prod _{v\ne \varphi (v)}{y}_{\{v,\varphi (v)\}}$$

With the above set-up, we can state the matrix tree theorem as follows.

Theorem 5.1.17. Let $M$ be the matrix with rows and columns indexed by $V$, then we define$$M_{uv}=\{\begin{array}{l}{x}_v+{\sum }_{w\ne v}{y}_{vw},\text{ if }u=v\\ -y_{vw},\text{ if }u\ne v\end{array}$$Then $|\mathcal{T}{|}_{Wt}=\det (M)$.

Proof. By inclusion-exclusion, we see $|\mathcal{T}{|}_{Wt}=F(-1)$. We need to show $\det (M)=F(-1)$.

Expanding $\det (M)$. First level expansion we get$$\det (M)=\sum _{\sigma \in S_V}sgn(\sigma )\prod _{v\in V}{M}_{v,\sigma (v)}$$Then each of the product we can expand$$\prod _{v\in V}{M}_{v,\sigma (v)}=\sum \text{ Terms}$$The terms in the expansion of $\det (M)$ is the same as we make a choice of permutations $\sigma :V\to V$ plus a choice of terms from each $M_{v,\sigma (v)}$.

It turns out, terms $T$ in the expansion of $\det (M)$ are in bijection to $(\sigma ,\alpha )\in \mathcal{F}$. Moreover, $T=(-1{)}^{|\alpha |}Wt(\varphi )$ and hence $\det (M)=\sum T={\sum }_{(\sigma ,\alpha )\in \mathcal{T}}(-1{)}^{|\alpha |}Wt(\varphi )=F(-1)$.

$\square$

5.2Marked and Virtual Species

Remark 5.2.1 (Weighted Species Techniques). The set-up:

1.	Let $\mathcal{A}$ be a species, which is structures that can have flaws.
2.	Let $\mathcal{B}$ be the subspecies of $\mathcal{A}$ which are good.
3.	Let $\mathcal{M}$ be the weighted species of $\mathcal{A}$-structures with marked flaws with weight as the number of marks.

Then by inclusion exclusion we get $B(x)=M(x;-1)$.

Example 5.2.2. We will re-do the example of derangements: let $\mathcal{S}$ be permutations with flaws being fixed points. Then $\mathcal{D}$ is going to be the subspecies of derangements. Then let $\mathcal{M}$ be the permutation with marked fixed points. For example, we havewhere $\star$ means they are marked. Then we have $\mathcal{M}\equiv \mathcal{E}\ast \mathcal{S}$ where $\mathcal{E}$ is the set of marked fixed points and $\mathcal{S}$ is a permutation of the rest. Then the weight on $\mathcal{E}$ is just the order, to match our weight on $\mathcal{M}$. Thus the MGF of $\mathcal{M}$ is $E(x;t)S(x)=e^{tx}\frac{1}{1-x}$. On the other hand, we would have $D(x)=M(x,-1)=\frac{e^{-x}}{1-x}$.

Remark 5.2.3 ($2$-Species Technique). Let $\mathcal{A}$ and $\mathcal{B}$ as before. We assume: for $\sigma \in {\mathcal{A}}_X$, we have $Flaws(\sigma )\subseteq X$. Then we define ${\mathcal{M}}^S$ be the $2$-species of “split” $\mathcal{A}$-structure with marked flaws. The unmarked labels are the $1$st sort, and the marked labels are the second sort. Then $B(x)=M^S(x,-x)$.

Example 5.2.4. Let us do the derangement example again. An example of ${\mathcal{M}}^S$ iswhere the input set is ${\mathcal{M}}_{\{1,2,3\},\{a,b\}}^S$. Then we have ${\mathcal{M}}^S=\mathcal{S}[{\mathcal{X}}_1]\ast \mathcal{E}[{\mathcal{X}}_2]$ and hence the EGF is $M^S(x_1,x_2)=\frac{1}{1-x_1}{e}^{x_2}$ and hence we are done.

Example 5.2.5 (Feature, Not Bugs!). In this example we consider an example where we have features, instead of flaws. Let $\mathcal{A}$ be a weighted species, weight function equal the number of widgets. Let $\mathcal{M}$ be the weighted species of $\mathcal{A}$-structures with marked widgets with weight function equal the number of marks. Then $A(x;t)=M(x;t-1)$.

The example we are going to consider is permutations and descents. If $\sigma \in S_n$, and $\sigma (i)>\sigma (i+1)$, then we say $i$ is a descent of $\sigma$. The question is, how many permutations of $S_n$ with $k$ descents?

Here we consider the linear species of permutations $\mathcal{S}$. In other word, the input should be an ordered list instead of a set and we should produce the set of permutation of the given list. Let the weight function on $\mathcal{S}$ is the number of descents. Let $\mathcal{M}$ be the linear species of permutations with marked descents with weight function equal the number of marks.

Then let $\mathcal{D}$ be the linear species of decreasing sequences of length $\ge 2$ with weight function being the order minus $1$. For example, we have ${\mathcal{D}}_{(3,5,6,9)}=\{(9652)\}$ and $(9652)$ has weight $3$. Then the MGF of $\mathcal{D}$ should be$$D(x;t)=\sum _{n\ge 2}{t}^{n-1}\frac{x^n}{n!}=\frac{e^{xt}-xt-1}{t}$$Then we see we get decomposition $\mathcal{M}\equiv (\mathcal{X}+\mathcal{D}{)}^{\ast }$ and it is a weighted equivalence. Thus we get$$M(x;t)=\frac{1}{1-(x+D(x;t))}=\frac{1}{1-x-\frac{e^{xt}-xt-1}{t}}=\frac{-t}{e^{xt}-t-1}$$Finally, we get$$S(x;t)=M(x;t-1)=\frac{1-t}{e^{x(t-1)}-t}$$

Definition 5.2.6. Let $R$ be a ring with $2$ not a zero-divisor. Let $\mathcal{S},{\mathcal{S}}^{\prime }$ be two sets with generalized weight functions $Wt:\mathcal{S}\to R,W{t}^{\prime }:{\mathcal{S}}^{\prime }\to R$. Then suppose $\Phi :\mathcal{S}\to {\mathcal{S}}^{\prime }$ is a bijection, then we say $\Phi$ is sign-reversing bijection (SRB) if $W{t}^{\prime }(\Phi (s))=-Wt(s)$ for all $s\in \mathcal{S}$.

Remark 5.2.7. If a SRB exists between $\mathcal{S}$ and ${\mathcal{S}}^{\prime }$ then $|\mathcal{S}{|}_{Wt}=-|{\mathcal{S}}^{\prime }{|}_{W{t}^{\prime }}$.

Now we talk about the common scenarios of SRB.

Proposition 5.2.8. Let $\mathcal{T}\subseteq \mathcal{S}$, suppose there exists SRB $\Phi :\mathcal{S}\backslash \mathcal{T}\to \mathcal{S}\backslash \mathcal{T}$ then $|\mathcal{T}{|}_{Wt}=|\mathcal{S}{|}_{Wt}$.

Proof. Since SRB exists, we have $|\mathcal{S}\backslash \mathcal{T}{|}_{Wt}=-|\mathcal{S}\backslash \mathcal{T}{|}_{Wt}$ and hence we must have $|\mathcal{S}\backslash \mathcal{T}{|}_{Wt}=0$. However, we see $|\mathcal{S}{|}_{Wt}=|\mathcal{S}\backslash \mathcal{T}{|}_{Wt}+|\mathcal{T}{|}_{Wt}=|\mathcal{T}{|}_{Wt}$.

$\square$

Remark 5.2.9. If $\Phi \circ \Phi =\mathrm{I}\mathrm{d}$, then $\Phi$ is called a sign-reversing involution (SRI).

Example 5.2.10 (Euler’s Pentagonal Number Theorem). Let $\mathcal{S}$ be the set of strict partitions, i.e. $\lambda =({\lambda }_1,...,{\lambda }_l)$ with ${\lambda }_1>{\lambda }_2>...>{\lambda }_l$. Then we have weight $Wt:\mathcal{S}\to \mathbb{Q}[[x]]$ be$$Wt(\lambda )=(-1{)}^{length(l)}{x}^{|\lambda |}$$Then let $\mathcal{T}$ be the pentagonal partitions, which is equal$$\{ϵ,(1),(2),(3,2),(4,3),(5,4,3),(6,5,4),(7,6,5,4),(8,7,6,5),...\}$$Then there exists a SRI $\Phi :\mathcal{S}\backslash \mathcal{T}\to \mathcal{S}\backslash \mathcal{T}$. Thus we have$$\prod _{i\ge 1}(1-x^i)=|\mathcal{S}{|}_{Wt}=|\mathcal{T}{|}_{Wt}=\sum _{k\in \mathbb{Z}}(-1{)}^k{x}^{g_k}$$where $g_k$ is the pentagonal numbers.

Remark 5.2.11 (What is Virtual Species). We consider the analogy:

1.	The species are like natural numbers $\mathbb{N}$ (we have operations like $+,-,\cdot$).
2.	Then generalized weighted species are like ${\mathbb{N}}^X$, which is functions from $X$ to $\mathbb{N}$ (we also have operations like $+,-,\cdot$).
3.	Then, virtual species are like integers, as we note subtraction for natural numbers are only partially defined, e.g. $3-5$ is not defined in $\mathbb{N}$.

Thus, to define virtual species, we recall the construction of $\mathbb{Z}$:

1.	We start with the set ${\mathbb{N}}^{\{+,-\}}$. In other word, this is the set of functions from set $\{+,-\}$ map to $\mathbb{N}$. We can write these functions as pairs, i.e. $f=(f(+),f(-))\in {\mathbb{N}}^{\{+,-\}}$.
2.	Then we can add interpretations of those functions to think them as integers. The idea is that function $f$ represents integer $f(+)-f(-)$. However, $f(+)-f(-)$ does not make sense yet. To achieve this, we define an equivalence relation on ${\mathbb{N}}^{\{+,-\}}$, which is $f{\equiv }_{\mathbb{Z}}g$ if and only if $f(+)+g(-)=f(-)+g(+)$.
3.	Then we have an embedding $\mathbb{N}\to \mathbb{Z}$. In other word, if we have natural number $m\in \mathbb{N}$, then we can identify $m$ as the function $(m,0)$. For $m,n\in \mathbb{N}$, we have $m{\equiv }_{\mathbb{Z}}n$ if and only if $m=n$.
4.	Negation of integers. For integer $f=(f(+),f(-))$, we can define $-f$ as the function $(f(-),f(+))$.
5.	Addition of integers. We can define $f+g$ as addition as functions.
6.	We can also subtract integers. In other word, we just define $f-g$ as $f+(-g)$.
7.	Thus we have defined the additive group $\mathbb{Z}$.
8.	We still have one operation left, which is multiplication. This is not just the product of functions, the reason is that integer multiplication must respect the equivalence relation. If $f{\equiv }_{\mathbb{Z}}{f}^{\prime }$ and $g{\equiv }_{\mathbb{Z}}{g}^{\prime }$, then we must have $fg{\equiv }_{\mathbb{Z}}{f}^{\prime }{g}^{\prime }$. The function multiplication does not have this property. The correct formula is$$fg=f(+)g(+)-f(+)g(-)-f(-)g(+)+f(-)g(-)$$This is the unique formula satisfying distributive property and rules about negation.
9.	New definitions of $+,-,\cdot$ consists with the old definitions when we consider $\mathbb{N}$ embedded into $\mathbb{Z}$.

Definition 5.2.12 (Virtual Species). A virtual species $\mathcal{V}$ is a generalized weighted species, with generalized weight function $sg{n}_V:\mathcal{V}\to \{+1,-1\}$. We can also think $\mathcal{V}$ as a pair of ordinary (unweighted) species, called ${\mathcal{V}}^{+},{\mathcal{V}}^{-}$. The ${\mathcal{V}}_X^{+}$ is defined to be $\{\alpha \in {\mathcal{U}}_X:sg{n}_V(\alpha )=1\}$ and similarly ${\mathcal{V}}_X^{-}=\{\alpha \in {\mathcal{V}}_X:sg{n}_V(\alpha )=-1\}$.

Definition 5.2.13.

Suppose $\mathcal{V},\mathcal{W}$ be two virtual species, we say $\mathcal{V},\mathcal{W}$ are virtually equivalent and write $\mathcal{V}{\equiv }_{vir}\mathcal{W}$ if and only if ${\mathcal{V}}^{+}+{\mathcal{W}}^{-}\equiv {\mathcal{W}}^{+}+{\mathcal{V}}^{-}$.

Remark 5.2.14. Every ordinary species $\mathcal{A}$ can be turned into a virtual species by giving it constant sign function $+1$. If $\mathcal{A},\mathcal{B}$ are ordinary species, then $\mathcal{A}{\equiv }_{vir}\mathcal{B}$ if and only if $\mathcal{A}\equiv \mathcal{B}$.

Definition 5.2.15. Let $\mathcal{V}$ be a virtual species, we define the negation of a virtual species $-\mathcal{V}$ as $(-\mathcal{V}{)}_X={\mathcal{V}}_X$ with $sg{n}_{-V}=-sg{n}_V$.

Definition 5.2.16. Let $\mathcal{V},\mathcal{W}$ be virtual species, then addition is defined as $\mathcal{V}+\mathcal{W}$ as addition of generalized weighted species. Then subtraction is defined to be $\mathcal{V}-\mathcal{W}:=\mathcal{V}+(-\mathcal{W})$.

Remark 5.2.17. Under such definitions, we get $\mathcal{V}{\equiv }_{vir}{\mathcal{V}}^{+}-{\mathcal{V}}^{-}$. Thus what about other operations? For most, same definitions as generalized weighted species. For others, the GWS definitions does not respect virtual equivalence.

Finally, our new definitions will be consistent with the old definitions.

Remark 5.2.18 (Why Virtual Species?).

1.	We have seen some species with no known decomposition but can still get EGF by inclusion exclusion.
2.	However, IE is based on numerical equivalence, not natural equivalence.
3.	Thus to go beyond EGFs, this is not good enough.
4.	Sometimes, when we do not have decomposition, we can come up some virtual decomposition.

Definition 5.2.19. Let $\mathcal{V}$ be a virtual species, then the EGF of $\mathcal{V}$ is just $V(x)={\sum }_{n\ge 0}|{\mathcal{V}}_n{|}_{sg{n}_V}\frac{x^n}{n!}$ where$$|{\mathcal{V}}_n{|}_{sg{n}_V}=\sum _{\alpha \in {\mathcal{V}}_X}sgn(\alpha )$$where $|X|=n$.

Remark 5.2.20. A virtual species operation is good, if it respects the virtual equivalence relation. For example, if $R$ is a virtual species operation, with $\mathcal{V}{\equiv }_{vir}{\mathcal{V}}^{\prime }$ and $\mathcal{W}{\equiv }_{vir}{\mathcal{W}}^{\prime }$ then we must have $\mathcal{V}R\mathcal{W}{\equiv }_{vir}{\mathcal{V}}^{\prime }R{\mathcal{W}}^{\prime }$.

Definition 5.2.21. The virtual species operations for filters, products (all three), sequences and derivatives and rootings are just the generalized weighted species operation.

Remark 5.2.22. In other word, the GWS definitions for the above operations respect virtual equivalence. We note:

1.	Perform operations on bases species (base $\mathcal{V}={\mathcal{V}}^{+}+{\mathcal{V}}^{-}$).
2.	Add sign functions according the rules: sign of composite objects is the product of the signs of its components.

In this case, the EGF is just given by the main theorem.

We note the concept of “base species” does not respect virtual equivalence, i.e. $\mathcal{V}{\equiv }_{vir}\mathcal{U}$ does not imply the base of $\mathcal{V}$ is equivalent to the base of $\mathcal{U}$. But nonetheless, these operations do respect virtual equivalence.

Example 5.2.23 (Products). We have $(\mathcal{V}\ast \mathcal{W}{)}_X=(({\mathcal{V}}^{+}+{\mathcal{V}}^{-})\ast ({\mathcal{W}}^{+}+{\mathcal{W}}^{-}){)}_X$. However, this is just$$({\mathcal{V}}^{+}\ast {\mathcal{W}}^{+}{)}_X\cup ({\mathcal{V}}^{+}\ast {\mathcal{W}}^{-}{)}_X\cup ({\mathcal{V}}^{-}\ast {\mathcal{W}}^{+}{)}_X\cup ({\mathcal{V}}^{-}\ast {\mathcal{W}}^{-}{)}_X$$Then we look at the signs and we get$$\mathcal{V}\ast \mathcal{W}:={\mathcal{V}}^{+}\ast {\mathcal{W}}^{+}-{\mathcal{V}}^{+}\ast {\mathcal{W}}^{-}-{\mathcal{V}}^{-}\ast {\mathcal{W}}^{+}+{\mathcal{V}}^{-}\ast {\mathcal{W}}^{-}$$

Definition 5.2.24. If $\mathcal{V}\ast \mathcal{W}{\equiv }_{cir}1$ then we say $\mathcal{W}$ is a multiplicative inverse of $\mathcal{V}$.

Theorem 5.2.25.

1.	$\mathcal{V}$ has a multiplicative inverse if and only if ${\mathcal{V}}_0{\equiv }_{vir}1$.
2.	Assume $\mathcal{V}$ has multiplication inverse ${\mathcal{V}}^{-1}$, then it is unique up to virtual equivalence.
3.	If ${\mathcal{V}}_0{\equiv }_{vir}1$ then ${\mathcal{V}}^{-1}{\equiv }_{vir}(-{\mathcal{V}}_{+}{)}^{\ast }$.
4.	The EGF of ${\mathcal{V}}^{-1}$ is $V(x{)}^{-1}$.

Proof. We will only talk about $(3)$. We note we have $\mathcal{V}\ast {\mathcal{V}}^{-1}{\equiv }_{vir}(1+{\mathcal{V}}_{+})\ast (1-{\mathcal{V}}_{+}+{\mathcal{V}}_{+}^2-{\mathcal{V}}_{+}^3+...)=1$.

$\square$

Example 5.2.26. We have $$\begin{array}{rl}{\mathcal{E}}^{-1}& =(-{\mathcal{E}}_{+}{)}^{\ast }\\ & =\sum _{n\ge 0}({\mathcal{E}}_{+}{)}^{2n}-\sum _{n\ge 0}({\mathcal{E}}_{+}{)}^{2n+1}\end{array}$$where we see the left part is just ordered set partitions with even number of parts and the right sum is ordered set partitions with odd number of parts.

Remark 5.2.27. We finally talk about virtual multisort species. Everything so far extends to multisort species. Moreover, the diagonal operation $\nabla$ on generalized weighted $2$-species also respect virtual equivalence.

Remark 5.2.28 (Compositions). We will not give a definition of virtual species composition. Instead, we will give a set of rules so that we can compute virtual species compositions.

Let $\mathcal{A},\mathcal{B}$ be ordinary connected $1$-species or $2$-species. Let $\mathcal{V}$ be virtual $1$-species and $\mathcal{Z}$ be virtual $2$-species.

Then we have:

1.	$\mathcal{V}[\mathcal{A}]{\equiv }_{vir}{\mathcal{V}}^{+}[\mathcal{A}]-{\mathcal{V}}^{-}[\mathcal{A}]$.
2.	$\mathcal{Z}[\mathcal{A},\mathcal{B}]{\equiv }_{vir}{\mathcal{Z}}^{+}[\mathcal{A},\mathcal{B}]-{\mathcal{Z}}^{-}[\mathcal{A},\mathcal{B}]$.
3.	$\mathcal{V}[-\mathcal{X}]{\equiv }_{vir}\mathcal{V}⊠{\mathcal{E}}^{-1}$.
4.	$\mathcal{Z}[{\mathcal{X}}_1,-{\mathcal{X}}_2]{\equiv }_{vir}\mathcal{Z}⊠(\mathcal{E}[{\mathcal{X}}_1]\ast {\mathcal{E}}^{-1}[{\mathcal{X}}_2])$.
5.	$\mathcal{V}[-\mathcal{B}]{\equiv }_{vir}\mathcal{V}[-\mathcal{X}][\mathcal{B}]$.
6.	$\mathcal{Z}[\mathcal{A},-\mathcal{B}]{\equiv }_{vir}\mathcal{Z}[{\mathcal{X}}_1,-{\mathcal{X}}_2][\mathcal{A},\mathcal{B}]$.
7.	$\mathcal{V}[\mathcal{A}-\mathcal{B}]{\equiv }_{vir}\mathcal{V}[{\mathcal{X}}_1+{\mathcal{X}}_2][\mathcal{A},-\mathcal{B}]$.

In each of the case, the rule is a slight generalizations of an identity for ordinary species. For example, for $k\in \mathbb{N}$, we can define $k\mathcal{X}=\mathcal{X}+\mathcal{X}+...+\mathcal{X}$. Then $\mathcal{A}[k\mathcal{X}]\equiv \mathcal{A}⊠{\mathcal{E}}^k$. Now let $\mathcal{A}$ be virtual and $k=-1$, then we get $(3)$ in the above rule.

Example 5.2.29. If $\mathcal{W}$ is connected virtual species, then $\mathcal{E}[\mathcal{W}]{\equiv }_{vir}\mathcal{E}[{\mathcal{W}}^{+}]\ast {\mathcal{E}}^{-1}[{\mathcal{W}}^{-}]$.

Proof: We see $\mathcal{E}[\mathcal{W}]{\equiv }_v\mathcal{E}[{\mathcal{W}}^{+}-{\mathcal{W}}^{-}]$. Then by rule $(7)$, we get this is the same as$$\mathcal{E}\mathcal{W}{\equiv }_v\mathcal{E}[{\mathcal{X}}_1+{\mathcal{X}}_2][{\mathcal{W}}^{+},-{\mathcal{W}}^{-}]$$Now apply rule $(6)$, we get this is$$\mathcal{E}[\mathcal{W}]\equiv \mathcal{E}[{\mathcal{X}}_1+{\mathcal{X}}_2][{\mathcal{X}}_1,-{\mathcal{X}}_2][{\mathcal{W}}^{+},{\mathcal{W}}^{-}]$$Now use rule $(4)$, we get$$\mathcal{E}[\mathcal{W}]\equiv \left(\mathcal{E}[{\mathcal{X}}_1+{\mathcal{X}}_2]⊠(\mathcal{E}[{\mathcal{X}}_1]\ast {\mathcal{E}}^{-1}[{\mathcal{X}}_2])\right)[{\mathcal{W}}^{+},{\mathcal{W}}^{-}]$$However, we note the multiplicative identity for the operation superposition is $\mathcal{E}[{\mathcal{X}}_1+{\mathcal{X}}_2]$, and hence we get$$\mathcal{E}[{\mathcal{X}}_1+{\mathcal{X}}_2]⊠(\mathcal{E}[{\mathcal{X}}_1]\ast {\mathcal{E}}^{-1}[{\mathcal{X}}_2])=\mathcal{E}[{\mathcal{X}}_1]\ast {\mathcal{E}}^{-1}[{\mathcal{X}}_2]$$Thus by use rule $(2)$ and $(1)$ a few times, we would get$$\mathcal{E}[\mathcal{W}]{\equiv }_{vir}\mathcal{E}[{\mathcal{W}}^{+}]\ast {\mathcal{E}}^{-1}[{\mathcal{W}}^{-}]$$

Theorem 5.2.30.

1.	Rule $(1)$ to $(7)$ can be used to compute $\mathcal{V}[\mathcal{W}]$ for any virtual species $\mathcal{V},\mathcal{W}$ with $\mathcal{W}$ connected
2.	Virtual species composition respects ${\mathcal{E}}_{vir}$.
3.	EGF of $\mathcal{V}[\mathcal{W}]$ is $V(W(x))$.

Remark 5.2.31. Recall $2$-species inclusion exclusion technique:

1.	$\mathcal{A}$ is a species with structures have flaws $\subseteq X$.
2.	$\mathcal{B}$ is the species of good $\mathcal{A}$-structures.
3.	${\mathcal{M}}^S$ is the $1$-species of split $\mathcal{A}$-structures with marked flaws.

In this set-up, we have the following theorem.

Theorem 5.2.32. $\mathcal{B}{\equiv }_{vir}{\mathcal{M}}^S[\mathcal{X},-\mathcal{X}]$.

Proof. Define a split version of $\mathcal{A}$, defined to be ${\mathcal{A}}^S$, as the subspecies of ${\mathcal{M}}^S$, where all flaws are marked. Then ${\mathcal{M}}^S\equiv {\mathcal{A}}^S[{\mathcal{X}}_1,{\mathcal{X}}_1+{\mathcal{X}}_2]$ where the ${\mathcal{X}}_1+{\mathcal{X}}_2$ is like unmark subset of the flaws. Thus we get $\mathcal{B}\equiv {\mathcal{A}}^S[\mathcal{X},0]$, which is no marks, which is the same as no flaws. Thus we get$$\mathcal{B}{\equiv }_{vir}{\mathcal{A}}^S[\mathcal{X},\mathcal{X}+(-\mathcal{X})]{\equiv }_{vir}{\mathcal{M}}^S[\mathcal{X},-\mathcal{X}]$$

$\square$

5.3Counting With Automorphism

Definition 5.3.1. Let $G$ be a finite group, $Y$ a finite set of “points” with a $G$-action. Then we define the orbit of $y\in Y$ is given by$$\tilde{y}=G\cdot y:=\{g\cdot y:g\in G\}$$We write the set of all orbits as $\tilde{Y}=Y/G=\{\tilde{y}:y\in Y\}$. We define the stabilizer of $y\in Y$ is given by$$G_y:=\{g\in G:gy=y\}$$We define the fixed points of $g\in G$ by$$Y^g:=\{y\in Y:gy=y\}$$

Remark 5.3.2. We recall the orbit-stabilizer theorem, which states $|G_y|\cdot |\tilde{y}|=|G|$. We also recall the orbit counting lemma, which states$$|\tilde{Y}|=\frac{1}{|G|}\sum _{g\in G}|Y^g|$$Now we prove this. We see $$\begin{array}{rl}\frac{1}{|G|}\sum _{g\in G}|Y^g|& =\frac{1}{|G|}\sum _{\begin{array}{c}(g,y)\in G\times Y\\ gy=y\end{array}}1\\ & =\frac{1}{|G|}\sum _{y\in Y}|G_y|\\ & =\sum _{y\in Y}\frac{|G_y|}{|G|}\\ & =\sum _{y\in Y}\frac{1}{|\tilde{y}|}\\ & =\sum _{\tilde{y}\in \tilde{Y}}\sum _{y\in \tilde{y}}\frac{1}{|\tilde{y}|}\\ & =\sum _{\tilde{y}\in \tilde{Y}}1\\ & =|\tilde{Y}|\end{array}$$

Example 5.3.3. How many ways can we colour $n$-gon up to rotation? Well, let $K$ be the set of colours, say $|K|=k$, and let our group be $C_n=({\mathbb{Z}}_n,+)$, which we can think as sides of $n$-gon.

We want to count $Y=K^{{\mathbb{Z}}_n}$, which we can think as functions from ${\mathbb{Z}}_n$ to $K$, which correspond to a way of colour the $n$-gon. The group action will be, for function $f:{\mathbb{Z}}_n\to K$ and $c\in C_n$, we define $C_n$-action$$cf:\mathbb{Z}\to K,i\mapsto f(i-c)$$

Then our goal is to count the orbits. Hence we need to look at fixed points. For $c\in C_n$, we see $$\begin{array}{rl}{Y}^c& =\{f:{\mathbb{Z}}_n\to K:\forall i\in {\mathbb{Z}}_n,f(i-c)=f(i)\}\\ & =\{f:{\mathbb{Z}}_n\to K:\forall i\in {\mathbb{Z}}_n,f(i-d)=f(i),d=\gcd (c,n)\}\end{array}$$Thus we see $|Y^c|=k^{\gcd (c,n)}$ and hence$$|\tilde{Y}|=\frac{1}{n}\sum _{c\in C_n}{k}^{\gcd (c,n)}=\frac{1}{n}\sum _{d|n}\varphi (\frac{n}{d})k^d$$where $\varphi$ is the Totient function.

Example 5.3.4. Let ${\mathcal{M}}_m:=\{f:{\mathbb{Z}}_n\to \mathbb{N}:{\sum }_{i\in {\mathbb{Z}}_n}f(i)=m\}$. How many $C_n$-orbits? Again, this $C_n$-action would given by $cf:{\mathbb{Z}}_n\to \mathbb{N}$ with $i\mapsto f(i-c)$. To use generating function, we let $\mathcal{S}={\mathbb{N}}^{{\mathbb{Z}}_n}=\{f:{\mathbb{Z}}_n\to \mathbb{N}\}$, then we let weight function be $wt:\mathcal{S}\to \mathbb{N}$ with $wt(f)={\sum }_{i\in {\mathbb{Z}}_n}f(i)$. Note for $S(x)=(1-x{)}^{-n}$ and hence$$|{\mathcal{S}}_m|=[x^m]S(x)$$

Now we want to generalize this to count fixed points. For $c\in C_n$, we see ${\mathcal{S}}^c$ is in bijection with $(\frac{n}{d}\mathbb{N}{)}^{{\mathbb{Z}}_d}$ where $d=\gcd (c,n)$. Thus, we see $S^c(x)=(1-x^{h/d}{)}^{-d}$ and hence$$|{\mathcal{S}}_m^c|=[x^m]S^c(x)$$Now by orbit counting lemma, we get$$|{\tilde{\mathcal{S}}}_m|=\frac{1}{n}\sum _{c\in C_n}|{\mathcal{S}}_m^c|=[x^m]\frac{1}{m}\sum _{d\mid n}\varphi (\frac{n}{d})(1-x^{n/d}{)}^{-d}$$

Remark 5.3.5 (Type Generating Function). Let $\mathcal{A}$ be a species, $S_n$ the symmetric group of $[n]$. Then we have a $S_n$-action of sets of structures on ${\mathcal{A}}_{[n]}$. For $\alpha \in {\mathcal{A}}_{[n]}$ and $\sigma \in S_n$, we have$$\sigma \alpha ={\sigma }_{\ast }(\alpha )$$where ${\sigma }_{\ast }$ is transportation of $\mathcal{A}$-structures along $\sigma$. In particular, the isomorphism type of order $n$ are exactly the $S_n$-orbits on ${\mathcal{A}}_{[n]}$.

In this case, we can define type generating functions. For an isomorphism type $\tilde{\alpha }\in {\tilde{\mathcal{A}}}_n$, write $ord(\tilde{\alpha })=n$. Then the type generating function for $\mathcal{A}$ is the OGF for $\tilde{\mathcal{A}}$ with respect to $ord$. In other word,$$\tilde{A}(x)=\sum _{\tilde{\alpha }\in \tilde{\mathcal{A}}}{x}^{ord(\tilde{\alpha })}=\sum _{n\ge 0}|{\tilde{\mathcal{A}}}_n|x^n$$

Example 5.3.6.

1.	Consider the species $\mathcal{E}$. We see we have $1$ isomorphism type of each order, thus$$\tilde{E}(x)=\sum _{n\ge 0}1x^n=\frac{1}{1-x}$$
2.	Consider the rooted linear order ${\mathcal{L}}^{\bullet }$. We see $\mathcal{L}$ has $1$ isomorphism type of each order $n$, thus the rooted version has $n$ non-isomorphic ways to root. Thus$$\widetilde{L^{\bullet }}(x)=\sum _{n\ge 0}n{x}^n=\frac{x}{(1-x{)}^2}$$
3.	Consider $\mathcal{S}$, the species of permutations. The cycle type of a permutation $\sigma \in {\mathcal{S}}_X$ is the partition $\lambda =({\lambda }_1,...,{\lambda }_l)$ such that ${\lambda }_1,...,{\lambda }_l$ are the lengths of the cycles of $\sigma$. Then we see two permutations are isomorphic iff they have the same cycle type. In other word$$\tilde{\mathcal{S}}(x)=\prod _{i\ge 1}\frac{1}{1-x^i}$$

Proposition 5.3.7. Let $\mathcal{A},\mathcal{B}$ be two species, then

1.	TGF of $\mathcal{A}+\mathcal{B}$ is $\tilde{A}(x)+\tilde{B}(x)$.
2.	TGF of $\mathcal{A}\ast \mathcal{B}$ is $\tilde{A}(x)\tilde{B}(x)$.

Proof. This is because $\widetilde{\mathcal{A}+\mathcal{B}}=\tilde{\mathcal{A}}\cup \tilde{\mathcal{B}}$ and $\widetilde{\mathcal{A}\ast \mathcal{B}}=\tilde{\mathcal{A}}\times \tilde{\mathcal{B}}$.

$\square$

Remark 5.3.8. However, this is all we get. For other operations, TGF of output species cannot be determined from TGF of input. For example, $\mathcal{E}$ and $\mathcal{L}$ have the same TGF, but ${\mathcal{E}}^{\bullet }$ and ${\mathcal{L}}^{\bullet }$ have different TGF.

Definition 5.3.9. Let $G$ be a finite group, $\mathcal{A}$ a species. Then a natural $G$-action on $\mathcal{A}$ is a rule that assigns to each group element a natural equivalence ${\Phi }^g:\mathcal{A}\to \mathcal{A}$ such that for every finite set $X$, we get a $G$-group action on ${\mathcal{A}}_X$ given by$$g\alpha ={\Phi }_X^g(\alpha )$$

Definition 5.3.10. Let $G$ acts naturally on $\mathcal{A}$. We define the species of orbits $\mathcal{A}/G$ to be$$(\mathcal{A}/G{)}_X={\mathcal{A}}_X/G$$

Example 5.3.11. We see $S_n$ acts naturally on ${\mathcal{A}}^n$. For $({\alpha }_1,...,{\alpha }_n)\in {\mathcal{A}}_X$ and $\sigma \in S_n$, we define$$\sigma ({\alpha }_1,...,{\alpha }_n)=({\alpha }_{\sigma (1)},...,{\alpha }_{\sigma (n)})$$This is a natural $S_n$-action and$${\mathcal{A}}^n/S_n\equiv {\mathcal{E}}_n[\mathcal{A}]$$

Remark 5.3.12 (Speciesification). Let $G$ be a subgroup of $S_n$, $\mathcal{Y}$ be a finite set with $G$-action. The natural action of $G$ on $Y\times {\mathcal{X}}^n$ will be$$g(y,(x_1,...,x_n))=(gy,(x_{g(1)},...,x_{g(n)}))$$Then the speciesification ${\mathcal{Y}}^{sp}$ will be defined as$${\mathcal{Y}}^{sp}:=(\mathcal{Y}\times {\mathcal{X}}^n)/G$$

Proposition 5.3.13. Let $G$ be a subgroup of $S_n$, $\mathcal{Y}$ a finite set with $G$-action. Then there is a bijection$$\widetilde{{\mathcal{Y}}^{sp}}\leftrightarrow \tilde{\mathcal{Y}}$$

Example 5.3.14. Say $\mathcal{Y}=K^{{\mathbb{Z}}_n}$ be the colourings of sides of $n$-gon with $C_n$-action. Then ${\mathcal{Y}}^{sp}\equiv \mathcal{C}[K\times \mathcal{X}]$.

Remark 5.3.15 (Cycle Index Functions). Let $\mathcal{A}$ be a species, we are going to construct the cycle index function $Z_{\mathcal{A}}\in \mathbb{T}=\mathbb{T}(\mathbb{Q}[[x]])$, which is a algebraic transformation.

First, for a species $\mathcal{A}$ we can construct the species of automorphisms as follows. For $\alpha \in {\mathcal{A}}_X,\sigma \in {\mathcal{S}}_X$, $\sigma$ is an automorphism of $\alpha$ iff ${\sigma }_{\ast }(\alpha )=\alpha$. Then $Aut(\mathcal{A})$ is a subspecies of $\mathcal{A}⊠\mathcal{S}$, given by$$Aut(\mathcal{A}{)}_X=\{(\alpha ,\sigma ):\alpha \in {\mathcal{A}}_X,\sigma \in {\mathcal{S}}_X,{\sigma }_{\ast }(\alpha )=\alpha \}$$

Then the TGF of species of automorphisms is given by$$|{\tilde{\mathcal{A}}}_n|=\frac{1}{n!}|Aut(\mathcal{A}{)}_n|$$using$$|\tilde{\mathcal{Y}}|=\frac{1}{|G|}\sum _{(s,y)\in G\times Y,gy=y}1$$Thus we get$$\tilde{A}(x)=\sum _{n\ge 0}|Aut(\mathcal{A}){|}_n\frac{x^n}{n!}$$

However, this may not be helpful if $Aut(\mathcal{A})$ is hard to compute. Thus, we consider the power evaluation maps for $k=1,2,3,...$. In particular, $p_k:=e{v}_{x^k}\in {\mathbb{T}}_{+}$ is given by $p_k[u(x)]=u(x^k)$. Then for a partition $\lambda =({\lambda }_1,...,{\lambda }_l)$, we define the algebraic transformation$$p_{\lambda }:=p_{{\lambda }_1}...p_{{\lambda }_l}$$as$$p_{\lambda }[u(x)]=\prod _{i=1}^{l}u(x^{{\lambda }_i})$$In particular, if $|\lambda |=0$ then $p_{\lambda }=1\in \mathbb{T}$.

For permutation $\sigma$, with the cycle type $cyc(\sigma )=\lambda$. Then we write $p_{\sigma }=p_{\lambda }$. Now we can define the cycle index function (which is an algebraic transformation) as follows$$Z_{\mathcal{A}}=\sum _{n\ge 0}\frac{1}{n!}\sum _{(\alpha ,\sigma )\in Aut(\mathcal{A}{)}_n}{p}_{\sigma }$$We can think this as generalized EGF for $Aut(\mathcal{A})$ with $Wt(\alpha ,\sigma )=p_{\sigma }$.

Proposition 5.3.16. $$\tilde{A}(x)=Z_{\mathcal{A}}[x]$$

Proof. For all $\sigma \in S_n$, we see $p_{\sigma }[x]=x^n$. Thus$$Z_{\mathcal{A}}[x]=\sum _{n\ge 0}\frac{1}{n!}\sum _{(\alpha ,\sigma )\in Aut(\mathcal{A}{)}_n}{p}_{\sigma }[x]=\sum _{n\ge 0}|Aut(\mathcal{A}{)}_n|\frac{x^n}{n!}=\tilde{\mathcal{A}}(x)$$

$\square$

Definition 5.3.17. We define $\Lambda \subseteq \mathbb{T}$ be the closed subring of $\mathbb{T}$ generated over $\mathbb{Q}$ in $p_1,p_2,p_3,\dots$. In other word,$$\Lambda =\{f\in \sum _{\lambda \in p}{f}_{\lambda }{p}_{\lambda }:f_{\lambda }\in \mathbb{Q}\}$$where $p$ is the set of integer partitions. We also define ${\Lambda }_{+}:=\Lambda \cap {\mathbb{T}}_{+}$.

Theorem 5.3.18. The set of $\{p_{\lambda }:\lambda \in p\}$ is $\mathbb{Q}$-linearly independent.

Remark 5.3.19 (Implications). Some implications of the above theorem includes:

1.	For $f={\sum }_{\lambda \in p}{f}_{\lambda }{p}_{\lambda }$, we can define$$[p_{\lambda }]f:=f_{\lambda }$$
2.	We can also define partial derivative $\frac{\partial }{\partial p_k}:\Lambda \to \Lambda$

Proposition 5.3.20. Let $f\in \Lambda$ and $g\in {\Lambda }_{+}$. Then

1.	$p_k\circ p_l=p_{kl}$ where $k,l\in {\mathbb{N}}_{\ge 1}$.
2.	$p_k\circ g=p\circ p_k$ where $k\in {\mathbb{N}}_{\ge 1}$.
3.	$\circ$ (composition) is left homomorphic, i.e. if $f={\sum }_{\lambda }{f}_{\lambda }{p}_{\lambda }$, then$$f\circ g=\sum _{\lambda }{f}_{\lambda }\prod _{i=1}^{length(\lambda )}(p_{{\lambda }_i}\circ g)$$

Corollary 5.3.21. $\Lambda$ is closed under composition.

Example 5.3.22. We have $$\begin{array}{rl}(p_2^3+p_3)\circ (2p_2-p_5)& =((p_2\circ (2p_2-p_5)){)}^3+(p_3\circ (2p_2-p_5))\\ & =((2p_3-p_5)\circ p_2{)}^3+((2p_2-p_5)\circ p_5)\\ & =(2p_2\circ p_2-p_5\circ p_2{)}^3+(2p_2\circ p_3-p_5\circ p_3)\\ & =(2p_4-p_{10}{)}^3+(2p_6-p_{15})\end{array}$$

Remark 5.3.23 (Dual Basis). Let $\lambda \in p$, define $z_{\lambda }\in {\mathbb{Z}}_{+}$ using one of the three definitions:

1.	If $\sigma \in S_n$, with cycle type $cyc(\sigma )=:\lambda$, then $z_{\lambda }=|Cen{t}_{S_n}(\sigma )|$ where $Cen{t}_{S_n}(\sigma )$ means the centralizer of $\sigma$.
2.	If $|\lambda |=n$, then$$z_{\lambda }=\frac{n!}{|\{\sigma \in S_n:cyc(\sigma )=\lambda \}|}$$
3.	If $n_j(\lambda )$ equal the number of parts of size $j$ in $\lambda$, then$$z_{\lambda }=\prod _{j\ge 1}(j^{n_j(\lambda )}\cdot n_j(\lambda )!)$$

We often prefer to write elements of $\Lambda$ in the form$$f=\sum _{\lambda \in p}{f}_{\lambda }\frac{p_{\lambda }}{z_{\lambda }}$$and we will write $[\frac{p_{\lambda }}{z_{\lambda }}]f:=f_{\lambda }$. The analogy is $A(x)={\sum }_{n\ge 0}{a}_n{x}^n$ as to $f=\sum f_{\lambda }{p}_{\lambda }$ and $A(x)={\sum }_{n\ge 0}{a}_n\frac{x^n}{n!}$ as to $f=\sum f_{\lambda }\frac{p_{\lambda }}{z_{\lambda }}$.

Remark 5.3.24 (Cycle Index Functions In Dual Basis). Say $\mathcal{A}$ is a species, and$$Z_{\mathcal{A}}=\sum _{\lambda \in p}{a}_{\lambda }\frac{p_{\lambda }}{z_{\lambda }}$$Then for any permutation $\sigma \in {\mathcal{S}}_X$ with cycle type $cyc(\sigma )=\lambda$, we have$$a_{\lambda }=\#\{\alpha \in {\mathcal{A}}_X:{\sigma }_{\ast }(\alpha )=\alpha \}$$

Remark 5.3.25 (Symmetric Functions). Let $f={\sum }_{\lambda \in p}{f}_{\lambda }{p}_{\lambda }\in \Lambda$, we associate symmetric function $F(x_1,...,x_m)\in \mathbb{Q}[[x_1,...,x_m]]$ defined as follows:$$F(x_1,...,x_m)=\sum _{\lambda \in p}{f}_{\lambda }\prod _{i=1}^{length(\lambda )}(x_1^{{\lambda }_i}+...+x_m^{{\lambda }_i})$$Since each expression is symmetric in variables $x_1,...,x_m$, the overall expression is symmetric.

On the other hand, we have equivalent description of $F(x_1,...,x_m)$, which is the unique FPS with the property$$F(x^{k_1},...,x^{k_m})=f[x^{k_1}+x^{k_2}+...+x^{k_m}]$$for all tuples $(k_1,...,k_m)\in {\mathbb{Z}}_{+}^m$.

Then, use symmetric function theory, we can express $[p_{\lambda }]f$ in terms of $F$ provided $m\ge length(\lambda )$

Example 5.3.26. Let $\mathcal{L}$ be the species of linear orders. Since linear orders have no non-trivial automorphisms, we see$$Aut(\mathcal{L}{)}_X={\mathcal{L}}_X\times \{{\mathrm{I}\mathrm{d}}_{\mathrm{X}}\}$$Hence we get$$Z_{\mathcal{L}}=\sum _{n\ge 0}\frac{1}{n!}(n!p_{{\mathrm{I}\mathrm{d}}_{\mathrm{n}}})=\sum _{n\ge 0}{p}_1^n=\frac{1}{1-p_1}$$

Next, consider $\mathcal{E}$ be the species of sets. Then every permutation is going to be an automorphism. Thus $Aut(\mathcal{E})\equiv \mathcal{S}$ where the generalized weight function is $Wt(\sigma )=p_{\sigma }$. We see $\mathcal{S}\equiv \mathcal{E}[\mathcal{C}]$ and the weight on $\mathcal{C}$ should be $p_k$ where $k$ is the order of $\alpha \in \mathcal{C}$ and the weight on $\mathcal{E}$ is the trivial one. Then the generalized EGF for $\mathcal{C}$ is ${\sum }_{k\ge 1}\frac{p_k}{k}$ and hence $Z_{\mathcal{S}}=\exp ({\sum }_{k\ge 1}\frac{p_k}{k})$.

Next, we look at $\mathcal{S}$. We see $Aut(\mathcal{S}{)}_X=\{(\alpha ,\sigma )\in {\mathcal{S}}_X\times {\mathcal{S}}_X:\alpha \sigma =\sigma \alpha \}$. Write$$Z_{\mathcal{S}}=\sum _{\lambda \in p}{s}_{\lambda }\cdot \frac{p_{\lambda }}{z_{\lambda }}$$Then for any $\sigma \in {\mathcal{S}}_X$, $cyc(\sigma )=\lambda$, we have $s_{\lambda }=\#\{\alpha \in {\mathcal{S}}_X:\alpha \sigma =\sigma \alpha \}=z_{\lambda }$. Therefore,$$Z_{\mathcal{S}}=\sum _{\lambda \in p}{p}_{\lambda }=\prod _{k\ge 1}\frac{1}{1-p_k}$$

Finally, let’s look at $\mathcal{C}$. For $\alpha \in {\mathcal{C}}_X$, let $⟨\alpha ⟩\subseteq {\mathcal{S}}_X$ be the cycle subgroup generated by $\alpha$. Then $Aut(\mathcal{C}{)}_X=\{(\alpha ,\sigma )\in {\mathcal{C}}_X\times {\mathcal{S}}_X:\sigma \in ⟨\alpha ⟩\}$. If $\alpha \in {\mathcal{C}}_{[n]}$, then $⟨\alpha ⟩$ has $\varphi (\ell )$ permutations of cycle type $(\ell ,\ell ,...,\ell )$ for all $\ell \mid n$. Thus $$\begin{array}{rl}{Z}_{\mathcal{C}}& =\sum _{n\ge 1}\frac{1}{n!}\#{\mathcal{C}}_n\sum _{\ell \mid n}\varphi (\ell )p_{\ell }^{n/\ell }\\ & =\sum _{n\ge 1}\sum _{\ell \mid n}\frac{1}{n}\varphi (\ell )p_{\ell }^{n/\ell }\\ & =\sum _{d\ge 1}\sum _{\ell \ge 1}\frac{1}{\ell \cdot d}\varphi (\ell )p_l^d=\sum _{\ell \ge 1}\frac{\varphi (\ell )}{\ell }\log (\frac{1}{1-p_{\ell }})\end{array}$$

Theorem 5.3.27 (Main Theorem). Let $\mathcal{A},\mathcal{B}$ be two species, with $Z_{\mathcal{A}}=\sum a_{\lambda }\frac{p_{\lambda }}{z_{\lambda }}$ and $Z_{\mathcal{B}}=\sum b_{\lambda }\frac{p_{\lambda }}{z_{\lambda }}$. Then:

1.	$\mathcal{A}\pm \mathcal{B}$ has cycle index function $Z_{\mathcal{A}}\pm Z_{\mathcal{B}}$.
2.	$K\times \mathcal{A}$ has cycle index function $|K|\cdot Z_{\mathcal{A}}$.
3.	$\mathcal{A}\ast \mathcal{B}$ has CIF $Z_{\mathcal{A}}{Z}_{\mathcal{B}}$.
4.	$\mathcal{A}⊠\mathcal{B}$ has CIF $Z_{\mathcal{A}}⊠Z_{\mathcal{B}}:={\sum }_{\lambda \in p}{a}_{\lambda }{b}_{\lambda }\frac{p_{\lambda }}{z_{\lambda }}$.
5.	${\mathcal{A}}^{\ast }$ has CIF $(1-Z_{\mathcal{A}}{)}^{-1}$ provided its defined.
6.	${\mathcal{A}}^{\prime }$ has CIF $\frac{\partial }{\partial p_1}{Z}_{\mathcal{A}}$.
7.	${\mathcal{A}}^{\bullet }$ has CIF $p_1\frac{\partial }{\partial p_1}{Z}_{\mathcal{A}}$.
8.	$\mathcal{A}\circ \mathcal{B}$ has CIF $Z_{\mathcal{A}}\circ Z_{\mathcal{B}}$ if $B$ is connected.

Corollary 5.3.28. The TGF of $\mathcal{A}\circ \mathcal{B}$ is $Z_{\mathcal{A}}[\tilde{B}(x)]$.

Proof. We have $Z_{\mathcal{A}\circ \mathcal{B}}[x]=Z_{\mathcal{A}}\circ Z_{\mathcal{B}}[x]=Z_{\mathcal{A}}[Z_{\mathcal{B}}[x]]=Z_{\mathcal{A}}[\tilde{B}(x)]$

$\square$

Example 5.3.29. We revisit the colouring of $n$-gon. Previously, we see $Y=K^{{\mathbb{Z}}_n}$ where $K$ is the set of colours with $C_n$-action. Then $Y^{sp}\equiv {\mathcal{C}}_n[K\times \mathcal{X}]\equiv \mathcal{C}[K\times \mathcal{X}]$. Then $|\tilde{Y}|=[x^n]\widetilde{Y^{sp}}(x)=[x^n]Z_{\mathcal{C}}[kx]$. The cycle index function for $\mathcal{C}$ evaluated at $kx$ is$$\left(\sum _{\ell \ge 1}\frac{\varphi (\ell )}{\ell }\log (\frac{1}{1-p_{\ell }})\right)[kx]=\sum _{\ell \ge 1}\frac{\varphi (\ell )}{\ell }\log (\frac{1}{1-k{x}^{\ell }})$$We can just expand this and get$$\sum _{\ell \ge 1}\frac{\varphi (\ell )}{\ell }\log (\frac{1}{1-k{x}^{\ell }})=\sum _{\ell \ge 1}\sum _{d\ge 1}\frac{\varphi (\ell )}{\ell }\frac{k^d{x}^{dl}}{d}=\sum _{n\ge 1}\left(\frac{1}{n}\sum _{d\mid n}\varphi (\frac{n}{d})k^d\right)x^n$$

Example 5.3.30 (Rooted Trees). Consider rooted trees. We see ${\mathcal{T}}^{\bullet }\equiv \mathcal{X}\ast \mathcal{E}[{\mathcal{T}}^{\bullet }]$. Thus$$\widetilde{T^{\bullet }}(x)=x\cdot Z_{\mathcal{E}}[\widetilde{T^{\bullet }}(x)]$$Write $\widetilde{T^{\bullet }}(x)={\sum }_{m\ge 1}{t}_m{x}^m$ then$$Z_{\mathcal{E}}[\widetilde{T^{\bullet }}(x)]=\prod _{m\ge 1}(1-x^m{)}^{-t_m}$$Compare coefficients of $x^n$ on both sides, we get$$t_n=[x^{n-1}]\prod _{m=1}^{n-1}(1-x^m{)}^{-t_m}$$which is a recurrence relation which defines $t_n$ in terms of $t_1,...,t_{n-1}$.

Example 5.3.31 (Endofunctions). We see $\mathcal{N}\equiv \mathcal{S}[{\mathcal{T}}^{\bullet }]$, then ${\mathcal{Z}}_{\mathcal{S}}={\prod }_{k\ge 1}\frac{1}{1-p_k}$. Then$$\tilde{N}(x)=Z_{\mathcal{S}}[\widetilde{T^{\bullet }}(x)]=\prod _{k\ge 1}\frac{1}{1-\widetilde{T^{\bullet }}(x^k)}$$

Example 5.3.32 (Unrooted Trees). There is no general way to get $\tilde{A}(x)$ from $\widetilde{A^{\bullet }}(x)$, but for trees there is a trick.

In particular, we have$$\tilde{T}(x)=([p_1-\frac{1}{2}{p}_2^2+\frac{1}{2}{p}_2])[\widetilde{T^{\bullet }}(x)]$$To see this, we note there are two types of unlabelled trees:

1.	Trees for which every automorphism has a fixed vertex.
2.	Trees which have a fixed point free automorphism.

For $\tau \in \tilde{\mathcal{T}}$, let $v_{\tau }$ be the number of ways to root at vertex up to isomorphism. We also let $e_{\tau }$ be the number of ways to root at edge up to isomorphism.

For type $1$, we have $v_{\tau }-e_{\tau }=1$ and for type $2$ we get $v_{\tau }-e_{\tau }=0$. Next, note the number of unrooted trees is equal the number of vertex rooted trees minus number of edge rooted trees plus number of type $2$ trees.