[combinatorics] generating function (positive integer splitting | unordered non repeated splitting example)

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 )

One 、 Positive integer split summary

---

Positive integer split , You need to give Number after splitting ,

The number of each split , Can have a corresponding Generate function items ,

Every Generate the item of the function

y

y

y Number of power terms , With this The number and type of values of the number to be split equally ,

Such as : A number that is split

a

1

a_1

a1​ , Its It can take

0

,

1

,

2

0,1,2

0,1,2 Three values , So the corresponding Generate the item of the function

y

y

y Number of power terms Yes

3

3

3 It's worth , by

(

y

a

1

)

0

+

(

y

a

1

)

1

+

(

y

a

1

)

2

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

(ya1​)0+(ya1​)1+(ya1​)2 ,

In the generated function item The bottom is

y

By

Demolition

branch

Of

Count

y^{ The number to be split }

y By Demolition branch Of Count , A sub idempotent is The positive integer Possible values , Item in

y

y

y The number of power components Namely The Positive integer The number of types of values ;

Positive integer split , Allow repetition And No repetition , The difference is that Split integer The number of occurrences of ,

• If No repetition , That should be split Positive integer Can only appear

  0

  ,

  1

  0,1

  0,1 Time ;

• If Allow repetition , Then the positive integer can appear

  0

  ,

  1

  ,

  2

  ,

  ⋯

  0,1,2, \cdots

  0,1,2,⋯ Infinite times ;

Positive integer split generator :

• Number of generated function items : Namely The number of positive integer types after splitting ; It can be divided into $2,4,8$
• Generate... In the function item $0,1$

  y Power number : Corresponding A positive integer after splitting Number of value types ; A split integer may appear

• Generate... In the function item $y^{DemolitionbranchafterOfjustwholeCount}$

  y Power base :

• Generate... In the function item $5$

  y The next power : Of a positive integer after splitting Number of values ; A positive integer after splitting is

Two 、 Positive integer split example

---

Prove any Positive integer Binary representation is unique ;

The above problem can be equivalent to , take Arbitrary positive integer , Fine Break it down into

2

2

2 The sum of the powers of , also Duplicate elements are not allowed ;

2

2

2 To the power of :

2

0

,

2

1

,

2

2

,

2

3

,

⋯

2^0, 2^1, 2^2, 2^3 , \cdots

20,21,22,23,⋯

Because repetition is not allowed , So every

2

2

2 The next power The number of , Can only be

0

,

1

0,1

0,1 Two cases ;

According to the model of positive integer splitting , Write a generating function :

2

0

2^0

20 Corresponding generating function items : The bottom is

y

2

0

=

y

y^{2^0} = y

y20=y , Value

0

,

1

0, 1

0,1 , Corresponding The generated function item is

y

0

+

y

1

=

1

+

y

y^0 + y^1 = 1+ y

y0+y1=1+y

2

1

2^1

21 Corresponding generating function items : The bottom is

y

2

1

=

y

2

y^{2^1} = y^2

y21=y2 , Value

0

,

1

0, 1

0,1 , Then the corresponding generating function item is

(

y

2

)

0

+

(

y

2

)

1

=

1

+

y

2

(y^2)^0 + (y^2)^1 = 1+ y^2

(y2)0+(y2)1=1+y2

2

2

2^2

22 Corresponding generating function items : The bottom is

y

2

2

=

y

4

y^{2^2} = y^4

y22=y4 , Value

0

,

1

0, 1

0,1 , Then the corresponding generating function item is

(

y

4

)

0

+

(

y

4

)

1

=

1

+

y

4

(y^4)^0 + (y^4)^1 = 1+ y^4

(y4)0+(y4)1=1+y4

2

3

2^3

23 Corresponding generating function items : The bottom is

y

2

3

=

y

8

y^{2^3} = y^8

y23=y8 , Value

0

,

1

0, 1

0,1 , Then the corresponding generating function item is

(

y

8

)

0

+

(

y

8

)

1

=

1

+

y

8

(y^8)^0 + (y^8)^1 = 1+ y^8

(y8)0+(y8)1=1+y8

⋮

\vdots

⋮

The complete generating function is :

G

(

x

)

=

(

1

+

y

)

(

1

+

y

2

)

(

1

+

y

4

)

(

1

+

y

8

)

⋯

G(x) = (1+ y)(1+ y^2)(1+ y^4)(1+ y^8)\cdots

G(x)=(1+y)(1+y2)(1+y4)(1+y8)⋯

Break down each of the above Generate function items :

1

+

y

=

1

−

y

2

1

−

y

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

1+y=1−y1−y2​

1

+

y

2

=

1

−

y

4

1

−

y

2

1+ y^2= \cfrac{1-y^4}{1-y^2}

1+y2=1−y21−y4​

1

+

y

4

=

1

−

y

8

1

−

y

4

1+ y^4= \cfrac{1-y^8}{1-y^4}

1+y4=1−y41−y8​

Substitute the above three equations into the generating function

G

(

x

)

G(x)

G(x) in ,

G

(

x

)

=

1

−

y

2

1

−

y

⋅

1

−

y

4

1

−

y

2

⋅

1

−

y

8

1

−

y

4

⋯

G(x) = \cfrac{1-y^2}{1-y} \cdot \cfrac{1-y^4}{1-y^2} \cdot \cfrac{1-y^8}{1-y^4} \cdots

G(x)=1−y1−y2​⋅1−y21−y4​⋅1−y41−y8​⋯

          

=

1

1

−

y

\ \ \ \ \ \ \ \ \ \ = \cfrac{1}{1-y}

          =1−y1​

          

=

1

+

y

+

y

2

+

y

3

+

⋯

\ \ \ \ \ \ \ \ \ \ = 1 + y + y^2 + y^3 + \cdots

          =1+y+y2+y3+⋯

The above generating function is

1

n

1^n

1n General formula Of the corresponding sequence Generating function ;

After the above generation function is expanded , The coefficient before each term is

1

1

1 , There is only one solution ;