[combinatorics] generating function (positive integer splitting | unordered | ordered | allowed repetition | not allowed repetition | unordered not repeated splitting | unordered repeated splitting)

Reference blog :

• 【 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 )

One 、 Positive integer split

---

Positive integer split Contents involved :

• Split definition and classification
• Unordered split
• Orderly splitting

A positive integer can Split into several positive integers And , Each different split method , Can As a plan ;

Sort according to the splitting order :

4

4

4 Split into

1

1

1 and

3

3

3 ,

4

4

4 Split into

3

3

3 and

1

1

1 ;

• Orderly splitting : Above $2$
• Unordered split : Above $2$

Classify according to whether it is repeated :

• Allow repetition : When splitting , It is allowed to split into several repeated positive integers , Such as $3$
• No repetition : When splitting , Split positive integer No repetition , Such as $3$

Positive integer splitting can be done by nature , It is divided into

4

4

4 class ;

• Orderly repetition
• Order does not repeat
• Disorderly repetition
• Disorder does not repeat

Two 、 Unordered split

---

Unordered split basic model :

take Positive integer

N

N

N Unordered split into positive integers ,

a

1

,

a

2

,

⋯
 

,

a

n

a_1, a_2, \cdots , a_n

a1​,a2​,⋯,an​ It is a split

n

n

n Number ,

The split is unordered , Split above

n

n

n The number of numbers may be different ,

hypothesis

a

1

a_1

a1​ Yes

x

1

x_1

x1​ individual ,

a

2

a_2

a2​ Yes

x

2

x_2

x2​ individual ,

⋯

\cdots

⋯ ,

a

n

a_n

an​ Yes

x

n

x_n

xn​ individual , Then there is the following equation :

a

1

x

1

+

a

2

x

2

+

⋯

+

a

n

x

n

=

N

a_1x_1 + a_2x_2 + \cdots + a_nx_n = N

a1​x1​+a2​x2​+⋯+an​xn​=N

This form can be used Number of nonnegative integer solutions of indefinite equation Generation function calculation of , yes With coefficients , With restrictions , Reference resources : Combinatorial mathematics 】 Generating function ( Use generating function to solve the number of solutions of indefinite equation )

In the case of unordered splitting , A positive integer after splitting , Allow repetition and No repetition , It is two kinds of combinatorial problems ;

If No repetition , So these

x

i

x_i

xi​ The value of , Can only Value

0

,

1

0, 1

0,1 ; amount to With restrictions , With coefficients Of Nonnegative integer solutions of indefinite equations The situation of ;

If Allow repetition , So these

x

i

x_i

xi​ The value of , Namely Natural number ; amount to With coefficients Of Nonnegative integer solutions of indefinite equations The situation of ;

1、 Unordered split No repetition

Discuss Unordered split , Repetition is not allowed , This way Equivalent to With restrictions , With coefficients Of Nonnegative integer solutions of indefinite equations The situation of ;

a

1

a_1

a1​ Item corresponds to the generating function item ,

x

1

x_1

x1​ Value

0

,

1

0,1

0,1 , Then the corresponding generating function item is

(

y

a

1

)

0

+

(

y

a

1

)

1

=

1

+

y

a

1

(y^{a_1})^{0} + (y^{a_1})^{1}= 1+ y^{a_1}

(ya1​)0+(ya1​)1=1+ya1​

a

2

a_2

a2​ Item corresponds to the generating function item ,

x

2

x_2

x2​ Value

0

,

1

0,1

0,1 , Then the corresponding generating function item is

(

y

a

2

)

0

+

(

y

a

2

)

1

=

1

+

y

a

2

(y^{a_2})^{0} + (y^{a_2})^{1}= 1+ y^{a_2}

(ya2​)0+(ya2​)1=1+ya2​

⋮

\vdots

⋮

a

n

a_n

an​ Item corresponds to the generating function item ,

x

n

x_n

xn​ Value

0

,

1

0,1

0,1 , Then the corresponding generating function item is

(

y

a

n

)

0

+

(

y

a

n

)

1

=

1

+

y

a

n

(y^{a_n})^{0} + (y^{a_n})^{1}= 1+ y^{a_n}

(yan​)0+(yan​)1=1+yan​

Multiply the above generated function items , Then the complete generating function can be obtained :

G

(

x

)

=

(

1

+

y

a

1

)

(

1

+

y

a

2

)

⋯

(

1

+

y

a

n

)

G(x) = (1+ y^{a_1}) (1+ y^{a_2}) \cdots (1+ y^{a_n})

G(x)=(1+ya1​)(1+ya2​)⋯(1+yan​)

After the above generation function is written , Calculation an ,

y

y

y Of

N

N

N Coefficient of power , Namely Positive integer

N

N

N The number of splitting schemes ;

2、 Unordered split Allow repetition

Discuss Unordered split , Repetition is allowed , This way Equivalent to Without restrictions , With coefficients Of Nonnegative integer solutions of indefinite equations The situation of ;

a

