3. Exponential Generating Functions

3.1Species

在这一章节中, 我们会考虑指数生成函数. 其内蕴的哲学思想依旧是通过生成函数来解决组合问题, 不过这一次, 不同于普通生成函数, 我们所面对的问题往往会有一个置换群的群作用, 而我们会想要计数的对象则变成了等价类. 所以, 传统代数组合中指数生成函数的定义则是 $P(x)={\sum }_{p\in \mathcal{P}}\frac{x^{w(p)}}{n!}$, 而非单纯的 ${\sum }_{p\in \mathcal{P}}{x}^{w(p)}$.

在这一份讲义中, 我们会考虑一种更为系统的研究, 也就是通过组合物种这一框架/语言来研究关于指数生成函数的问题.

对于范畴论较为熟悉的同学不难看出, 在下述定义中, 一个组合物种 $\mathcal{A}$ 其实就是一个函子 $F:\mathcal{S}\to \mathcal{S}$, 其中 $\mathcal{S}$ 的对象为有限集合, 态射为集合之间的双射 $S\stackrel{\sim }{\to }{S}^{\prime }$.

然而, 在实际使用中, 我们完全不会去使用任何的范畴论语言, 甚至下面给出的更为具体的定义也并不是最好的去思考组合物种的方法. 我们将会把组合物种考虑为一种把组合对象添加标签的方式. 举例来说, 如果我们考虑树这个组合对象, 那么树的组合物种则是, 把没有标签的树添加标签的过程.

举例来说, 你可以把树的组合物种想象成是一个 " 工厂 ", 然后里面有各种各样的 " 原材料 " (它们是没有标签的树). 然后, 我作为 " 客户 ", 给这个 " 工厂 " 一个 " 订单 "(一个大小为 $n$ 的有限集合 $S$), 然后工厂里的工人就开始没日没夜地把大小为 $n$ 的没有标签的树全部提出来, 开始给这些没有标签的树根据我给出的有限集合上标签.

Example 3.1.1 (Graphs). We note there is no set of all graphs, i.e. the class of all graphs form a proper class. Thus, we need to add definite constrains to make the proper class into a set.

In other word, given a finite set $X$, we can form the set ${\mathcal{G}}_X$ of graphs on $X$ given by$${\mathcal{G}}_X=\{\text{ all graphs }\Gamma :V(\Gamma )=X\}$$. In particular, we see the following properties:

1.	If $|X|=|Y|=n$ then $|{\mathcal{G}}_X|=|{\mathcal{G}}_Y|=2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$.
2.	We have isomorphism: it is a bijection $f:V(\Gamma )\to V({\Gamma }^{\prime })$ such that $(u,v)\in E(\Gamma )$ if and only if $(f(u),f(v))\in E({\Gamma }^{\prime })$.
3.	If $f:X\to Y$ is a bijection and we have $\Gamma \in {\mathcal{G}}_X$, then there is a unique graph ${\Gamma }^{\prime }\in {\mathcal{G}}_Y$, such that $f$ is an isomorphism of graphs.
4.	In other word, a bijection of sets $f:X\to Y$ induces a bijection $f_{\ast }:{\mathcal{G}}_X\to {\mathcal{G}}_Y$.

Definition 3.1.2. A species $\mathcal{A}$ is a rule that assigns:

1.	To every finite set $X$, a (finite) set ${\mathcal{A}}_X$ called the set of $\mathcal{A}$-structures on $\mathbf{X}$.
2.	To every bijection $f:X\to Y$ of finite sets, we get a bijection $f_{\ast }:{\mathcal{A}}_X\to {\mathcal{A}}_Y$. This is called a transportation of $\mathbf{A}$-structures along $\mathbf{f}$.

such that:

1.	If $X\ne Y$ then ${\mathcal{A}}_X\cap {\mathcal{A}}_Y=\varnothing$.
2.	If ${\mathrm{Id}}_{\mathrm{X}}:\mathrm{X}\to \mathrm{X}$ is the identity map, then the transportation ${\mathrm{Id}}_{\mathrm{X},\ast }:{\mathcal{A}}_{\mathrm{X}}\to {\mathcal{A}}_{\mathrm{X}}$ should be the identity.
3.	If $f:X\to Y$ and $g:Y\to Z$ are bijections, then $(g\circ f{)}_{\ast }=g_{\ast }\circ f_{\ast }$.

