[combinatorics] exponential generating function (concept of exponential generating function | permutation number exponential generating function = combinatorial number ordinary generating function | e

Reference blog : Look in order

• 【 Combinatorial mathematics 】 Generating function Brief introduction ( Generating function definition | Newton's binomial coefficient | Common generating functions | Related to constants | Related to binomial coefficient | Related to polynomial coefficients )
• 【 Combinatorial mathematics 】 Generating function ( Linear properties | Product properties )
• 【 Combinatorial mathematics 】 Generating function ( Shift property )
• 【 Combinatorial mathematics 】 Generating function ( The nature of summation )
• 【 Combinatorial mathematics 】 Generating function ( Commutative properties | Derivative property | Integral properties )
• 【 Combinatorial mathematics 】 Generating function ( Summary of nature | Important generating functions ) *
• 【 Combinatorial mathematics 】 Generating function ( Generate function examples | Given the general term formula, find the generating function | Given the generating function, find the general term formula )
• 【 Combinatorial mathematics 】 Generating function ( Generate function application scenarios | Solving recursive equations using generating functions )
• 【 Combinatorial mathematics 】 Generating function ( Use the generating function to solve multiple sets r Combinatorial number )
• 【 Combinatorial mathematics 】 Generating function ( Use generating function to solve the number of solutions of indefinite equation )
• 【 Combinatorial mathematics 】 Generating function ( Examples of using generating functions to solve the number of solutions of indefinite equations )
• 【 Combinatorial mathematics 】 Generating function ( Examples of using generating functions to solve the number of solutions of indefinite equations 2 | Extended to integer solutions )
• 【 Combinatorial mathematics 】 Generating function ( Positive integer split | disorder | Orderly | Allow repetition | No repetition | Unordered and unrepeated splitting | Unordered repeated split )
• 【 Combinatorial mathematics 】 Generating function ( Positive integer split | Unordered non repeated split example )
• 【 Combinatorial mathematics 】 Generating function ( Positive integer split | Basic model of positive integer splitting | Disorderly splitting with restrictions )
• 【 Combinatorial mathematics 】 Generating function ( Positive integer split | Repeated ordered splitting | Do not repeat orderly splitting | Proof of the number of repeated ordered splitting schemes )

One 、 Exponential generating function

---

Of multiple sets Combinatorial number , Use Generating function Calculate ;

Of multiple sets Number of permutations , Use Exponential generating function Calculate ;

Sequence

{

a

n

}

\{ a_n \}

{ an​} , The general formula is

a

n

a_n

an​ ,

{

a

n

}

\{ a_n \}

{ an​} Of The general generating function is

G

(

x

)

=

∑

n

=

0

∞

a

n

x

n

G(x) = \sum\limits_{n=0}^{\infty}a_n x^n

G(x)=n=0∑∞​an​xn ,

{

a

n

}

\{ a_n \}

{ an​} Of The exponential generating function is

G

e

(

x

)

=

∑

n

=

0

∞

a

n

x

n

n

!

G_e(x) = \sum\limits_{n=0}^{\infty}a_n \cfrac{x^n}{n!}

Ge​(x)=n=0∑∞​an​n!xn​

   
 

\ \ \ \,

   * ( Key formula )

{

a

n

}

\{ a_n \}

{ an​} Of Exponential generating function It is based on the general generating function Divided by

n

!

n!

n! ;

Two 、 Permutation number exponential generating function = General generating function of combinatorial number

---

Number of permutations :

P

(

n

,

r

)

=

n

!

(

n

−

r

)

!

P(n,r) = \cfrac{n!}{(n-r)!}

P(n,r)=(n−r)!n!​ ,

n

n

n Of the elements

r

r

r Elements , Duplicate permutations are not allowed ;

Combinatorial number :

C

(

n

,

r

)

=

n

!

r

!

(

n

−

r

)

!

C(n,r) = \cfrac{n!}{r!(n-r)!}

C(n,r)=r!(n−r)!n!​ ,

n

n

n Of the elements

r

r

r Elements , Duplicate combinations are not allowed ;

The generating function corresponding to the combination number yes

G

(

x

)

=

∑

n

=

0

∞

(

m

n

)

x

n

G(x) = \sum\limits_{n=0}^{\infty}\dbinom{m}{n} x^n

G(x)=n=0∑∞​(nm​)xn , After convergence

(

1

+

x

)

n

(1+x)^n

(1+x)n

The generating function corresponding to the permutation number yes

G

(

x

)

=

∑

n

=

0

∞

P

(

m

,

n

)

x

n

G(x) = \sum\limits_{n=0}^{\infty}P(m, n) x^n

G(x)=n=0∑∞​P(m,n)xn , according to

n

!

C

(

m

,

n

)

=

P

(

m

,

n

)

n! C(m,n) = P(m, n)

n!C(m,n)=P(m,n) , The generating function of the permutation , Each term is divided by

n

!

n!

n! , You can get the generating function of the corresponding combination number ;

The exponential generating function corresponding to the permutation count yes

G

e

(

x

)

=

∑

n

=

0

∞

P

(

m

,

n

)

x

n

n

!

G_e(x) = \sum\limits_{n=0}^{\infty}P(m, n) \cfrac{x^n}{n!}

Ge​(x)=n=0∑∞​P(m,n)n!xn​ , according to according to

C

(

m

,

n

)

=

P

(

m

,

n

)

n

!

C(m,n) =\cfrac{ P(m, n)}{n!}

C(m,n)=n!P(m,n)​ , It can be concluded as follows :

Exponential generating function of permutation count

=

=

= General generating function of combinatorial counting

3、 ... and 、 Example of exponential generating function

---

The sequence

b

n

=

1

b_n=1

bn​=1 , seek

{

b

n

}

\{ b_n \}

{ bn​} The exponential generating function of ;

The sequence is

{

1

,

1

,

1

,

⋯
 

}

\{1, 1 ,1 , \cdots\}

{ 1,1,1,⋯}

Ordinary generating functions

G

(

x

)

=

1

+

x

+

x

2

+

⋯

=

∑

n

=

0

∞

x

n

G(x) = 1 + x + x^2 + \cdots = \sum\limits_{n=0}^{\infty}x^n

G(x)=1+x+x2+⋯=n=0∑∞​xn

Exponential generating function

G

e

(

x

)

=

∑

n

=

0

∞

x

n

n

!

=

e

x

G_e(x) = \sum\limits_{n=0}^{\infty}\cfrac{x^n}{n!}=e^x

Ge​(x)=n=0∑∞​n!xn​=ex