2
$\begingroup$

I am working through the these notes (pdf) for my enumeration class, and I am having some trouble understanding some of the definitions and theorems.

Could someone try and provide me with an intuitive sense as well as the difference between what is explained in EX11.14, Definition 11.15, Theorem 11.16 and then finally Definition 11.20?

The problem is that all these are all built on-top of one another (are nested within one another, if you will) and I find it difficult and confusing to keep track of what is going on and being said.

I am able to understand the product and power of classes, but then looking at the composition and the k-sets of structures seems really confusing to me.

Clarification would greatly be appreciated :)

URL: (http://www.math.uwaterloo.ca/~dgwagner/co430II.pdf)

1 Answers 1

1

Here is an example which may help. Let $\mathcal{T}$ be the class of trees. Consider the class $\mathcal{F}$ of forests: finite graphs whose connected components are trees. Define a $k$-forest to be a forest that has exactly $k$ components, and denote by $\mathcal{F}_k$ the class of $k$-forests. Each forest is a $k$-forest for exactly one $k$, and so we have $\mathcal{F} = \bigoplus_{k\geq 0}\mathcal{F}_k$.

Given a finite set $X$, defining a $k$-forest on $X$ is the same as choosing a partition $\alpha_1,\ldots,\alpha_k$ of $X$ into $k$ parts, and defining a tree on each of these parts. The components of a forest aren't ordered in any particular way, and so this partition is unordered. An element of $\mathcal{T}^k_X$ is an ordered partition of $X$ each of whose parts is equipped with a tree structure, and so we obtain a $k$-forest -- an element of $(\mathcal{F}_k)_X$ -- by taking an element of $\mathcal{T}^k_X$ and forgetting the order. Comparing with Definition 11.15, we have $\mathcal{F}_k \equiv \mathcal{E}_k[\mathcal{T}]$, i.e. a $k$-forest is a $k$-set of trees. Then $\mathcal{F} \equiv \bigoplus_{k\geq 0}\mathcal{E}_k[\mathcal T] =: \mathcal{E}[\mathcal T],$ i.e. a forest is a set of trees.

Another example: any permutation on a set $X$ can be uniquely factored into a product of disjoint cyclic permutations, which are the same thing as directed cycles; if $\mathcal{S}$ is the class of permutations and $\mathcal{C}$ is the class of directed cycles, we have $\mathcal{S}\equiv \mathcal{E}[\mathcal{C}]$.

  • 0
    Thanks! I think I've got it for this particular example at least.2012-11-25