Definition 3.1.3. Let $\mathcal{A}$ be a species, and $\alpha \in {\mathcal{A}}_X,\beta \in {\mathcal{A}}_Y$, then we say $\alpha$ and $\beta$ are isomorphic if and only if there exists bijection $f:X\to Y$ such that $f_{\ast }(\alpha )=\beta$.

Definition 3.1.4. Let $\mathcal{A}$ be a species, assume ${\mathcal{A}}_X$ is finite for every finite set $X$. Then if $|X|=|Y|=n$, we must have $|{\mathcal{A}}_X|=|{\mathcal{A}}_X|$ and hence we define $|{\mathcal{A}}_n|:=|{\mathcal{A}}_X|$ for any set $X$ with $|X|=n$. Then we define the exponential generating function associated with $\mathcal{A}$ to be$$A(x):=\sum _{n\ge 0}|{\mathcal{A}}_n|\frac{x^n}{n!}$$

Example 3.1.5. We have the following examples of species:

Name/Notation	Structures on $X$	Transport along $f:X\to Y$	EGF
Sets($\mathcal{E}$)	$X$, i.e. ${\mathcal{E}}_X=\{X\}$	$f_{\ast }(X)=Y$	$E(x)={\sum }_{n\ge 0}1\frac{x^n}{n!}=e^x$
Linear Orders($\mathcal{L}$)	${\mathcal{L}}_X=\{(x_1,...,x_n):|X|=n,X=\{x_1,...,x_n\}\}$	$f_{\ast }(x_1,...,x_n)=(f(x_1),...,f(x_n))$	$L(x)={\sum }_{n\ge 0}n!\frac{x^n}{n!}=\frac{1}{1-x}$
Endofunctions($\mathcal{N}$)	${\mathcal{N}}_X=\{\alpha :X\to X\}$	$f_{\ast }(\alpha )=f\circ \alpha \circ f^{-1}$	$N(x)={\sum }_{n\ge 0}{n}^n\frac{x^n}{n!}$
Permutations $(\mathcal{S})$	${\mathcal{S}}_X=\{\alpha :X\to X\text{ is bijection}\}$	$f_{\ast }(\alpha )=f\circ \alpha \circ f^{-1}$	$S(x)={\sum }_{n\ge 0}n!\frac{x^n}{n!}=\frac{1}{1-x}$
Cyclic Permutations($\mathcal{C}$)	${\mathcal{C}}_X=\{\alpha :X\to X\text{ is a cycle}\}$	$f_{\ast }(\alpha )=f\circ \alpha \circ f^{-1}$	$C(x)={\sum }_{n\ge 1}(n-1)!\frac{x^n}{n!}=\log (\frac{1}{1-x})$
Trees ($\mathcal{T}$)	${\mathcal{T}}_X=\{\tau \in {\mathcal{G}}_X:\tau \text{ is a tree}\}$	same as graph	$T(x)={\sum }_{n\ge 1}{n}^{n-2}\frac{x^n}{n!}$
Set Partitions($\Pi$)	${\Pi }_X$ is set partitions of $X$	$f_{\ast }(\{X_1,..,X_k\})=\{f(X_1),...,f(X_k)\}$	$\Pi (x)={\sum }_{n\ge 0}{B}_n\frac{x^n}{n!}$

We remark for the last one, $B_n$ are called the Bell numbers and ${\Pi }_X$ is equal $\{\{X_1,...,X_k\}:k\ge 1,X_i\subseteq X,X_i\cap X_j=\varnothing ,X=\bigcup X_i\}$

Definition 3.1.6. Let $\mathcal{A},\mathcal{B}$ be two species. A natural transformation $\Phi :\mathcal{A}\to \mathcal{B}$ is a rule which assigns to every finite set $X$ a function ${\Phi }_X:{\mathcal{A}}_X\to {\mathcal{B}}_Y$, such that if $f:X\to Y$ is a bijection of sets, then the following diagram commutes:

Example 3.1.7.

