[combinatorics] generating function (positive integer splitting | repeated ordered splitting | non repeated ordered splitting | proof of the number of repeated ordered splitting schemes)

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 )

One 、 Repeated ordered splitting

---

take Positive integer

N

N

N Repeatedly , Orderly splitting become

r

r

r part , The number of programmes is

C

(

N

−

1

,

r

−

1

)

C(N-1, r-1)

C(N−1,r−1) *

( 3、 ... and 、 The combination number is proved in )

If the Positive integer

N

N

N do Arbitrary repeated ordered splitting , It can be split into

1

1

1 Number ,

2

2

2 Number ,

⋯

\cdots

⋯ ,

N

N

N Number ,

Split into

1

1

1 The number of schemes is

(

N

−

1

1

−

1

)

\dbinom{N-1}{1-1}

(1−1N−1​)

Split into

2

2

2 The number of schemes is

(

N

−

1

2

−

1

)

\dbinom{N-1}{2-1}

(2−1N−1​)

⋮

\vdots

⋮

Split into

N

N

N The number of schemes is

(

N

−

1

N

−

1

)

\dbinom{N-1}{N-1}

(N−1N−1​)

The total number of schemes mentioned above is :

∑

r

=

1

N

=

2

N

−

1

\sum\limits_{r=1}^{N}=2^{N-1}

r=1∑N​=2N−1

( It is calculated according to the basic combinatorial identity )

Two 、 Do not repeat orderly splitting

---

to Do not repeat unordered splitting , Proceed again Full Permutation ;

1、 Unordered split basic model

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​) * Focus on here

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​

2、 Full Permutation

n

n

n The whole permutation is

n

!

n!

n!

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

3、 ... and 、 Proof of the number of repeated ordered splitting schemes

---

Use a one-to-one correspondence method to prove : take Positive integer

N

N

N Repeatedly , Orderly splitting become

r

r

r part , The number of programmes is

C

(

N

−

1

,

r

−

1

)

C(N-1, r-1)

C(N−1,r−1) *

A positive integer after splitting , If the order is changed , The arrangement is different , The number of schemes it represents is also different ;

Convert this split into a combinatorial counting problem ;

hypothesis

N

=

a

1

+

a

2

+

⋯

+

a

r

N=a_1 + a_2 + \cdots + a_r

N=a1​+a2​+⋯+ar​ Is a split that meets the conditions , This split repeat , Orderly ;

Put the above scheme , Make a partial sequence ,

Split plan And Split sequence :

Write the splitting sequence according to the splitting scheme :

The original plan

6

=

1

+

2

+

3

6=1+2+3

6=1+2+3 , Make a partial sequence from the original scheme ,

The first sequence

S

1

=

1

S_1 = 1

S1​=1 , Take the first component of the original scheme

1

1

1 come out ,

The second sequence

S

2

=

1

+

2

=

3

S_2 = 1 + 2 = 3

S2​=1+2=3 , Take the first two components of the original scheme

1

+

2

1 + 2

1+2 come out ,

The third sequence

S

3

=

1

+

2

+

3

=

6

S_3 = 1 + 2 + 3 = 6

S3​=1+2+3=6 , Take the first three components of the original scheme

1

+

2

+

3

1 + 2 + 3

1+2+3 come out ,

The first sequence is the first number , The second sequence is the first two numbers , The first

n

n

n The first sequence is the first

n

n

n Number , The last sequence contains all split positive integers ;

Just give an original plan , You can make the above partial sequence ;

As long as the plan is the same , The sequence is exactly the same , The plan is different , The sequence must be different ;

Write the splitting scheme according to the splitting sequence :

conversely , Given a sequence , Sure Restore a splitting scheme , If the sequence is given

S

1

=

1

,

S

2

=

3

,

S

3

=

6

S_1 = 1 , S_2=3, S_3=6

S1​=1,S2​=3,S3​=6 , Corresponding splitting scheme :

The sum of all numbers in the last sequence , The split positive integer is the value of the last sequence

6

6

6

The first positive integer Is the first sequence

1

1

1

The second positive integer Is the second sequence minus the first sequence

S

2

−

S

1

=

3

−

1

=

2

S_2 - S_1 = 3-1=2

S2​−S1​=3−1=2

The third positive integer Is the third sequence minus the second sequence

S

3

−

S

2

=

6

−

3

=

3

S_3-S_2=6-3=3

S3​−S2​=6−3=3

The splitting scheme is

6

=

1

+

2

+

3

6 = 1+2+3

6=1+2+3

N

=

a

1

+

a

2

+

⋯

+

a

r

N=a_1 + a_2 + \cdots + a_r

N=a1​+a2​+⋯+ar​ The split sequence of is

S

1

=

a

1

S_1 = a_1

S1​=a1​

S

2

=

a

1

+

a

2

S_2= a_1 + a_2

S2​=a1​+a2​

S

3

=

a

1

+

a

2

+

a

3

S_3= a_1 + a_2 + a_3

S3​=a1​+a2​+a3​

⋮

\vdots

⋮

S

i

=

a

1

+

a

2

+

a

3

+

⋯

+

a

i

=

∑

k

=

1

t

a

i

 

,

     

i

=

1

,

2

,

3

,

⋯

S_i= a_1 + a_2 + a_3 + \cdots + a_i = \sum\limits_{k=1}^ta_i\ , \ \ \ \ \ i=1,2,3, \cdots

Si​=a1​+a2​+a3​+⋯+ai​=k=1∑t​ai​ ,     i=1,2,3,⋯

The above split sequence must have the following properties :

0

<

S

1

<

S

2

<

⋯

<

S

r

=

N

0 < S_1 < S_2 < \cdots < S_r = N

0<S1​<S2​<⋯<Sr​=N

because

S

2

S_2

S2​ Must be

S

1

S_1

S1​ Add a positive integer ,

S

r

S_r

Sr​ Must be

S

r

−

1

S_{r-1}

Sr−1​ Add a positive integer , The last item is all

r

r

r Sum of positive integers , Is a positive integer split

N

N

N ;

The above split sequence

S

1

,

S

2

,

⋯
 

,

S

r

S_1, S_2, \cdots , S_r

S1​,S2​,⋯,Sr​ , Last number

S

r

=

N

S_r = N

Sr​=N ,

The last number doesn't matter , Ahead

r

−

1

r-1

r−1 The value range of the number is

1

,

2

,

3

,

⋯
 

,

N

−

1

1, 2, 3, \cdots , N-1

1,2,3,⋯,N−1 , Within the above value range Yes

n

−

1

n-1

n−1 A positive integer ;

from

n

−

1

n-1

n−1 In a positive integer , selection

r

−

1

r-1

r−1 A positive integer ,

therefore , take Positive integer

N

N

N Repeatedly , Orderly splitting become

r

r

r part , The number of programmes is

C

(

N

−

1

,

r

−

1

)

C(N-1, r-1)

C(N−1,r−1) *