4. Multivariate Generating Functions

4.1Mixed Generating Functions

在这一章中, 我们主要考虑更为自由一些的生成函数. 准确来说, 我们可能会考虑, 在两个变量的情况下, 一个变量的计数需要考虑置换群的作用, 而另一个则不需要.

Definition 4.1.1. Let $\mathcal{A}$ be a species, a weight function $wt:\mathcal{A}\to \mathbb{N}$ is a rule that assigns to every $\mathcal{A}$-structure $\alpha$ a weight $wt(a)\in \mathbb{N}$ such that if $\alpha ,\beta$ are isomorphic $\mathcal{A}$-structures then $wt(a)=wt(b)$.

Remark 4.1.2.

1.	Weight functions on species are not functions from set theory because $\mathcal{A}$ is not a set. Nonetheless, its restriction to ${\mathcal{A}}_X$ is a indeed a weight function from ${\mathcal{A}}_X\to \mathbb{N}$.
2.	Thus, it is not hard to see, a weight function $wt:\mathcal{A}\to \mathbb{N}$ is the same as specifying a weight function $\mathcal{A}\to \mathbb{N}$.
3.	We will no longer require ${\mathcal{A}}_X$ to be finite.

Example 4.1.3.

1.	For species of graphs, we can define a weight as the number of edges.
2.	For trees, a weight is the number of leaves.
3.	For endofunctions, a weight is the number of fixed points.
4.	For permutations, a weight is the number of cycles.
5.	For any species, a weight is the order itself.
6.	For any species, a weight is the constant weight.

Definition 4.1.4. A weighted species is a species $\mathcal{A}$ with one or more weight functions $w{t}_1,...,w{t}_n,...$.

Remark 4.1.5. For any finite set $X$, we can form OGF for ${\mathcal{A}}_X$ as$$A_X(t)=A_X(t_1,t_2,...)=\sum _{\alpha \in {\mathcal{A}}_X}{t}_1^{w{t}_1(\alpha )}{t}_2^{w{t}_2(\alpha )}...$$

If $|X|=|Y|=n$ then $A_X(t)=A_Y(t）$ and hence we will just write $A_n(t)$ for $|X|=n$.

Definition 4.1.6. Let $\mathcal{A}$ be a weighted species, then the mixed generating function (MGF) of $\mathcal{A}$ is$$A(x;t)=\sum _{n\ge 0}{A}_n(t)\frac{x^n}{n!}$$

Example 4.1.7. Let $\mathcal{Y}$ be the species of graphs and weight functions to be the number of edges. Then we see $G_n(t)=(1+t{)}^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$ and hence$$G(x;t)=\sum _{n\ge 0}(1+t{)}^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}\frac{x^n}{n!}$$

Definition 4.1.8. Let $\mathcal{A},\mathcal{B}$ be weighted species with weight functions $wt:\mathcal{A}\to \mathbb{N}$ and $w{t}^{\prime }:\mathcal{B}\to \mathbb{N}$. Let $\Phi :\mathcal{A}\to \mathcal{B}$ be a natural transformation. We say $\Phi$ is weight preserving if $w{t}^{\prime }(\Phi (\alpha ))=wt(\alpha )$ for any $\mathcal{A}$-structure $\alpha$. If $\Phi$ is a weight preserving equivalence then $A(x;t)=B(x;t)$.

Remark 4.1.9. We can also extend species operations to weighted species using the principle: The weight of a composite object shoulded be the sum of the weight of its components.

Example 4.1.10. For example:

1.	Consider $\mathcal{A}\ast \mathcal{B}$. Then the structures are $(\alpha ,\beta )$ and hence the natural weight function on $\mathcal{A}\ast \mathcal{B}$ should be $w{t}^{\prime \prime }(\alpha ,\beta )=wt(\alpha )+w{t}^{\prime }(\beta )$.
2.	Consider $\mathcal{A}\circ \mathcal{B}$. The structures are tuples $(\alpha ,{\beta }_1,...,{\beta }_k)$. Thus the weight should be $wt(\alpha )+\sum w{t}^{\prime }({\beta }_i)$.
3.	For rooting ${\mathcal{A}}^{\bullet }$, the structure is $(\alpha ,x)$ where $\alpha$ is a $\mathcal{A}$-structure and $x$ is the root. Thus the weight function on ${\mathcal{A}}^{\bullet }$ is $(\alpha ,x)\mapsto wt(\alpha )$.

