[combinatorics] generating function (use generating function to solve the number of solutions of indefinite equation example 2 | extended to integer solution)

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 )

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 ;

The weights can be placed on the left and right sides

The concept of generating functions , It can be generalized to the negative power , On the left is a positive number , No, it's

0

0

0 , On the right is a negative number ,

1

1

1 Gram's weight The number is

x

1

x_1

x1​ individual , The value range is

−

2

≤

x

1

≤

2

-2 \leq x_1 \leq 2

−2≤x1​≤2 , Value for

−

2

,

−

1

,

0

,

1

,

2

-2, -1, 0 , 1, 2

−2,−1,0,1,2

2

2

2 The number of weights of gram is

x

2

x_2

x2​ individual , The value range is

−

1

≤

x

2

≤

1

-1 \leq x_2 \leq 1

−1≤x2​≤1 , Value for

−

1

,

0

,

1

-1, 0,1

−1,0,1

4

4

4 The number of weights of gram is

x

3

x_3

x3​ individual , The value range is

−

2

≤

x

3

≤

2

-2 \leq x_3 \leq 2

−2≤x3​≤2 , Value for

−

2

,

−

1

,

0

,

1

,

2

-2, -1, 0,1,2

−2,−1,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

(

y

−

2

+

y

−

1

+

1

+

y

+

y

2

)

(y^{-2} + y^{-1} + 1 + y + y^2 )

(y−2+y−1+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

)

−

1

+

(

y

2

)

0

+

(

y

2

)

1

=

y

−

2

+

1

+

y

2

(y^2)^{-1} + (y^2)^0 + (y^2)^1 = y^{-2} + 1+ y^2

(y2)−1+(y2)0+(y2)1=y−2+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

)

−

2

+

(

y

4

)

−

1

+

(

y

4

)

0

+

(

y

4

)

1

+

(

y

4

)

2

=

y

−

8

+

y

−

4

+

1

+

y

4

+

y

8

(y^4)^{-2} + (y^4)^{-1} + (y^4)^0 + (y^4)^1 + (y^4)^2 = y^{-8} + y^{-4} + 1+ y^4 + y^8

(y4)−2+(y4)−1+(y4)0+(y4)1+(y4)2=y−8+y−4+1+y4+y8

Multiply the above three items , And unfold :

G

(

x

)

=

(

y

−

2

+

y

−

1

+

1

+

y

+

y

2

)

(

y

−

2

+

1

+

y

2

)

(

y

−

8

+

y

−

4

+

1

+

y

4

+

y

8

)

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

G(x)=(y−2+y−1+1+y+y2)(y−2+1+y2)(y−8+y−4+1+y4+y8)

          

=

5

+

3

y

+

4

y

2

+

3

y

3

+

5

y

4

+

3

y

5

+

4

y

6

+

3

y

7

+

4

y

8

+

2

y

9

+

2

y

10

+

y

11

+

y

12

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

          =5+3y+4y2+3y3+5y4+3y5+4y6+3y7+4y8+2y9+2y10+y11+y12

After the above expansion

y

y

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

4

y

2

4y^2

4y2 Item representation , Weigh out

2

2

2 Gram weight , Yes

4

4

4 A plan ;

General description :

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