[combinatorics] number of solutions of indefinite equations (number of combinations of multiple sets R | number of non negative integer solutions of indefinite equations | number of integer solutions

Multiple sets r Combinatorial number Calculation method of generating function

Introduce... Here Solution of indefinite equation and Generating function coefficients , Help solve the problem ;

The following three values are equivalent :

① Multiple sets

S

=

{

n

1

⋅

a

1

,

n

2

⋅

a

2

,

⋯
 

,

n

k

⋅

a

k

}

S = \{n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \}

S={ n1​⋅a1​,n2​⋅a2​,⋯,nk​⋅ak​} Of

r

−

r-

r− Combinatorial number

② Indefinite equation

x

1

+

x

2

+

⋯

+

x

k

=

r

(

x

i

≤

n

i

)

x_1 + x_2 + \cdots + x_k = r (x_i \leq n_i)

x1​+x2​+⋯+xk​=r(xi​≤ni​) Number of nonnegative integer solutions of ;

③ Generating function

G

(

y

)

=

(

1

+

y

+

y

2

+

⋯

+

y

n

1

)

(

1

+

y

+

y

2

+

⋯

+

y

n

2

)

⋯

(

1

+

y

+

y

2

+

⋯

+

y

n

k

)

G(y) = (1+y+y^2 + \cdots + y^{n_1}) (1+y+y^2 + \cdots + y^{n_2})\cdots (1+y+y^2 + \cdots + y^{n_k})

G(y)=(1+y+y2+⋯+yn1​)(1+y+y2+⋯+yn2​)⋯(1+y+y2+⋯+ynk​) After deployment

y

r

y^r

yr The coefficient of ;

In the generating function

y

y

y Power of

0

0

0 To

n

i

n_i

ni​ ,

1

1

1 yes

y

0

y^0

y0 ;

x

i

x_i

xi​ Corresponding to multiple centralized , Specify an element

a

i

a_i

ai​ The number of ;

---

Multiple sets r Combinatorial number problem

subject : Calculation

S

=

{

3

⋅

a

,

4

⋅

b

,

5

⋅

c

}

S=\{3 \cdot a , 4 \cdot b , 5 \cdot c\}

S={ 3⋅a,4⋅b,5⋅c} Of 10- Combinatorial number ;

analysis : following Three Count It is equivalent. ;

• 1> Multiple sets $S=\{3\cdot a,4\cdot b,5\cdot c\}$

  10− Combinatorial number ;

• 2>$x_1 + x_2 + x_3 = 10 $ ,

  0

  ≤

  x

  1

  ≤

  3

  ,

  0

  ≤

  x

  2

  ≤

  4

  ,

  0

  ≤

  x

  3

  ≤

  5

  0 \leq x_1 \leq 3, 0 \leq x_2 \leq 4, 0 \leq x_3 \leq 5

  0≤x1​≤3,0≤x2​≤4,0≤x3​≤5 Number of nonnegative integer solutions of ;

• 3> Generating function $G(y)=(y^0+y^1+y^2+y^3)(y^0+y^1+y^2+y^3+y^4)(y^0+y^1+y^2+y^3+y^4+y^5)$

  y10 The coefficient of ;

Explain :

① Expand the above generation function :

G

(

y

)

=

(

y

0

+

y

1

+

y

2

+

y

3

)

(

y

0

+

y

1

+

y

2

+

y

3

+

y

4

)

(

y

0

+

y

1

+

y

2

+

y

3

+

y

4

+

y

5

)

G(y) = (y^0 + y^1 + y^2 + y^3) (y^0 + y^1 + y^2 + y^3 + y^4) (y^0 + y^1 + y^2 + y^3 + y^4 + y^5)

G(y)=(y0+y1+y2+y3)(y0+y1+y2+y3+y4)(y0+y1+y2+y3+y4+y5)

② among

y

0

=

1

y^0 = 1

y0=1 ,

y

1

=

y

y^1 =y

y1=y , Replace :

=

(

1

+

y

+

y

2

+

y

3

)

(

1

+

y

+

y

2

+

y

3

+

y

4

)

(

1

+

y

+

y

2

+

y

3

+

y

4

+

y

5

)

= (1 + y + y^2 + y^3) (1 + y + y^2 + y^3 + y^4) (1 + y + y^2 + y^3 + y^4 + y^5)

=(1+y+y2+y3)(1+y+y2+y3+y4)(1+y+y2+y3+y4+y5)

③ The first two items

(

1

+

y

+

y

2

+

y

3

)

(

1

+

y

+

y

2

+

y

3

+

y

4

)

(1 + y + y^2 + y^3) (1 + y + y^2 + y^3 + y^4)

(1+y+y2+y3)(1+y+y2+y3+y4) Work it out :

(

1

+

y

+

y

2

+

y

3

)

(

1

+

y

+

y

2

+

y

3

+

y

4

)

(1 + y + y^2 + y^3) (1 + y + y^2 + y^3 + y^4)

(1+y+y2+y3)(1+y+y2+y3+y4)

=

1

+

y

+

y

2

+

y

3

+

y

4

+

y

(

1

+

y

+

y

2

+

y

3

+

y

4

)

+

y

2

(

1

+

y

+

y

2

+

y

3

+

y

4

)

+

y

3

(

1

+

y

+

y

2

+

y

3

+

y

4

)

=1 + y + y^2 + y^3 + y^4 + y(1 + y + y^2 + y^3 + y^4) + y^2(1 + y + y^2 + y^3 + y^4) + y^3(1 + y + y^2 + y^3 + y^4)

=1+y+y2+y3+y4+y(1+y+y2+y3+y4)+y2(1+y+y2+y3+y4)+y3(1+y+y2+y3+y4)

=

1

+

2

y

+

3

y

2

+

4

y

3

+

4

y

4

+

3

y

5

+

2

y

6

+

y

7

=1+2y + 3y^2 + 4y^3 + 4y^4 + 3y^5 + 2y^6 + y^7

=1+2y+3y2+4y3+4y4+3y5+2y6+y7

④ take ③ Results are substituted into ② in :

G

(

y

)

=

(

1

+

2

y

+

3

y

2

+

4

y

3

+

4

y

4

+

3

y

5

+

2

y

6

+

y

7

)

(

1

+

y

+

y

2

+

y

3

+

y

4

+

y

5

)

G(y) = (1+2y + 3y^2 + 4y^3 + 4y^4 + 3y^5 + 2y^6 + y^7) (1 + y + y^2 + y^3 + y^4 + y^5)

G(y)=(1+2y+3y2+4y3+4y4+3y5+2y6+y7)(1+y+y2+y3+y4+y5)

⑤ It is meaningless to expand all the above expressions , Here we only count y^10 The combination of :

• 1> among $3y^5$

  3y10

• 2> among $2y^6$

  2y10

• 3> among $y^7$

  y10

⑥ Add the final results :

y

10

y^{10}

y10 The coefficient before is 6 ;

---

The number of solutions of the indefinite equation x The value range is ( 0 ~ n )

In this case value And Multiple sets Group

r

−

r-

r− Combinatorial numbers are equivalent ;
The number of each element in the multiset at this time Is limited to

0

0

0 To Some number

n

n

n Between ;

This is the case that the previous multiple set arrangement formula cannot be calculated , The generating function can be used here to count Multiple sets Of

r

−

r-

r− Combinatorial number ;

The following three values are equivalent :

① Indefinite equation

x

1

+

x

2

+

⋯

+

x

k

=

r

(

x

i

≤

n

i

)

x_1 + x_2 + \cdots + x_k = r (x_i \leq n_i)

x1​+x2​+⋯+xk​=r(xi​≤ni​) Number of solutions ;

② Multiple sets

S

=

{

n

1

⋅

a

1

,

n

2

⋅

a

2

,

⋯
 

,

n

k

⋅

a

k

}

S = \{n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \}

S={ n1​⋅a1​,n2​⋅a2​,⋯,nk​⋅ak​} Of

r

−

r-

r− Combinatorial number

③ Generating function

G

(

y

)

=

(

1

+

y

+

y

2

+

⋯

+

y

n

1

)

(

1

+

y

+

y

2

+

⋯

+

y

n

2

)

⋯

(

1

+

y

+

y

2

+

⋯

+

y

n

k

)

G(y) = (1+y+y^2 + \cdots + y^{n_1}) (1+y+y^2 + \cdots + y^{n_2})\cdots (1+y+y^2 + \cdots + y^{n_k})

G(y)=(1+y+y2+⋯+yn1​)(1+y+y2+⋯+yn2​)⋯(1+y+y2+⋯+ynk​) After deployment

y

r

y^r

yr The coefficient of ;

In the generating function

y

y

y Power of

0

0

0 To

n

i

n_i

ni​ ,

1

1

1 yes

y

0

y^0

y0 ;

x

i

x_i

xi​ Corresponding to multiple centralized , Specify an element

a

i

a_i

ai​ The number of ;

---

The number of solutions of the indefinite equation x The value range is Natural number ( 0 ~ ∞ ) It conforms to the calculation of the combination formula of multiple sets

In this case value And Multiple sets Group

r

−

r-

r− Combinatorial numbers are equivalent ;
The number of each element in the multiset at this time It's infinite perhaps Greater than be equal to

r

r

r ;

The problem of multiple set combination in this case , You can use a combination formula , Multiple sets Of

r

−

r-

r− Combine , Its have

k

k

k Elements The number of each kind is greater than or equal to

r

r

r or Infinite ; Use the formula

C

(

r

+

k

−

1

,

r

)

C(r + k - 1, r)

C(r+k−1,r)

The following three values are equivalent :

① Indefinite equation

x

1

+

x

2

+

⋯

+

x

k

=

r

(

0

≤

x

i

)

x_1 + x_2 + \cdots + x_k = r ( 0 \leq x_i)

x1​+x2​+⋯+xk​=r(0≤xi​) Number of solutions ;

② Multiple sets

S

=

{

∞

⋅

a

1

,

∞

⋅

a

2

,

⋯
 

,

∞

⋅

a

k

}

S = \{\infty \cdot a_1 , \infty \cdot a_2 , \cdots , \infty \cdot a_k \}

S={ ∞⋅a1​,∞⋅a2​,⋯,∞⋅ak​} Of

r

−

r-

r− Combinatorial number

③ Generating function

G

(

y

)

=

(

1

+

y

+

y

2

+

⋯
 

)

k

G(y) = (1+y+y^2 + \cdots )^k

G(y)=(1+y+y2+⋯)k After deployment

y

r

y^r

yr The coefficient of ;

In the generating function

y

y

y Power of

0

0

0 To

n

i

n_i

ni​ ,

1

1

1 yes

y

0

y^0

y0 ;

x

i

x_i

xi​ Corresponding to multiple centralized , Specify an element

a

i

a_i

ai​ The number of ;

---

The number of solutions of the indefinite equation x Value range ( Given a range )

In this case Combination of multiple sets It's time to quit the stage , only Solution of indefinite equation and Coefficient of generating function 了 ,

x

i

x_i

xi​ The value of may be negative ;

The following two values are equivalent :

① Indefinite equation

x

1

+

x

2

+

⋯

+

x

k

=

r

(

l

i

≤

x

i

≤

n

j

)

x_1 + x_2 + \cdots + x_k = r ( l_i \leq x_i \leq n_j)

x1​+x2​+⋯+xk​=r(li​≤xi​≤nj​) Number of solutions ;

② Generating function

G

(

y

)

=

(

y

l

1

+

⋯

+

y

n

1

)

(

y

l

2

+

⋯

+

y

n

2

)

⋯

(

y

l

k

+

⋯

+

y

n

k

)

G(y) = (y^{l_1} + \cdots + y^{n_1})(y^{l_2} + \cdots + y^{n_2})\cdots(y^{l_k} + \cdots + y^{n_k})

G(y)=(yl1​+⋯+yn1​)(yl2​+⋯+yn2​)⋯(ylk​+⋯+ynk​) After deployment

y

r

y^r

yr The coefficient of ;

③ The problem of multiple sets is not applicable here ,

x

x

x The value may be negative ;

In the generating function

y

y

y Power of

i

i

i To

j

j

j ;

---

The number of solutions of the indefinite equation x Value range ( Given a range Coalescence coefficient )

The following two values are equivalent :

① Indefinite equation

p

1

x

1

+

p

2

x

2

+

⋯

+

p

k

x

k

=

r

(

l

i

≤

x

i

≤

n

j

)

p_1x_1 + p_2x_2 + \cdots + p_kx_k = r ( l_i \leq x_i \leq n_j)

p1​x1​+p2​x2​+⋯+pk​xk​=r(li​≤xi​≤nj​) Number of solutions ;

② Generating function

G

(

y

)

=

(

(

y

1

p

)

l

1

+

⋯

+

(

y

1

p

)

n

1

)

(

(

y

2

p

)

l

2

+

⋯

+

(

y

2

p

)

n

2

)

⋯

(

(

y

k

p

)

l

k

+

⋯

+

(

y

k

p

)

n

k

)

G(y) = ((y^p_1)^{l_1} + \cdots + (y^p_1)^{n_1})((y^p_2)^{l_2} + \cdots + (y^p_2)^{n_2})\cdots((y^p_k)^{l_k} + \cdots + (y^p_k)^{n_k})

G(y)=((y1p​)l1​+⋯+(y1p​)n1​)((y2p​)l2​+⋯+(y2p​)n2​)⋯((ykp​)lk​+⋯+(ykp​)nk​) After deployment

y

r

y^r

yr The coefficient of ;

③ The problem of multiple sets is not applicable here ,

x

x

x The value may be negative ;

Note that the indefinite equation has coefficients , You need to use

y

system

Count

y^{ coefficient }

y system Count replace

y

y

y , In the generating function

y

system

Count

y^{ coefficient }

y system Count Power of

i

i

i To

j

j

j ;

---

The problem of solutions of indefinite equations With restrictions

subject : Find the equation

x

1

+

x

2

+

x

3

+

x

4

=

15

x_1 + x_2 + x_3 + x_4 = 15

x1​+x2​+x3​+x4​=15 Number of integer solutions , among

x

1

≥

1

,

x

2

≥

2

,

x

3

≥

4

,

x

4

≥

4

x_1 \geq 1 , x_2 \geq 2 , x_3 \geq 4 , x_4 \geq 4

x1​≥1,x2​≥2,x3​≥4,x4​≥4 ;

analysis :

• 1> Don't solve directly : List the generating functions directly , It complicates the problem ;
• 2> Conversion : Here we can turn it into Calculate the number of non negative integer solutions ;
• 3> The combinatorial number of multiple sets : This is equivalent to Multiple sets $S=\{\infty \cdot a_1,\infty \cdot a_2,\cdots ,\infty \cdot a_k\}$

  C(r+k−1,r) Calculation ;

Explain :

① Prepare for RMB Exchange :

• 1> Make $y_1=x_1-1$
• 2> Make $y_2=x_2-2$
• 3> Make $y_3=x_3-4$
• 4> Make $y_4=x_4-4$

② Conversion process :

• 1> Use $y_1+1$
• 2> Use $y_2+2$
• 3> Use $y_3+4$
• 4> Use $y_4+4$

x

1

+

x

2

+

x

3

+

x

4

=

15

x_1 + x_2 + x_3 + x_4 = 15

x1​+x2​+x3​+x4​=15

(

y

1

+

1

)

+

(

y

2

+

2

)

+

(

y

3

+

4

)

+

(

y

4

+

4

)

=

15

(y_1 + 1) + (y_2 + 2) + (y_3 + 4) + (y_4 + 4) = 15

(y1​+1)+(y2​+2)+(y3​+4)+(y4​+4)=15

y

1

+

y

2

+

y

3

+

y

4

+

11

=

15

y_1 + y_2 + y_3+y_4 + 11 = 15

y1​+y2​+y3​+y4​+11=15

y

1

+

y

2

+

y

3

+

y

4

=

4

y_1 + y_2 + y_3+y_4 = 4

y1​+y2​+y3​+y4​=4

③ seek

y

1

+

y

2

+

y

3

+

y

4

=

4

y_1 + y_2 + y_3+y_4 = 4

y1​+y2​+y3​+y4​=4 (

y

i

y_i

yi​ It's a natural number ) , Number of nonnegative integer solutions ;
It's equivalent to asking for

S

=

{

∞

⋅

a

1

,

∞

⋅

a

2

,

∞

⋅

a

3

,

∞

⋅

a

4

}

S = \{\infty \cdot a_1 , \infty \cdot a_2 , \infty \cdot a_3, \infty \cdot a_4 \}

S={ ∞⋅a1​,∞⋅a2​,∞⋅a3​,∞⋅a4​} Of

4

−

4-

4− Combinatorial number , According to the formula

C

(

r

+

k

−

1

,

r

)

C(r + k - 1 , r)

C(r+k−1,r) Calculation :

C

(

4

+

4

−

1

,

4

)

=

C

(

7

,

4

)

=

(

7

4

)

=

7

!

(

7

−

4

)

!

4

!

=

7

×

6

×

5

×

4

×

3

×

2

×

1

4

×

3

×

2

×

1

×

3

×

2

×

1

=

35

C(4 + 4 - 1 , 4) = C(7,4) = \dbinom{7}{4} = \cfrac{7!}{(7-4)!4!} = \cfrac{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{4 \times 3 \times 2 \times 1 \times 3 \times 2 \times 1} = 35

C(4+4−1,4)=C(7,4)=(47​)=(7−4)!4!7!​=4×3×2×1×3×2×17×6×5×4×3×2×1​=35

Solve this Integer solution The number of questions :
① If

x

i

x_i

xi​ The range of phi is zero Natural number or It can be transformed into Natural number , Then use Multiple sets Combined formula calculation ;
② If

x

i

x_i

xi​ The value range of is a closed interval , Directly generate functions an , Calculation

y

r

y^r

yr What is the coefficient of , This coefficient is the number of integer solutions ;

---