Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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}]$.

share|improve this answer
    
Thanks! I think I've got it for this particular example at least. –  Nizbel99 Nov 25 '12 at 15:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.