Theorem 4.1.11 (Main Theorem). The main theorem is true for MGFs/weighted species.

Remark 4.1.12. A few things to note:

1.	Composition is in $x$ variable. In other word, the composition should be $A(B(x;t);t)$.
2.	Derivatives are now become partial derivatives.
3.	${\mathcal{A}}^{\ast }$ no longer require $\mathcal{A}$ to be connected. Provided the mixed generating function is defined. On the other hand, $\mathcal{A}\circ \mathcal{B}$ still requires $\mathcal{B}$ connected.

Example 4.1.13. Compute the average number of cycles in a permutations of $[n]$. Take $\mathcal{S}$ with weight as the number of cycles, $\mathcal{E}$ with constant weight function $0$, and $\mathcal{C}$ with constant weight function $1$.

With these weight functions, we see $\mathcal{S}\equiv \mathcal{E}(\mathcal{C})$ becomes a weighted equivalent. Then we have$$S(x;t)=\exp (C(x;t))=\exp (t\log (\frac{1}{1-x}))=(1-x{)}^{-t}$$In particular, we see the average number of cycles is then $$\begin{array}{rl}\frac{1}{n!}\sum _{\sigma \in {\mathcal{S}}_{[n]}}wt(\sigma )& =\frac{1}{n}\left(\frac{d}{dt}{S}_n(t)\right){|}_{t=1}\\ & =[x^n]\frac{\partial }{\partial t}S(x;t){|}_{t=1}\\ & =[x^n]\log (\frac{1}{1-x})\frac{1}{1-x}=\sum _{k=1}^n\frac{1}{k}\end{array}$$

Remark 4.1.14. In future, if the weight on a species was not specified, then it was assumed to be $0$.

Example 4.1.15. Compute the average number of $k$-cycles among all permutations of $[n]$. Take $\mathcal{S}$ with weight function equal the number of $k$-cycles and $\mathcal{C}$ with weight $1$ if the order is $k$ and $0$ otherwise.

Again, we have $\mathcal{S}\equiv \mathcal{E}(\mathcal{C})$ is a weighted equivalence. This time, we have$$C(x;t)=x+\frac{x^2}{2}+\frac{x^3}{3}+...+\frac{t{x}^k}{k}+\frac{x^{k+1}}{k+1}+...$$It is not hard to see this is the same as$$C(x;t)=\log (\frac{1}{1-x})+(t-1)\frac{x^k}{k}$$and we can continue as before, and get the final answer to be $\frac{1}{k}$.

Example 4.1.16. If $\alpha :X\to X$ is an endofunction, we say $x\in X$ is a recurrent element, if $\alpha \circ \alpha ...\circ \alpha (x)=x$ where we composed $k$ times for some $k\ge 1$.

Let $\mathcal{N}$ be endofunctions with weight equal the number of recurrent elements. We want to compute $N(x;t)$. Take $\mathcal{S}$ with weight as the order, then $S(x;t)=\frac{1}{1-tx}$. Then $\mathcal{N}\equiv \mathcal{S}({\mathcal{T}}^{\bullet })$ is a weighted equivalence and so$$N(x;t)=S(T^{\bullet }(x);t)=\frac{1}{1-t{T}^{\bullet }(x)}$$Since $T^{\bullet }(x)=x{e}^{T^{\bullet }(x)}$ and hence use LIFT, we get$$N(x;t)=1+\sum _{n\ge 1}\sum _{k=1}^n\frac{k{n}^{n-k-1}}{(n-k)!}{t}^k{x}^n$$