1.	We have a natural transformation from trees to graphs by inclusion (if we have a sub-species then inclusion is always a natural transformation).
2.	From directed graphs to graphs we have the forgetful natural transformation, i.e. we forget the direction of edges.
3.	From endofunctions to directed graphs we have a natural transformation as follows. Given $\alpha :X\to X$, the edges are given by $(x,\alpha (x))$.
4.	From any species to sets we get a natural transformation by forgetful natural transformation.
5.	From graphs to graphs we have the graph complement as a natural transformation.

Lemma 3.1.8. If $\alpha \in {\mathcal{A}}_X,\beta \in {\mathcal{A}}_Y$ are isomorphic, then ${\Phi }_X(\alpha )$ and ${\Phi }_Y(\beta )$ are isomorphic.

Definition 3.1.9. Let $\Phi$ be a natural transformation. If ${\Phi }_X:{\mathcal{A}}_X\to {\mathcal{B}}_X$ is a bijection for all finite set $X$, then we say $\Phi$ is a natural equivalence and we say $\mathcal{A}$ and $\mathcal{B}$ are naturally equivalent and write $\mathcal{A}\equiv \mathcal{B}$.

Example 3.1.10.

1.	The graph complement is an equivalence from graphs to graphs.
2.	Let $\mathcal{G}$ be the species of graphs and $\hat{\mathcal{G}}$ be the species of pairs of equal graphs, i.e. ${\hat{\mathcal{G}}}_X=\{(\Gamma ,\Gamma ):\Gamma \in {\mathcal{G}}_X\}$. Then the map $\Gamma \mapsto (\Gamma ,\Gamma )$ is a natural equivalence.
3.	We have an equivalence between $\mathcal{S}$ the species of permutations and the sub-species of $\mathcal{G}$ where the graphs has every vertex with in-degree $1$ and out-degree $1$.

Definition 3.1.11. We say two species $\mathcal{A}$ and $\mathcal{B}$ are numerically equivalent if $A(x)=B(x)$ and write $\mathcal{A}\approx \mathcal{B}$.

Remark 3.1.12. We note natural equivalence implies numerically equivalence but not vice versa.

Example 3.1.13. We see $\mathcal{L}$ and $\mathcal{S}$ are numerically equivalent but $\mathcal{L}\not\equiv \mathcal{S}$.

Proof. Suppose $\Phi :\mathcal{L}\to \mathcal{S}$ is a natural transformation. Any two $\mathcal{L}$-structure of same order are isomorphic. But this is not true for $\mathcal{S}$ and hence $\Phi$ cannot be natural equivalence by the lemma above.

$\square$

Definition 3.1.14. A species $\mathcal{A}$ is connected if and only if ${\mathcal{A}}_{\varnothing }=\varnothing$.

Remark 3.1.15 (Labelled & Unlabelled Diagrams). Given a species $\mathcal{A}$, we can think $\mathcal{A}$-structures on $X$ as diagrams with “widgets” that are labelled by elements of $X$.

For example, we can think ${\mathcal{S}}_{[3]}$ as graphs with each vertex has in-degree $1$ and out-degree $1$: We could also have some examples of species that are not “graph-like” but still represented by diagrams. For instance, consider set partitions, and we have the set partition $\{\{1,3,4\},\{2,7\},\{5,6\}\}$ correspond to the following tableau (can’t draw tableau here...)$$\begin{array}{ccc}1& 3& 4\\ 2& 7& \\ 5& 6& \end{array}$$

With this point of view of species, the transportations of $\mathcal{A}$-structures are always relabelling of our diagrammatic objects. Then the isomorphism types in this diagrammatic point of view are just unlabelled drawings and now we consider the widgets as “label receivers”. Also, the “order” of species $\mathcal{A}$ in this context is just the number of label receivers.

We will write $\tilde{\mathcal{A}}$ for the set of isomorphism types of species $\mathcal{A}$. Then, we can just think species $\mathcal{A}$ as a set of isomorphism types plus a labelling operation.

For example, consider the species of trees, $\mathcal{T}$. Then we have some of the isomorphism types as

