[combinatorics] generating function (positive integer splitting | basic model of positive integer splitting | disordered splitting with restrictions)

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

One 、 Basic model of positive integer splitting

---

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 ;

The corresponding generating function is :

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​)

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 ;

The corresponding generating function is :

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​⋯)

or

G

(

x

)

=

1

(

1

−

y

a

1

)

(

1

−

y

a

2

)

⋯

(

1

−

y

a

n

)

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

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

Two 、 Disorderly splitting with restrictions

---

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

There are restrictions ,

a

i

a_i

ai​ The number of values

x

i

x_i

xi​ Value range Make some restrictions ,

l

i

≤

x

i

≤

t

i

l_i \leq x_i \leq t_i

li​≤xi​≤ti​

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 )

Disordered splitting under the above restricted conditions , Is complete With coefficients , With restrictions Of Nonnegative integer solutions of indefinite equations The problem of ;