[combinatorics] generating function (example of using generating function to solve the number of solutions of indefinite equation)

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 )

One 、 Examples of using generating functions to solve the number of solutions of indefinite equations

---

1

1

1 Gram weight

2

2

2 individual ,

2

2

2 Gram weight

1

1

1 individual ,

4

4

4 Gram weight

2

2

2 individual ,
Which weights can be weighed , How many schemes are there ;

1

1

1 Gram's weight The number is

x

1

x_1

x1​ individual , The value range is

0

≤

x

1

≤

2

0 \leq x_1 \leq 2

0≤x1​≤2 , Value for

0

,

1

,

2

0 , 1, 2

0,1,2

2

2

2 The number of weights of gram is

x

2

x_2

x2​ individual , The value range is

0

≤

x

2

≤

1

0 \leq x_2 \leq 1

0≤x2​≤1 , Value for

0

,

1

0,1

0,1

4

4

4 The number of weights of gram is

x

3

x_3

x3​ individual , The value range is

0

≤

x

3

≤

2

0 \leq x_3 \leq 2

0≤x3​≤2 , Value for

0

,

1

,

2

0,1,2

0,1,2

x

1

+

2

x

2

+

4

x

3

=

r

x_1 + 2x_2 + 4x_3 = r

x1​+2x2​+4x3​=r , among

r

r

r Represents the weight that can be weighed ,

Write the above , With restrictions , And with coefficients Of nonnegative integer solutions of indefinite equations Generating function :

x

1

x_1

x1​ term , With restrictions , There is no coefficient , Its The bottom is

y

y

y , Power value

0

,

1

,

2

0 , 1, 2

0,1,2 , The corresponding generating function item is

(

1

+

y

+

y

2

)

( 1 + y + y^2 )

(1+y+y2)

x

2

x_2

x2​ term , With restrictions , With coefficients

2

2

2 , Its The bottom is

y

2

y^2

y2 , Power value

0

,

1

0,1

0,1 , 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

x

3

x_3

x3​ term , With restrictions , With coefficients

4

4

4 , Its The bottom is

y

4

y^4

y4 , Power value

0

,

1

,

2

0,1, 2

0,1,2 , The corresponding generating function item is

(

y

4

)

0

+

(

y

4

)

1

+

(

y

4

)

2

=

1

+

y

4

+

y

8

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

(y4)0+(y4)1+(y4)2=1+y4+y8

Multiply the above three items , And unfold :

G

(

x

)

=

(

1

+

y

+

y

2

)

(

1

+

y

2

)

(

1

+

y

4

+

y

8

)

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

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

          

=

1

+

y

+

2

y

2

+

y

3

+

2

y

4

+

y

5

+

2

y

6

+

y

7

+

2

y

8

+

y

9

+

2

y

10

+

y

11

+

y

12

\ \ \ \ \ \ \ \ \ \ =1 + y + 2y^2 + y^3 + 2y^4 + y^5 + 2y^6 + y^7 + 2y^8 + y^9 + 2y^{10} + y^{11} + y^{12}

          =1+y+2y2+y3+2y4+y5+2y6+y7+2y8+y9+2y10+y11+y12

After the above expansion

y

y

y The idempotent of is weight , The coefficient is Number of schemes , Such as

2

y

8

2y^8

2y8 Item representation , Weigh out

8

8

8 Gram weight , Yes

2

2

2 A plan ;

General description :

• $1$
• $y$
• $2y^2$
• $y^3$
• $2y^4$
• $y^5$
• $2y^6$
• $y^7$
• $2y^8$
• $y^9$
• $2y^{10}$
• $y^{11}$
• $y^{12}$