To form ${\mathcal{T}}_{[4]}$, we see we have two isomorphism types with $4$ nodes, and we just need to label them with $[4]=\{1,2,3,4\}$ and this gives us the set ${\mathcal{T}}_{[4]}$, where we are going to list some examples:

3.2Species Operations

Remark 3.2.1. In this section, $\mathcal{A},\mathcal{B}$ will always be species.

Definition 3.2.2 (Sum and Difference). We define $\mathcal{A}+\mathcal{B}$ as follows. The structures are given by$$(\mathcal{A}+\mathcal{B}{)}_X={\mathcal{A}}_X\coprod {\mathcal{B}}_X=\{1\}\times {\mathcal{A}}_X\cup \{2\}\times {\mathcal{B}}_X$$as the disjoint union of ${\mathcal{A}}_X$ and ${\mathcal{B}}_X$. This construction extends to infinite sums. In terms of isomorphism types, we have $\widetilde{\mathcal{A}+\mathcal{B}}=\tilde{\mathcal{A}}\coprod \tilde{\mathcal{B}}$.

Now assume $\mathcal{B}\subseteq \mathcal{A}$, i.e. ${\mathcal{B}}_X\subseteq {\mathcal{A}}_X$ for all $X$. Then we define $(\mathcal{A}-\mathcal{B}{)}_X={\mathcal{A}}_X\backslash {\mathcal{B}}_X$.

Definition 3.2.3 (Filtering by Order). We define ${\mathcal{A}}_n,{\mathcal{A}}_{+},{\mathcal{A}}_{even},{\mathcal{A}}_{odd}$.

