Understaing Concept of Generating function.

Question

I can easily understand the generating function of sequence such as $a_n = n+1$ or something, but cannot understand generating function for some object.

There are 2 examples (with photos):

1. What does "egf for counting set" mean? For example, $\{a_n\}=1,1,1,1,1…$ means numbers of set with $n$ elements or something? I can never understand.

2. What is gf for prime path (in Schroder number) The number of prime paths? According to which one? I am so confused.

I think they are very basic questions. I'm sorry for that

Answer 1

$1-)$ When a sequence is given like $1,1,1,1..$ , it means the coefficients of variables of generating function ,respectively.For example ,

• $1,1,1,1,1= 1+x+x^2 +x^3 +x^4 +x^5$

• $1,3,2,2,4,7 = 1+3x+2x^2 +2x^3 +4x^4 +7x^5$

• $0,0,0,0,0,1,1,1=x^5 +x^6+x^7$

• $0,1,0,0,0,4,4,9 =x+4x^5 +4x^6 +9x^7$

• $\binom{5}{0},\binom{5}{1},\binom{5}{2},\binom{5}{3},\binom{5}{4},\binom{5}{5}=1+5x+10x^2+10x^3+5x^4 +x^5 =(1+x)^5$

$1.b-)$ When we comes to "$e^x$ is the egf for counting set" , you must know that when we distribute distinguishable objects into distinguishable boxes , we makes use of exponential generating functions , you can find many example about it in my answers.I am putting here one of them.However ,this is a little long to teach here.I recommend you read this book to begin.

$2-)$ It is given that Schöder path is $\sum_0^\infty( x+xR(x))^k$ , it means that $$( x+xR(x))^0 +( x+xR(x))^1+( x+xR(x))^2+( x+xR(x))^3+( x+xR(x))^4+...$$

Then ,we know that $$\frac{1}{1-x}=x^0 +x^1 +x^2 +x^3 +....$$

So , if we switch $x$ with $x+xR(x)$ , we can reach our aim such that $$\frac{1}{1-(x+xR(x))} =(x+xR(x))^0 +(x+xR(x))^1 +(x+xR(x))^2 +...$$

Answer 2

The question about

$e^x$ is the egf for counting "set".

does not have enough context, but I can guess what it is supposed to be. Given any sequence $\,a_0,a_1,\dots,\,$ its egf is the formal power series

$$ A(x) = \text{egf}\,[a_n] := \sum_{n=0}^\infty a_n\frac{x^n}{n!}. $$

Its gf is the same without $\,n!\,$ in the denominator. Thus, as the first example, $\,\frac1{1-x}\,$ is the gf for the sequence $\,1,1,1,\dots\,$ and $\,e^x\,$ is the egf for the same sequence.

Now suppose we are counting the number of sets which are the "same up to isomorphism". That is, there is a bijection between them. Then, they have the same number of elements. Therefore, there is only a single set "up to isomorphism" for each number of elements. This is the same sequence $\,1,1,1,\dots.$