[combinatorics] exponential generating function (example of 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 )
• 【 Combinatorial mathematics 】 Exponential generating function ( Properties of exponential generating function | The exponential generating function solves the arrangement of multiple sets )

One 、 Example of solving multiple set permutation with exponential generating function

---

Use

1

,

2

,

3

,

4

1,2,3,4

1,2,3,4 Four numbers make up five digits , requirement

1

1

1 The number of occurrences cannot exceed

2

2

2 Time , But there has to be ,

2

2

2 Not more than

1

1

1 Time ,

3

3

3 The most frequent occurrence

3

3

3 Time ,

4

4

4 Even number of times ,
Find the number of the above five digits ;

This is a solution Multiset arrangement The subject of , Use Exponential generating function ;

Altogether

5

5

5 A place , Use

1

,

2

,

3

,

4

1,2,3,4

1,2,3,4 To this

5

5

5 Fill in positions ,

Select a number to analyze :

1

1

1 No more than

2

2

2 Time , There must be , That is, it must be greater than

0

0

0 , Then the number that can be selected is

1

,

2

1,2

1,2 ,

2

2

2 No more than

1

1

1 Time , Optional number

0

,

1

0,1

0,1 ,

3

3

3 Emergence can achieve

3

3

3 Time , Number of selectable

0

,

1

,

2

,

3

0,1,2,3

0,1,2,3 ,

4

4

4 Even number of times , The optional number is

0

,

2

,

4

,

6

,

8

,

⋯

0, 2, 4, 6, 8, \cdots

0,2,4,6,8,⋯ , Pay attention to the total choice here

5

5

5 individual , When finally solving multiple sets , Mainly to see

x

5

x^5

x5 The former idempotent , So here's The optional number is... In a single factor

x

x

x Subidempotent , There is no need to exceed

5

5

5 , choice

0

,

2

,

4

0,2,4

0,2,4 that will do ;

According to the following model , Write the exponential generating function ;

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

r

r

r The coefficient is the permutation number of multiple sets ; *

Writing of exponential generating function :

① Determine the number of generated function items : Number of element types in multiple sets

② Determine the number of items in the generated function item : Pick value Number ;

③ Itemized format :

x

n

n

!

\cfrac{x^n}{n!}

n!xn​

④ Partial power : Pick value ;

All in all

4

4

4 Elements

1

,

2

,

3

,

4

1,2,3,4

1,2,3,4 , So the generating function is

4

4

4 Multiply the generated function items ;

1

1

1 The generating function item corresponding to the element :

• Pick value : $1,2$
• final result :

  x

  1

  1

  !

  +

  x

  2

  2

  !

  =

  x

  +

  x

  2

  2

  !

  \cfrac{x^1}{1!} + \cfrac{x^2}{2!} = x + \cfrac{x^2}{2!}

  1!x1​+2!x2​=x+2!x2​

2

2

2 The generating function item corresponding to the element :

• Pick value : $0,1$
• final result :

  x

  0

  0

  !

  +

  x

  1

  1

  !

  =

  1

  +

  x

  \cfrac{x^0}{0!} + \cfrac{x^1}{1!} = 1 + x

  0!x0​+1!x1​=1+x

3

3

3 The generating function item corresponding to the element :

• Pick value : $0,1,2,3$
• final result :

  x

  0

  0

  !

  +

  x

  1

  1

  !

  +

  x

  2

  2

  !

  +

  x

  3

  3

  !

  =

  1

  +

  x

  +

  x

  2

  2

  !

  +

  x

  3

  3

  !

  \cfrac{x^0}{0!} + \cfrac{x^1}{1!} + \cfrac{x^2}{2!} + \cfrac{x^3}{3!} = 1 + x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!}

  0!x0​+1!x1​+2!x2​+3!x3​=1+x+2!x2​+3!x3​

4

4

4 The generating function item corresponding to the element :

• Pick value : $0,2,4,6,\cdots$
• final result :

  x

  0

  0

  !

  +

  x

  2

  2

  !

  +

  x

  4

  4

  !

  =

  1

  +

  x

  2

  2

  !

  +

  x

  4

  4

  !

  \cfrac{x^0}{0!} + \cfrac{x^2}{2!} + \cfrac{x^4}{4!} = 1+ \cfrac{x^2}{2!} + \cfrac{x^4}{4!}

  0!x0​+2!x2​+4!x4​=1+2!x2​+4!x4​

Generate four of the above exponents Multiply the exponential generating function terms , To calculate the

x

5

x^5

x5 The coefficient before , Is the permutation number of multiple sets ;

G

e

(

x

)

=

(

x

+

x

2

2

!

)

(

1

+

x

)

(

1

+

x

+

x

2

2

!

+

x

3

3

!

)

(

1

+

x

2

2

!

+

x

4

4

!

)

G_e(x) = (x + \cfrac{x^2}{2!}) (1 + x) (1 + x + \cfrac{x^2}{2!} + \cfrac{x^3}{3!}) (1+ \cfrac{x^2}{2!} + \cfrac{x^4}{4!})

Ge​(x)=(x+2!x2​)(1+x)(1+x+2!x2​+3!x3​)(1+2!x2​+4!x4​)

           
 

=

x

+

5

x

2

2

!

+

18

x

3

3

!

+

64

x

4

4

!

+

215

x

5

5

!

⋯

\ \ \ \ \ \ \ \ \ \ \ \,= x + 5\cfrac{x^2}{2!} + 18\cfrac{x^3}{3!} + 64\cfrac{x^4}{4!} + 215\cfrac{x^5}{5!} \cdots

           =x+52!x2​+183!x3​+644!x4​+2155!x5​⋯

Don't forget the back , among

x

5

x^5

x5 The item is

215

x

5

5

!

215\cfrac{x^5}{5!}

2155!x5​ , Therefore, what is required in the title

5

5

5 The number of digits is

215

215

215 individual ;