The definitions are given as follows$$({\mathcal{A}}_n{)}_X=\{\begin{array}{l}{\mathcal{A}}_X,|X|=n\\ \varnothing ,\text{ otherwise}\end{array}$$$$({\mathcal{A}}_{+}{)}_X=\{\begin{array}{l}{\mathcal{A}}_X,\text{ if }|X|>0\\ \varnothing ,\text{ otherwise}\end{array}$$$$({\mathcal{A}}_{even/odd})=\{\begin{array}{l}{\mathcal{A}}_X,\text{ if }|X|\text{ is even/odd}\\ \varnothing ,\text{ otherwise}\end{array}$$

Example 3.2.4. For example, we have ${\mathcal{E}}_{+}$ is the non-empty set operation. We also define ${\mathcal{E}}_1$ to be the species of singletons and denoted by $\mathcal{X}$. Finally we have ${\mathcal{E}}_0:=1$.

Definition 3.2.5 (Products). We define $\mathcal{K}\times \mathcal{A},\mathcal{A}\ast \mathcal{B},\mathcal{A}⊠\mathcal{B}$.

The first one is Cartesian product with a set. Here $\mathcal{K}$ is a set, usually finite, and we define$$(\mathcal{K}\times \mathcal{A}{)}_X=\mathcal{K}\times {\mathcal{A}}_X$$

The second one is species product. The species product is defined as follows$$(\mathcal{A}\ast \mathcal{B}{)}_X=\coprod _{S\subseteq X}{\mathcal{A}}_S\times {\mathcal{B}}_{X\backslash S}$$

We note the following:

1.	To put an $\mathcal{A}\ast \mathcal{B}$ structure on $X$, we do the following: 1. partition $X$ into $(S,X\backslash S)$. 2. put an $\mathcal{A}$ structure on $S$. 3. put a $\mathcal{B}$ structure on $X\backslash A$.
2.	By default, ${\mathcal{A}}^m:=\mathcal{A}\ast \mathcal{A}\ast ...\ast \mathcal{A}$.
3.	$1$ is the multiplicative identity of this multiplication.
4.	We note $\widetilde{\mathcal{A}\ast \mathcal{B}}=\tilde{\mathcal{A}}\times \tilde{\mathcal{B}}$.

The third one is called superposition or Hadamard product. It is defined as$$(\mathcal{A}⊠\mathcal{B}{)}_X:={\mathcal{A}}_X\times {\mathcal{B}}_X$$

Definition 3.2.6 (Sequence). We define the sequence ${\mathcal{A}}^{\ast }$ by$${\mathcal{A}}^{\ast }=\sum _{n\ge 0}{\mathcal{A}}^n$$where ${\mathcal{A}}^0=1$. We note:

1.	If $\mathcal{A}$ is connected and ${\mathcal{A}}_X$ is finite for all $X$, then ${\mathcal{A}}_X^{\ast }$ is connected and ${\mathcal{A}}_X$ is fintie.
2.	$\widetilde{{\mathcal{A}}^{\ast }}=(\tilde{A}{)}^{\ast }$

Definition 3.2.7 (Rooting and Derivatives). We define ${\mathcal{A}}^{\bullet }$ and ${\mathcal{A}}^{\prime }$.

The rooting ${\mathcal{A}}^{\bullet }$ (aka marking or pointing) is defined by$${\mathcal{A}}_X^{\bullet }={\mathcal{A}}_X\times X$$

The derivative ${\mathcal{A}}^{\prime }$ (aka mark and delete) is defined by$${\mathcal{A}}_X^{\prime }={\mathcal{A}}_{X\coprod \{\ast \}}$$where $\{\ast \}$ is an element not in $X$.

We note:

1.	$\widetilde{{\mathcal{A}}^{\bullet }}$ is more or less $\widetilde{{\mathcal{A}}^{\prime }}$ and the difference is how we interprete them.
2.	${\mathcal{A}}^{\bullet }\equiv \mathcal{X}\ast {\mathcal{A}}^{\prime }$

Definition 3.2.8 (Composition). We define $\mathcal{A}[\mathcal{B}]$ (or $\mathcal{A}\circ \mathcal{B}$). We assume $\mathcal{B}$ is connected.

Then we define$$\mathcal{A}[\mathcal{B}{]}_X=\coprod _{\{X_1,...,X_k\}\in {\Pi }_X}{\mathcal{A}}_{\{X_1,...,X_k\}}\times {\mathcal{B}}_{X_1}\times {\mathcal{B}}_{X_2}\times ...\times {\mathcal{B}}_{X_k}$$We note:

1.	To put an $\mathcal{A}[\mathcal{B}]$-structure on $X$, we do the following: 1. Form a set partition $\{X_1,...,X_k\}$ of $X$. 2. Put an $\mathcal{A}$-structure on $\{X_1,...,X_k\}$, which is a set with $k$ elements. 3. Put a $\mathcal{B}$-structure on each $X_i$ for $i=1,...,k$. 4. We note $k$ is not fixed here.
2.	Unlabelled $\mathcal{A}[\mathcal{B}]$-structure constructed as follows: 1. Start with unlabelled $\mathcal{A}$-structure $\alpha$ 2. Replace each label receiver in $\alpha$ by $\mathcal{B}$-structure ${\beta }_i$. 3. Label receiver of composite object are label receivers of ${\beta }_i$.

Example 3.2.9.

1.	$\mathcal{E}[\mathcal{J}]$ is the species of forest.
2.	${\mathcal{E}}_2[\mathcal{J}]$ is the forest with 2 components. We note ${\mathcal{E}}_2[\mathcal{J}]\not\equiv {\mathcal{J}}^2$ as $|{\mathcal{J}}_X^2|=2|{\mathcal{E}}_2[\mathcal{J}{]}_X|$
3.	$\mathcal{E}[\mathcal{C}]=\mathcal{S}$.
4.	$\mathcal{L}[\mathcal{B}]={\mathcal{B}}^{\ast }$.
5.	$\mathcal{N}\equiv \mathcal{S}[{\mathcal{T}}^{\bullet }]$.

Theorem 3.2.10. Suppose we have $\mathcal{A},\mathcal{B}$ be two species with $A(x)=\sum a_n\frac{x^n}{n!}$ and $B(x)=\sum b_n\frac{x^n}{n!}$, then:

1.	Sum and Difference: ∘ $\mathcal{A}+\mathcal{B}\Rightarrow A(x)+B(x)$ ∘ $\mathcal{A}-\mathcal{B}\Rightarrow A(x)-B(x)$
2.	Filters ∘ ${\mathcal{A}}_n\Rightarrow a_n\frac{x^n}{n!}$ ∘ ${\mathcal{A}}_{+}\Rightarrow {\sum }_{n\ge 1}{a}_n\frac{x^n}{n!}$ ∘ ${\mathcal{A}}_{even}\Rightarrow \frac{1}{2}(A(x)+A(-x))$ ∘ ${\mathcal{A}}_{odd}\Rightarrow \frac{1}{2}(A(x)-A(-x))$
3.	Products ∘ $\mathcal{K}\times \mathcal{A}\Rightarrow |\mathcal{K}|A(x)$ ∘ $\mathcal{A}\ast \mathcal{B}\Rightarrow A(x)B(x)$ ∘ $\mathcal{A}⊠\mathcal{B}\Rightarrow {\sum }_{n\ge 0}{a}_n{b}_n\frac{x^n}{n!}$
4.	Sequence: ${\mathcal{A}}^{\ast }\Rightarrow \frac{1}{1-A(x)}$
5.	Derivatives and Rooting ∘ ${\mathcal{A}}^{\prime }\Rightarrow \frac{d}{dx}A(x)=A^{\prime }(x)$ ∘ ${\mathcal{A}}^{\ast }\Rightarrow x{A}^{\prime }(x)$
6.	Composition: $\mathcal{A}[\mathcal{B}]\Rightarrow A(B(x))$

Proof. All of the proofs are elementary counting.

For example, we consider $\mathcal{A}\ast \mathcal{B}$. We see $$\begin{array}{rl}|(\mathcal{A}\ast \mathcal{B}{)}_X|& =\sum _{S\subseteq X}|{\mathcal{A}}_S|\cdot |{\mathcal{B}}_{X\backslash S}|\\ & =\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)|{\mathcal{A}}_k|\cdot |{\mathcal{B}}_{n-k}|\\ & =n!\sum _{k=0}^n\frac{1}{k!}{a}_k\cdot \frac{1}{(n-k)!}{b}_{n-k}\\ & =n![x^n]A(x)B(x)\end{array}$$

$\square$

3.3Examples

Remark 3.3.1. We have some common notations. If $A(x)=\sum a_n\frac{x^n}{n!}$ then we write $[\frac{x^n}{n!}]A(x)=a_n$. We note we have $[\frac{x^n}{n!}]A(x)=n![x^n]A(x)$ and hence this operation is not linear.

Example 3.3.2 (Connected Graphs). Let $\mathcal{G}$ be graphs and ${\mathcal{G}}^c$ be connected graphs. We know $\mathcal{G}\equiv \mathcal{E}[{\mathcal{G}}^c]$ and therefore we have$$G(x)=\exp (G^c(x))$$where we know $G(x)=\sum 2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}\frac{x^n}{n!}$. Hence we see$$G^c(x)=\log (\sum _{n\ge 0}{2}^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}\frac{x^n}{n!})$$