Example 4.1.17. Consider ${\mathcal{T}}^{\bullet }$ with weight as the number of terminals. Consider $\mathcal{E}$ with weight function $1$ if order is $0$ and $0$ otherwise. Then $E(x;t)=e^x+t-1$ and ${\mathcal{T}}^{\bullet }\equiv \mathcal{X}\ast \mathcal{E}({\mathcal{T}}^{\bullet })$ becomes weighted equivalent. Thus we have$$T^{\bullet }(x;t)=x(e^{T^{\bullet }(x;t)}+t-1)$$and use LIFT from here to obtain the solution.

Example 4.1.18. Consider rooted trees with weight function the degree of the root. In this example, we write $\mathcal{A}$ a species with weight function $0$ and $\overline{\mathcal{A}}$ the same species with non-trivial weight.

In this example, we will consider ${\mathcal{T}}^{\bullet }$ and $\overline{{\mathcal{T}}^{\bullet }}$ with weight as the degree of the root. On the other hand, we put a non-trivial weight on $\mathcal{E}$ as $\overline{\mathcal{E}}$ with weight as the order.

We know ${\mathcal{T}}^{\bullet }\equiv \mathcal{X}\ast \mathcal{E}[{\mathcal{T}}^{\bullet }]$ and $\overline{{\mathcal{T}}^{\bullet }}\equiv \mathcal{X}\ast \overline{\mathcal{E}}({\mathcal{T}}^{\bullet })$. Thus $T^{\bullet }(x)=x{e}^{T^{\bullet }(x)}$ and$$\overline{T^{\bullet }}(x;t)=x\exp (t{T}^{\bullet }(x))$$Use LIFT, we get$$\overline{T^{\bullet }}(x;t)=1+\sum _{n\ge 1}\sum _{k=1}^n\frac{1}{k!}\frac{k{n}^{n-k-1}}{(n-k)!}{t}^k{x}^{n-k}$$

4.2Multi-Exponential Generating Functions

Definition 4.2.1. Let $\mathcal{A}$ be a set and $R$ be a commutative ring. Then we define generalized weight function $Wt:\mathcal{A}\to R$. We define $|\mathcal{A}{|}_{Wt}={\sum }_{a\in \mathcal{A}}Wt(a)$.

Example 4.2.2. If $wt:\mathcal{A}\to \mathbb{N}$ as a normal weight function, then let $R=\mathbb{Q}[[x]]$ and $Wt(\alpha ):=x^{wt(\alpha )}$. Then $|\mathcal{A}{|}_{Wt}=A(x)$ is just the OGF of $\mathcal{A}$ with weight $wt$.

Remark 4.2.3. Under operations, our principle for the generalized weight of a composite object is that the weight should be the product of weights.

Example 4.2.4. Let $R=\mathbb{Q}$, consider weight $sgn:\mathcal{A}\to \{\pm 1\}$. Then $|\mathcal{A}{|}_{sgn}=|\{a\in \mathcal{A}:sgn(a)=1\}|-|\{a\in \mathcal{A}:sgn(a)=-1\}|$.

Definition 4.2.5. Let $\mathcal{A}$ be a species and $R$ a ring, we can define generalized weight function $Wt:\mathcal{A}\to R$ to be a rule that assigns $Wt(a)\in R$ for every $\mathcal{A}$-structure $a$. We want $Wt(a)=Wt(b)$ if $a$ is isomorphic to $b$. Thus we will write $|{\mathcal{A}}_n{|}_{Wt}:=|{\mathcal{A}}_X{|}_{Wt}$ for any set $X$ of size $n$.

Definition 4.2.6. Given species $\mathcal{A}$ and generalized weight function $Wt$. Then we can define the generalized EGF to be$$\sum _{n\ge 0}\frac{1}{n!}|{\mathcal{A}}_n{|}_{Wt}{x}^n$$or$$\sum _{n\ge 0}\frac{1}{n!}|{\mathcal{A}}_n{|}_{Wt}$$

Definition 4.2.7. We define multisort species, it is like species, but input is a tuple of finite sets. We will focus on $2$-sort species (or $2$-species).

A $2$-species $\mathcal{A}$ is a rule which assigns:

