当前位置：网站首页>[combinatorics] generating function (generating function application scenario | using generating function to solve recursive equation)

[combinatorics] generating function (generating function application scenario | using generating function to solve recursive equation)

2022-07-03 17:57:00 【Programmer community】

List of articles

One 、 Generate function application scenarios
Two 、 Solving recursive equations using generating functions

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 )

One 、 Generate function application scenarios

Generate function application scenarios :

Solve the recursive equation
Multiple sets
$r$ Combination count
The number of solutions of the indefinite equation
integer partition

Multiple sets

$r$ Combination count , Before Only the number of combinations in special cases can be counted , That is, the selected number

$r$ Less than the repetition of each term of the multiple set , Only then Combinatorial number

(

−

)

N= C(k + r - 1, r)

$N = C (k + r - 1, r)$ , If

$r$ Greater than repeatability , You need to use the generating function to solve ;

The number of solutions of the indefinite equation , Before, we can only solve Without constraints , If there are constraints on variables , Such as

x_1

$x_{1}$ Values can only be taken in a certain interval , In this case , You must use the generating function to solve ;

integer partition , Split a positive number into the sum of several integers , Number of splitting schemes , It can also be calculated by generating functions ;

Review multiple set permutations :

Repeatable elements , Orderly selection , Corresponding Arrangement of multiple sets ; $\cfrac{n!}{n_1! n_2! \cdots n_k!} whole row Column =n1!n2!⋯nk!n! , Incomplete permutation k r , r ≤ n i k^r , \ \ r\leq n_ikr, r≤ni$
Repeatable elements , Unordered selection , Corresponding Combination of multiple sets ;

Two 、 Solving recursive equations using generating functions

Recurrence equation :

−

a_n - 5a_{n-1} + 6a_{n-2} = 0

$a_{n} - 5 a_{n - 1} + 6 a_{n - 2} = 0$

initial value :

a_0 = 1, a_1 = 2

$a_{0} = 1, a_{1} = 2$

{

}

\{a_n\}

${a_{n}}$ Number sequence is

{

⋯

}

\{ a_0 , a_1, a_2, a_3 , \cdots , a_n , \cdots\}

${a_{0}, a_{1}, a_{2}, a_{3}, \dots, a_{n}, \dots}$

a_n

$a_{n}$ The corresponding generating function is

(

)

⋯

G(x) = a_0 + a_1 x + a_2 x^2 + a_3x^3 + \cdots

$G (x) = a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3} + \dots$

According to the recursive equation , At the same time, in order to make the following items can be about , Use

−

-5x

$- 5 x$ multiply

(

)

G(x)

$G (x)$ Generating function , Use

+6x^2

$+ 6 x^{2}$ multiply

(

)

G(x)

$G (x)$ , Get the following three formulas ,

−

-5x

$- 5 x$ multiply

(

)

G(x)

$G (x)$ The first thing you get is

$x$ The first power term of , Map this item to

(

)

G(x)

$G (x)$ Medium

$x$ Under the power term ,

+6x^2

$+ 6 x^{2}$ multiply

(

)

G(x)

$G (x)$ The first thing you get is

$x$ The quadratic term of , Map this item to

(

)

G(x)

$G (x)$ Medium

$x$ Under the quadratic term ;

(

)

⋯

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ G(x) = a_0 + a_1 x + a_2 x^2 + a_3x^3 + \cdots

$G (x) = a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3} + \dots$

−

(

)

−

⋯

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -5x \ G(x) = \ \ \ \ -5a_0x - 5a_1x^2 - 5a_2x^3 - \cdots

$- 5 x G (x) = - 5 a_{0} x - 5 a_{1} x^{2} - 5 a_{2} x^{3} - \dots$

(

)

⋯

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6x^2 \,G(x) = \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + \,6a_0x^2 + 6a_x^3 + \cdots

$6 x^{2} G (x) = + 6 a_{0} x^{2} + 6 a_{x}^{3} + \dots$

(

−

)

(

)

(

−

)

(1-5x+6x^2)G(x) =a_0 + (a_1 - 5a_0)x

$(1 - 5 x + 6 x^{2}) G (x) = a_{0} + (a_{1} - 5 a_{0}) x$

The formula below the above horizontal line is Above the horizontal line The result of adding the three formulas ;

Observe the above right The third column , The red box in the picture ;
Insert picture description here

After the above power alignment , The third column to the right of the appearing equal sign

−

+ a_2 x^2 -5a_1x^2 + \,6a_0x^2

$+ a_{2} x^{2} - 5 a_{1} x^{2} + 6 a_{0} x^{2}$ , Will the

x^2

$x^{2}$ Extract to get

(

−

)

(a_2 - 5a_1 + 6a_0)x^2

$(a_{2} - 5 a_{1} + 6 a_{0}) x^{2}$ , It just corresponds to the recursive equation

−

a_n - 5a_{n-1} + 6a_{n-2} = 0

$a_{n} - 5 a_{n - 1} + 6 a_{n - 2} = 0$ ,

So there is

−

a_2 - 5a_1 + 6a_0 = 0

$a_{2} - 5 a_{1} + 6 a_{0} = 0$ , Then you can get

(

−

)

(a_2 - 5a_1 + 6a_0)x^2 = 0

$(a_{2} - 5 a_{1} + 6 a_{0}) x^{2} = 0$

From this we can see that , If all three formulas are added , The figure below Inside the blue rectangle on the right , All of them are

$0$ ;

Insert picture description here

At present, only

−

a_0 + a_1x -5a_0x

$a_{0} + a_{1} x - 5 a_{0} x$ Three items ; Among them

−

a_0 = 1 , a_1 = -2

$a_{0} = 1, a_{1} = - 2$ Is the initial value ;

On the right side of the final equation is :

−

1 - 2x - 5x = 1-7x

$1 - 2 x - 5 x = 1 - 7 x$

Substitute the above formula into

(

−

)

(

)

(

−

)

(1-5x+6x^2)G(x) =a_0 + (a_1 - 5a_0)x

$(1 - 5 x + 6 x^{2}) G (x) = a_{0} + (a_{1} - 5 a_{0}) x$ in , Use

−

1 - 2x - 5x = 1-7x

$1 - 2 x - 5 x = 1 - 7 x$ Replace the formula on the right side of the equation , obtain :

(

−

)

(

)

−

(1-5x+6x^2)G(x) =1-7x

$(1 - 5 x + 6 x^{2}) G (x) = 1 - 7 x$

(

)

−

G(x) = \cfrac{1-7x}{1-5x+6x^2}

$G (x) = \frac{1 - 7 x}{1 - 5 x + 6 x ^{2}}$

Use Given Generating function , Find the corresponding series Of Method , Expand the above formula , Reference resources 【 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 ) Two 、 Calculate the series given the generating function Method ,

First factorize the denominator , Then set two undetermined coefficients , After passing points , according to

$x$ Write the equations with the term coefficients , Finally solve the equations , In the end, you can get :

(

)

−