1

a_1

a1​ Item corresponds to the generating function item ,

x

1

x_1

x1​ Value

0

,

1

,

⋯

0,1, \cdots

0,1,⋯ , Then the corresponding generating function item is

(

y

a

1

)

0

+

(

y

a

1

)

1

+

(

y

a

1

)

2

=

1

+

y

a

1

+

y

2

a

1

⋯

(y^{a_1})^{0} + (y^{a_1})^{1} + (y^{a_1})^{2}= 1+ y^{a_1} + y^{2a_1}\cdots

(ya1​)0+(ya1​)1+(ya1​)2=1+ya1​+y2a1​⋯

a

2

a_2

a2​ Item corresponds to the generating function item ,

x

2

x_2

x2​ Value

0

,

1

,

⋯

0,1, \cdots

0,1,⋯ , Then the corresponding generating function item is

(

y

a

2

)

0

+

(

y

a

2

)

1

+

(

y

a

2

)

2

=

1

+

y

a

2

+

y

2

a

2

⋯

(y^{a_2})^{0} + (y^{a_2})^{1} + (y^{a_2})^{2}= 1+ y^{a_2} + y^{2a_2}\cdots

(ya2​)0+(ya2​)1+(ya2​)2=1+ya2​+y2a2​⋯

⋮

\vdots

⋮

a

n

a_n

an​ Item corresponds to the generating function item ,

x

n

x_n

xn​ Value

0

,

1

,

⋯

0,1, \cdots

0,1,⋯ , Then the corresponding generating function item is

(

y

a

n

)

0

+

(

y

a

n

)

1

+

(

y

a

n

)

2

=

1

+

y

a

n

+

y

2

a

n

⋯

(y^{a_n})^{0} + (y^{a_n})^{1} + (y^{a_n})^{2}= 1+ y^{a_n} + y^{2a_n}\cdots

(yan​)0+(yan​)1+(yan​)2=1+yan​+y2an​⋯

Multiply the above generated function items , Then the complete generating function can be obtained :

G

(

x

)

=

(

1

+

y

a

1

+

y

2

a

1

⋯
 

)

(

1

+

y

a

2

+

y

2

a

2

⋯
 

)

⋯

(

1

+

y

a

n

+

y

2

a

n

⋯
 

)

G(x) = (1+ y^{a_1}+ y^{2a_1}\cdots) (1+ y^{a_2} + y^{2a_2}\cdots) \cdots (1+ y^{a_n}+ y^{2a_n}\cdots )

G(x)=(1+ya1​+y2a1​⋯)(1+ya2​+y2a2​⋯)⋯(1+yan​+y2an​⋯)

The above generating function can be generated according to Common values of the following generation functions :

{

a

n

}

\{a_n\}

{ an​} ,

a

n

=

1

n

a_n = 1^n

an​=1n ;

A

(

x

)

=

∑

n

=

0

∞

x

n

=

1

1

−

x

\begin{aligned} A(x) & = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x} \end{aligned}

A(x)​=n=0∑∞​xn=1−x1​​

take

1

+

y

a

1

+

y

2

a

1

⋯

1+ y^{a_1}+ y^{2a_1}\cdots

1+ya1​+y2a1​⋯ Medium

y

a

1

y^{a_1}

ya1​ Yuan Cheng

x

x

x , Then you can get

1

+

x

+

x

2

+

x

3

+

⋯

1 + x + x^2 + x^3 + \cdots

1+x+x2+x3+⋯

The corresponding sequence is

1

n

1^n

1n

As mentioned above

1

+

y

a

1

+

y

2

a

1

⋯

=

1

1

−

y

a

1

1+ y^{a_1}+ y^{2a_1}\cdots =\cfrac{1}{1-y^{a_1}}

1+ya1​+y2a1​⋯=1−ya1​1​

The final simplification result :

G

(

x

)

=

(

1

+

y

a

1

+

y

2

a

1

⋯
 

)

(

1

+

y

a

2

+

y

2

a

2

⋯
 

)

⋯

(

1

+

y

a

n

+

y

2

a

n

⋯
 

)

G(x) = (1+ y^{a_1}+ y^{2a_1}\cdots) (1+ y^{a_2} + y^{2a_2}\cdots) \cdots (1+ y^{a_n}+ y^{2a_n}\cdots )

G(x)=(1+ya1​+y2a1​⋯)(1+ya2​+y2a2​⋯)⋯(1+yan​+y2an​⋯)

          

=

1

(

1

−

y

a

1

)

(

1

−

y

a

2

)

⋯

(

1

−

y

a

n

)

\ \ \ \ \ \ \ \ \ \ =\cfrac{1}{ (1-y^{a_1}) (1-y^{a_2}) \cdots (1-y^{a_n}) }

          =(1−ya1​)(1−ya2​)⋯(1−yan​)1​

After the above generation function is written , Calculation an ,

y

y

y Of

N

N

N Coefficient of power , Namely Positive integer

N

N

N The number of splitting schemes ;