1.	To every ordered pair $(X_1,X_2)$ of finite sets, we get a finite set ${\mathcal{A}}_{X_1,X_2}$ the $\mathcal{A}$-structures on $(X_1,X_2)$.
2.	To every pair of bijections $f_1:X_1\to Y_1$, $f_2:X_2\to Y_2$ a bijection $(f_1,f_2{)}_{\ast }:{\mathcal{A}}_{X_1,X_2}\to {\mathcal{A}}_{Y_1,Y_2}$ called the transportation of structures such that.

Remark 4.2.8. We can also define isomorphisms, natural transformations and equivalence. The first big difference between $2$-species and species is when we look at EGF.

Like before, we will write $|{\mathcal{A}}_{n,m}|=|{\mathcal{A}}_{X_1,X_2}|$ where $|X_1|=n$ and $|X_2|=m$. Then the EGF for $2$-species is given by$$A(x_1,x_2)=\sum _{m,n\ge 0}|{\mathcal{A}}_{n,m}|\frac{x_1^n}{n!}\frac{x_2^m}{m!}$$

Example 4.2.9.

1.	Consider $\mathcal{F}$ as the $2$-species of functions, where ${\mathcal{F}}_{X,Y}$ is the set of all functions from $X$ to $Y$.
2.	The $2$-species of vertex and edges-labelled graphs. This assigns $(X,Y)$ the set of all $(\Gamma ,\gamma )$ where $\Gamma$ is a graph with vertex set $X$ and $\gamma$ is a bijection from the edges of the graph to $Y$.
3.	${\Pi }^{(2)}$, the $2$-species of $2$-set partitions. A $2$-set partition of $(X,Y)$ is a set of pairs $\{(S_1,T_1),...,(S_k,T_k)\}$ where $X=S_1\coprod ...\coprod S_k$ and $Y=T_1\coprod ...\coprod T_k$ and $S_i\cup T_i\ne \varnothing$.
4.	${\mathcal{X}}_1,{\mathcal{X}}_2$ is the $2$-species of singletons of $1$st and $2$nd sort. The definition is:$$({\mathcal{X}}_1{)}_{X_1,X_2}=\{\begin{array}{l}\{X_1\},\text{ if }|X_1|=1,|X_2|=\varnothing \\ \varnothing ,\text{ otherwise}\end{array}$$Similarly, we define$$({\mathcal{X}}_2{)}_{X_1,X_2}=\{\begin{array}{l}\{X_2\},\text{ if }|X_1|=0,|X_2|=1\\ \varnothing ,\text{ otherwise}\end{array}$$

Remark 4.2.10 (Diagrammatic perspective of $2$-sort species).

The unlabelled structures have “two sorts” of label receivers. The first sort receives labels from $X_1$ and the second receives labels from $X_2$.

For example, if we consider $\mathcal{F}$ as the $2$-species of functions, then the unlabelled structures are two line of dots with some arrow from the first line to second. Then the first line would receive labels from $X$ and second line receive labels from $Y$.

Remark 4.2.11. Now we talk about operations on $2$-species. Suppose $\mathcal{A},\mathcal{B}$ are two $2$-species.

Definition 4.2.12 (Sums/Differences). The sum and difference are more or less the same:$$(\mathcal{A}+\mathcal{B}{)}_{X,Y}={\mathcal{A}}_{X,Y}\coprod B_{X,Y}$$Similarly if $\mathcal{B}$ is a subspecies of $\mathcal{A}$ then $(\mathcal{A}-\mathcal{B}{)}_{X,Y}={\mathcal{A}}_{X,Y}\backslash {\mathcal{B}}_{X,Y}$.

Remark 4.2.13. The filter operation is more or less the same and hence ommited.

Definition 4.2.14 (Products).

1.	If $R$ is a set, then $(R\times \mathcal{A}{)}_{X,Y}=R\times {\mathcal{A}}_{X,Y}$.
2.	$$(\mathcal{A}⊠\mathcal{B}{)}_{X,Y}={\mathcal{A}}_{X,Y}\times {\mathcal{B}}_{X,Y}$$
3.	$$(\mathcal{A}\ast \mathcal{B}{)}_{X,Y}=\coprod _{S\subseteq X}\coprod _{T\subseteq Y}{\mathcal{A}}_{S,Y}\times {\mathcal{B}}_{X\backslash S,Y\backslash T}$$

We note that the unlabelled structure is just $\tilde{\mathcal{A}}\times \tilde{\mathcal{B}}$ for $\mathcal{A}\ast \mathcal{B}$. Also, we note the multi-EGF of $\mathcal{A}\ast \mathcal{B}$ is just $A(x_1,x_2)B(x_1,x_2)$.

Example 4.2.15. Consider $\mathcal{F}\ast \mathcal{F}$ as the product of functions. We can think of this as the following: where thre gree means the left $\mathcal{F}$ and the red means the right. For structures on $\mathcal{F}\ast \mathcal{F}$, we can view it as a single function $\varphi$ where each elements of the domain/codomain is coloured red/green and $\varphi (x)$ has the same colour as $x$.

Definition 4.2.16 (Sequences). We just define ${\mathcal{A}}^{\ast }={\sum }_{n\ge 0}{\mathcal{A}}^n$.

Definition 4.2.17 (Derivatives). We have two derivatives $({\partial }_1\mathcal{A},{\partial }_2\mathcal{A})$.

1.	$({\partial }_1\mathcal{A}{)}_{X,Y}={\mathcal{A}}_{X\coprod \{\ast \},Y}$ where $\ast \notin X$.
2.	$({\partial }_2\mathcal{A}{)}_{X,Y}={\mathcal{A}}_{X,Y\coprod \{\ast \}}$ where $\ast \notin Y$.

Some remarks:

1.	We note the rooting operations are ${\mathcal{X}}_1\ast {\partial }_1\mathcal{A}$ and ${\mathcal{X}}_2\ast {\partial }_2\mathcal{A}$ where in the first one we root at elements of the first sort and the second one we root at elements of second sort.
2.	We note we can also consider “mark and change sort” operation. This is just ${\mathcal{X}}_2\ast {\partial }_1\mathcal{A}$ and ${\mathcal{X}}_1\ast {\partial }_2\mathcal{A}$. The first one is mark and change from $1$st sort to $2$nd sort and the second is mark and change $2$nd to $1$st.
3.	The multi-EGF for ${\partial }_1\mathcal{A}$ is $\frac{\partial }{\partial x_1}A(x_1,x_2)$ and ${\partial }_2\mathcal{A}$ is $\frac{\partial }{\partial x_2}A(x_1,x_2)$.

Definition 4.2.18 (Diagonal). If $\mathcal{A}$ is $2$-species, then we define the diagonal $\nabla \mathcal{A}$, which is a $1$-species, as$$(\nabla \mathcal{A}{)}_X={\mathcal{A}}_{X,X}$$

Example 4.2.19. We have $\nabla \mathcal{F}=\mathcal{N}$. If $A(x_1,x_2)={\sum }_{m,n\ge 0}{a}_{m,n}\frac{x_1^m}{m!}\frac{x_2^n}{n!}$ then$$(\nabla A)(x)=\sum _{n\ge 0}{a}_{n,n}\frac{x^n}{n!}$$

Remark 4.2.20. We can decompose $k$-species with $k$-tuples of $l$-species to a $l$-species. We will discuss $(k,l)=(1,2)$, $(2,1)$ and $(2,2)$.

Definition 4.2.21 (Composition when $(k,l)=(1,2)$). Let $\mathcal{A}$ be $1$-species and $\mathcal{B}$ be connected $2$-species, i.e. $B_{\varnothing ,\varnothing }=\varnothing$. Then the unlabelled structures is defined by :

1.	Start with unlabelled $\mathcal{A}$-structure $\alpha$.
2.	Replace its label receivers by unlabelled $\mathcal{B}$-structures ${\beta }_1,{\beta }_2,...$
3.	The label receivers of composite object come from ${\beta }_i$’s only, which is a $2$-sort species.

The the $\mathcal{A}(\mathcal{B})$ labelled structure consists of:

1.	$P=\{(S_1,T_1),...,(S_k,T_k)\}\in {\Pi }_{X,Y}^{(2)}$
2.	$\alpha \in {\mathcal{A}}_P$.
3.	${\beta }_i\in B_{S_i,T_i}$ for $i=1,...,k$.

The multi-EGF of $\mathcal{A}[\mathcal{B}]$ is just $\mathcal{A}(B(x_1,x_2))$.

Example 4.2.22. Let $\mathcal{H}$ as the $2$-species of vertex and edge labelled graphs and ${\mathcal{H}}^c$ be 2-species of connected graphs with vertex and edge labelled. Then $\mathcal{H}\equiv \mathcal{E}[{\mathcal{H}}^c]$.

Example 4.2.23. We can converting $1$-species into $2$-species: $\mathcal{A}[{\mathcal{X}}_1],\mathcal{A}[{\mathcal{X}}_2],\mathcal{A}[{\mathcal{X}}_1+{\mathcal{X}}_2]$. The definition goes as:$$\mathcal{A}[\mathcal{X}{]}_{X_1,X_2}=\{\begin{array}{l}{\mathcal{A}}_{X_1},X_2=\varnothing \\ \varnothing ,X_2\ne \varnothing \end{array}$$$$\mathcal{A}[{\mathcal{X}}_2{]}_{X_1,X_2}=\{\begin{array}{l}{\mathcal{A}}_{X_2},X_1=\varnothing \\ \varnothing ,X_1\ne \varnothing \end{array}$$$$\mathcal{A}[{\mathcal{X}}_1+{\mathcal{X}}_2{]}_{X_1,X_2}={\mathcal{A}}_{X_1\coprod X_2}$$

Definition 4.2.24 (Composition when $(k,l)=(2,1)$). Let $\mathcal{A}$ be $2$-species, ${\mathcal{B}}_1,{\mathcal{B}}_2$ be connected $1$-species. Then we can define $\mathcal{A}[{\mathcal{B}}_1,{\mathcal{B}}_2]$ as a $1$-species.

The unlabelled structure is defined by:

1.	Start with unlabelled $\mathcal{A}$-structure $\alpha$.
2.	Replace all label receivers of $1$st sort in $\alpha$ by ${\mathcal{B}}_1$-structures ${\beta }_1,{\beta }_2,...$
3.	Replace all label receivers of $2$nd sort in $\alpha$ by ${\mathcal{B}}_2$-structures ${\gamma }_1,{\gamma }_2,...$
4.	The label receivers of composite objects come from ${\beta }_i$’s and ${\gamma }_j$’s

The $\mathcal{A}[{\mathcal{B}}_1,{\mathcal{B}}_2]$-structure on $X$ consists of:

1.	$(P_1,P_2)\in (\Pi \ast \Pi {)}_X$, i.e. $P_1=\{S_{11},...,S_{1k}\}$ and $P_2=\{S_{21},...,S_{2l}\}$.
2.	Then we have $\alpha \in {\mathcal{A}}_{P_1,P_2}$.
3.	We have ${\beta }_i\in ({\mathcal{B}}_1{)}_{S_{1i}}$.
4.	And ${\gamma }_j\in ({\mathcal{B}}_2{)}_{S_{2j}}$.

The multi-EGF of $\mathcal{A}[{\mathcal{B}}_1,{\mathcal{B}}_2]$ will be $A(B_1(x),B_2(x))$.

Example 4.2.25. We can convert $2$-species into $1$-species, i.e. we have $\mathcal{A}[\mathcal{X},\mathcal{X}]$, this forgets that there are two sorts of label receivers and treat all the same.

Formally, we have$$\mathcal{A}[\mathcal{X},\mathcal{X}{]}_X=\coprod _{S\subseteq X}{\mathcal{A}}_{S,X\backslash S}$$In this case the EGF is just $A(x,x)$.

Definition 4.2.26 (Composition when $(k,l)=(2,2)$). Let $\mathcal{A},{\mathcal{B}}_1,{\mathcal{B}}_2$ be $2$-species, then we define $\mathcal{A}[{\mathcal{B}}_1,{\mathcal{B}}_2]$ as a $2$-species as follows.

The unlabelled structures is the same as the $(k,l)=(2,1)$ case.

The labelled structures is the same as the $(k,l)=(2,1)$ case but replace $\Pi \ast \Pi$ by ${\Pi }^{(2)}\ast {\Pi }^{(2)}$. The multi-EGF in this case is just $A(B_1(x_1,x_2),B_2(x_1,x_2))$.

Example 4.2.27. We consider the $2$-species of functions. We have natural equivalence$$\mathcal{F}\equiv \mathcal{E}[{\mathcal{X}}_2\ast \mathcal{E}[{\mathcal{X}}_1]]$$Indeed, to form a function, for each elements in the codomain, which is ${\mathcal{X}}_2$, and we need to pair that with a set of elements of the first sort, i.e. ${\mathcal{X}}_2\ast \mathcal{E}[{\mathcal{X}}_1]$. We need to do this to every elements in the codomain, hence we need to put a $\mathcal{E}$ in front. The EGF of $\mathcal{F}$ is then$$F(x_1,x_2)=\exp (x_2{e}^{x_1})$$

For surjective functions, we see this is just $\mathcal{E}({\mathcal{X}}_2\ast {\mathcal{E}}_{+}({\mathcal{X}}_1))$ with similar reasoning. On the other hand, the injective functions is $\mathcal{E}[{\mathcal{X}}_2\ast (1+{\mathcal{X}}_1)]$.

Example 4.2.28. Let $X,Y$ be disjoint finite sets. We want to count the permutations of $X\coprod Y$ with the property that every cycle has at least $1$ element of $X$ and $1$ element of $Y$.

Form the $2$-species of ${\mathcal{C}}^{mix}$ of cycles, with at least one label receiver of each sort. We get$${\mathcal{C}}^{mix}\equiv \mathcal{C}[{\mathcal{X}}_1+{\mathcal{X}}_2]-\mathcal{C}[{\mathcal{X}}_1]-\mathcal{C}[{\mathcal{X}}_2]$$where $\mathcal{C}[{\mathcal{X}}_1+{\mathcal{X}}_2]$ is cycles with labels of either sort, and $\mathcal{C}[{\mathcal{X}}_1]+\mathcal{C}[{\mathcal{X}}_2]$ are cycles without at least one label of each sort.

Thus we get $$\begin{array}{rl}{\mathcal{C}}^{mix}(x_1,x_2)& =C(x_1+x_2)-C(x_1)-C(x_2)\\ & =\log (\frac{1}{1-x_1-x_2})-\log (\frac{1}{1-x_1})-\log (\frac{1}{1-x_2})\end{array}$$What we want is $|\mathcal{E}({\mathcal{C}}^{mix}){|}_{x,y}$, which is$$[\frac{x_1^m}{m!}\frac{x_2^n}{n!}]\exp (C(x_1,x_2))$$

Example 4.2.29. Determine the number of bipartite graphs such that:

1.	$m$ vertices in the first part.
2.	$n$ vertices in the second part.
3.	no vertices of degree $0$.

We let $\mathcal{B}$ be the $2$-species of bipartite graphs, where ${\mathcal{B}}_{X,Y}$ is the set of all bipartite graphs with bipartition $(X,Y)$. Let $\mathcal{H}$ be the subspecies of $\mathcal{B}$ with no vertices of degree $0$.

Note we have $\mathcal{B}\equiv \mathcal{H}\ast \mathcal{E}[{\mathcal{X}}_1+{\mathcal{X}}_2]$. From here, we see$$B(x_1,x_2)=\sum _{m,n\ge 0}{2}^{mn}\frac{x_1^m}{m!}\frac{x_2^n}{n!}$$and hence$$H(x_1,x_2)=e^{-x_1-x_2}\sum _{m,n\ge 0}{2}^{mn}\frac{x_1^m}{m!}\frac{x_2^n}{n!}$$Thus the answer to the question is just $[\frac{x_1^m}{m!}\frac{x_2^n}{n!}]H(x_1,x_2)$.