[combinatorics] exponential generating function (properties of exponential generating function | exponential generating function solving multiple set arrangement)

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 )
• 【 Combinatorial mathematics 】 Exponential generating function ( The concept of exponential generating function | Permutation number exponential generating function = General generating function of combinatorial number | Example of exponential generating function )

One 、 Properties of exponential generating function

---

Two sequences

{

a

n

}

,

{

b

n

}

\{a_n\} , \{b_n\}

{ an​},{ bn​} The corresponding exponential generating functions are

A

e

(

x

)

,

B

e

(

x

)

A_e(x) , B_e(x)

Ae​(x),Be​(x) ,

Put the above two Exponential generating function Multiply , As a function , It can be expanded into another series ,

A

e

(

x

)

⋅

B

e

(

x

)

=

∑

n

=

0

∞

c

n

x

n

n

!

A_e(x) \cdot B_e(x) = \sum\limits_{n=0}^{\infty} c_n \cfrac{x^n}{n!}

Ae​(x)⋅Be​(x)=n=0∑∞​cn​n!xn​

among ,

c

n

=

∑

k

=

0

∞

(

n

k

)

a

k

b

n

−

k

c_n =\sum\limits_{k=0}^{\infty}\dbinom{n}{k}a_kb_{n-k}

cn​=k=0∑∞​(kn​)ak​bn−k​

( The result can be obtained by substituting )

Two 、 The exponential generating function solves the arrangement of multiple sets

---

Multiple sets

S

=

{

n

1

⋅

a

1

,

n

2

⋅

a

2

,

⋯
 

,

n

k

⋅

a

k

}

S=\{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \}

S={ n1​⋅a1​,n2​⋅a2​,⋯,nk​⋅ak​}

Multiple sets

S

S

S Of

r

r

r Number of permutations Composition sequence

{

a

r

}

\{ a_r \}

{ ar​} , The corresponding exponential generating function is :

G

e

(

x

)

=

f

n

1

(

x

)

f

n

2

(

x

)

⋯

f

n

k

(

x

)

G_e(x) = f_{n_1}(x) f_{n_2}(x) \cdots f_{n_k}(x)

Ge​(x)=fn1​​(x)fn2​​(x)⋯fnk​​(x) *

Each generated function item

f

n

i

(

x

)

f_{n_i}(x)

fni​​(x) yes

f

n

i

(

x

)

=

1

+

x

+

x

2

2

!

+

⋯

+

x

n

i

n

i

!

f_{n_i}(x) = 1 + x + \cfrac{x^2}{2!} + \cdots + \cfrac{x^{n_i}}{n_i!}

fni​​(x)=1+x+2!x2​+⋯+ni​!xni​​ *

take

G

e

(

x

)

G_e(x)

Ge​(x) an , Among them

x

r

r

!

\cfrac{x^r}{r!}

r!xr​ The coefficient of is the permutation number of multiple sets , Pay special attention if not

x

r

r

!

\cfrac{x^r}{r!}

r!xr​ form , It needs to be forcibly transformed into the above properties , Be sure to divide by

r

!

r!

r! ; *****

Select the problem reference :

n

n

n Meta set

S

S

S , from

S

S

S Select... From the set

r

r

r Elements ;

according to Whether the element can be repeated , Whether the selection process is orderly , The selection question is divided into four sub types :

	Elements do not repeat	Elements can be repeated
Orderly selection	Set arrangement P ( n , r ) P(n,r) P(n,r)	Multiset arrangement
Unordered selection	Set combination C ( n , r ) C(n,r) C(n,r)	Combination of multiple sets

Select the question :

• Non repeatable elements , Orderly selection , Corresponding Arrangement of sets ; $P(n,r)=\frac{n!}{(n-r)!}$
• Non repeatable elements , Unordered selection , Corresponding A combination of sets ; $C(n,r)=\frac{P(n,r)}{r!}=\frac{n!}{r!(n-r)!}$
• Repeatable elements , Orderly selection , Corresponding Arrangement of multiple sets ; $wholerowColumn=\frac{n!}{n_1!n_2!\cdots n_k!}$
• Repeatable elements , Unordered selection , Corresponding Combination of multiple sets ; $N=C(k+r-1,r)$