basic questions about combinatorial class

96 Views Asked by At

I have two questions:

1) How the concept of "exponential map " is related to "combinatorial classes"? consider the following question: let $\mathcal{A}$ be a combinatorial class, for each non-negative integer $n$ we let $a_n$ be the number of elements of size $n$, i.e., the number of elements of the set $\mathcal{A}_n=\{a\in\mathcal{A}:|a|=n\}$,

2) how these $a_n$s are used in a generating function? can someone explain what is the application of generating function in combinatorial class?

Wikipedia says :"Generating functions are used to describe families of combinatorial objects". but I think it's not a deep explanation, so any help is appreciated.

1

There are 1 best solutions below

0
On

This is too long of a comment. This is called Combinatorial species. There is a great book by Bergeron. To answer your question, consider that you have your family enumerated by $a_n.$ then by doing $A=\sum _{k=0}^{\infty}a_kx^k$ formally we have control of every level of the class. We can do usual thinks in calculus like adding, multiplying, differentiation and integrating formally in this function. The remarkable punch line is that this operations correspond to also usual operations in combinatorial settings, namely, disjoint union, convolution (ripping in parts objects), pointing(choosing a mark element of the object), dropping a pointed element in the object. So by doing calculus stuff we can understand a lot of our sequences.

In the specific question of the exponential map. Notice that doing $$\frac{x^k}{k!}$$ is like creating a sequence of $k$ elements of object $x$ and taking out the order in this sequence. So, when you add over all number of parts of your sequence (i.e., $\sum _{k\geq 0} \frac{x^k}{k!}$) you are getting all possible sequences of objects without an order. As an example, think about $$e^{e^x-1},$$ is taking sequence of elements where we do not care about ordering but we also do not take sequences of $0$ elements. This correspond to partitions! Notice that first you take sequences of numbers(You call them blocks) in which order is not important and then you take sequences of this numbers of non empty blocks, so what you get is partitions!