Example 3.3.3 (Permutations with even number of cycles). The species we want to consider is ${\mathcal{E}}_{even}[\mathcal{C}]$. We see $E_{even}(x)=\frac{1}{2}(e^x+e^{-x})=\cosh x$ and $C(x)=\log (\frac{1}{1-x})$ and hence we see$$E_{even}(C(x))=\cosh \log (\frac{1}{1-x})=\frac{1}{2}(\frac{1}{1-x}+1-x)=1+\frac{3}{2}\frac{x^2}{1-x}$$Thus the number of permutations of $[n]$ with an even number of cycles is$$[\frac{x^n}{n!}](1+\frac{3}{2}\frac{x^2}{1-x})=\{\begin{array}{l}1,n=0\\ 0,n=1\\ \frac{1}{2}n!,\text{ otherwise}\end{array}$$

Example 3.3.4 (Surjective Functions). How many surjective functions $f:[m]\to [k]$?

Method 1: Fix $m$ and let $\mathcal{A},\mathcal{B}$ be the species ${\mathcal{A}}_X=\{\text{all functions }f:[m]\to X\}$ and ${\mathcal{B}}_X=\{\text{surjective functions }f:[m]\to X\}$. Then we have$$\mathcal{A}\equiv \mathcal{B}\ast \mathcal{E}$$where we are going to think $\mathcal{B}$ as surjective functions onto subset $S\subseteq X$ and $\mathcal{E}$ is just the set $X\backslash S$. Thus we see$$A(x)=\sum _{n\ge 0}{n}^m\frac{x^n}{n!}=B(x)e^x$$and hence$$B(x)=e^{-x}\sum _{n\ge 0}{n}^m\frac{x^n}{n!}$$and the answer is $[\frac{x^k}{k!}]B(x)$.

Method 2: Fix $k$ and let $\mathcal{H}$ be the species given by$${\mathcal{H}}_X=\{\text{surjective functions }f:X\to [k]\}$$Then we see$$\mathcal{H}\equiv {\mathcal{E}}_{+}\ast {\mathcal{E}}_{+}\ast ...\ast {\mathcal{E}}_{+}=({\mathcal{E}}_{+}{)}^k$$as $k$ products, where given $f:X\to [k]$ we think the $k$ products as $f^{-1}(1),...,f^{-1}(k)$.

Thus we see$$H(x)=(e^x-1{)}^k$$and hence the answer is $[\frac{x^m}{m!}]H(x)$.

Example 3.3.5 (Trees). The species of trees have no natural decomposition. On the other hand, species of rooted trees does. In particular, we have$${\mathcal{T}}^{\bullet }\equiv \mathcal{X}\ast \mathcal{E}[{\mathcal{T}}^{\bullet }]$$where $\mathcal{X}$ is the root and $\mathcal{E}[{\mathcal{T}}^{\bullet }]$ is the set of rooted tree branches. Thus we get$$T^{\bullet }(x)=x{e}^{T^{\bullet }(x)}$$and apply LIFT we get$$[x^n]T^{\bullet }(x)=\frac{n^{n-1}}{n!}$$and hence$$T^{\bullet }(x)=\sum _{n\ge 1}\frac{n^{n-1}}{n!}{x}^n$$However, note each tree has $n$ ways to root the trees, and therefore we see$$T(x)=\sum _{n\ge 1}\frac{n^{n-2}}{n!}{x}^n$$and we conclude the number of trees of $n$ nodes is $n^{n-2}$.

Example 3.3.6 (Trivalent trees). Let $\mathcal{A}$ be the species of trees in which every vertex has degree $1$ or $3$. We will use the same trick and first look at the corresponding rooted structure.

However, note given a trivalent tree and if we break up, we do not get a set of trivalent trees and hence we we need to find something else in the recursive definition of ${\mathcal{A}}^{\bullet }$.

What we want to use is $\mathcal{B}$, the rooted trees in which every vertex has updegree $0$ or $2$. Then we get$${\mathcal{A}}^{\bullet }\equiv \mathcal{X}\ast \mathcal{B}+\mathcal{X}\ast {\mathcal{E}}_3[\mathcal{B}]$$$${\mathcal{B}}^{\bullet }\equiv \mathcal{X}+\mathcal{X}\ast {\mathcal{E}}_2[\mathcal{B}]$$By the above two relations, we get$$A^{\bullet }(x)=xB(x)+x\frac{1}{6}B(x{)}^3$$$$B(x)=x+\frac{1}{2}xB(x{)}^2$$

Therefore$$[x^{2n}]A^{\bullet }(x)=[x^{2n}]x(B(x)+\frac{1}{6}B(x{)}^3)=[x^{2n-1}](B(x)+\frac{1}{6}B(x{)}^3)$$Now use LIFT we see$$[x^{2n}]A^{\bullet }(x)=\frac{1}{2n-1}[{\lambda }^{2n-2}]\frac{d}{d\lambda }(\lambda +\frac{1}{6}{\lambda }^3)\cdot (1+\frac{1}{2}{\lambda }^2{)}^{2n-1}=\frac{1}{2n-1}{\left(\frac{1}{2}\right)}^{n-1}(\genfrac{}{}{0ex}{}{2n}{n-1})$$Thus we see$$|{\mathcal{A}}_{2n}^{\bullet }|=(2n)!\frac{1}{2n-1}{\left(\frac{1}{2}\right)}^{n-1}(\genfrac{}{}{0ex}{}{2n}{n-1})$$and hence$$|{\mathcal{A}}_{2n}|=\frac{1}{2n}|{\mathcal{A}}_{2n}^{\bullet }|=(2n-3)!!(2n{)}^{\underline{n-1}}$$