当前位置：网站首页>[combinatorics] generating function (linear property | product property)

[combinatorics] generating function (linear property | product property)

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

List of articles

One 、 Linear property of generating function
Two 、 Linear property of generating function 2
3、 ... and 、 Product property of generating function

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 )

One 、 Linear property of generating function

Generating function Linear properties 1 :

b_n = \alpha a_n

$b_{n} = α a_{n}$ , be

(

)

(

)

B(x) = \alpha A(x)

$B (x) = α A (x)$

The sequence

a_n

$a_{n}$ The generating function of is

(

)

A(x)

$A (x)$ , The sequence

b_n

$b_{n}$ The generating function of is

(

)

B(x)

$B (x)$ ,

b_n

$b_{n}$ The sequence yes

a_n

$a_{n}$ The sequence Of

\alpha

$α$ times , So the corresponding The generating function also has a corresponding relationship ;

Method of proof : Expand both sides , Just insert according to the definition ;

Two 、 Linear property of generating function 2

Generating function Linear properties 2 :

c_n = a_n + b_n

$c_{n} = a_{n} + b_{n}$ , be

(

)

(

)

(

)

C(x) = A(x) + B(x)

$C (x) = A (x) + B (x)$

The sequence

a_n

$a_{n}$ The generating function of is

(

)

A(x)

$A (x)$ , The sequence

b_n

$b_{n}$ The generating function of is

(

)

B(x)

$B (x)$ , The sequence

c_n

$c_{n}$ The tax included in the generation of is

(

)

C(x)

$C (x)$ ,

Sequence sum Of Generating function , be equal to Generate the sum of functions ;

One sequence is Linear combination of other series , So it Generate functions and combine them accordingly , You can also find Generating function of large sequence ;

Method of proof : Expand both sides , Just insert according to the definition ;

3、 ... and 、 Product property of generating function

Generating function Product properties :

∑

−

c_n = \sum\limits_{i=0}^n a_i b_{n-i}

$c_{n} = i = 0 \sum n a_{i} b_{n - i}$ , Then there are

(

)

(

)

⋅

(

)

C(x) = A(x) \cdot B(x)

$C (x) = A (x) \cdot B (x)$

The sequence

a_n

$a_{n}$ The generating function of is

(

)

A(x)

$A (x)$ , The sequence

b_n

$b_{n}$ The generating function of is

(

)

B(x)

$B (x)$ , The sequence

c_n

$c_{n}$ The tax included in the generation of is

(

)

C(x)

$C (x)$ ,

The sequence

a_n

$a_{n}$ The generating function of :

(

)

⋯

A(x) = a_0 + a_1x + a_2x^2 + \cdots

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

The sequence

b_n

$b_{n}$ The generating function of :

(

)

⋯

B(x) = b_0 + b_1x + b_2x^2 + \cdots

$B (x) = b_{0} + b_{1} x + b_{2} x^{2} + \dots$

The sequence

c_n

$c_{n}$ The generating function of :

(

)

⋯

C(x) = c_0 + c_1x + c_2x^2 + \cdots

$C (x) = c_{0} + c_{1} x + c_{2} x^{2} + \dots$

Dexter Two generating functions

(

)

A(x)

$A (x)$ and

(

)

B(x)

$B (x)$ Multiply :

(

⋯

)

(

⋯

)

(a_0 + a_1x + a_2x^2 + \cdots) \times ( b_0 + b_1x + b_2x^2 + \cdots )

$(a_{0} + a_{1} x + a_{2} x^{2} + \dots) \times (b_{0} + b_{1} x + b_{2} x^{2} + \dots)$

Multiply by polynomials ,

x^0

$x^{0}$ ,

$0$ Power term , Constant term , The composition methods are

$1$ Kind of , Constant terms in two generating functions , Multiply and then

a_0 b_0

$a_{0} b_{0}$ ,

x^1

$x^{1}$ ,

$1$ Power term , The composition methods are

$2$ Kind of ,

$a_1xa1x And B ( x ) B(x)B(x) Medium b 0 b_0b0 , constitute x 1 x^1x1 The first power term a 1 b 0 x a_1b_0xa1b0x ;$
$a_0a0 And B ( x ) B(x)B(x) Medium b 1 x b_1xb1x , constitute x 1 x^1x1 The first power term a 0 b 1 x a_0b_1xa0b1x ;$

x^1

$x^{1}$ ,

$1$ The coefficient of the power term is

a_1b_0 + a_0b_1

$a_{1} b_{0} + a_{0} b_{1}$ , complete

$1$ The power term is

(

)

(a_1b_0 + a_0b_1)x

$(a_{1} b_{0} + a_{0} b_{1}) x$

x^2

$x^{2}$ ,

$2$ Power term , The composition methods are

$3$ Kind of ,

$a_0a0 And B ( x ) B(x)B(x) Medium b 2 x 2 b_2x^2b2x2 , constitute x 2 x^2x2 , 2 22 Power term a 0 b 2 x 2 a_0b_2x^2a0b2x2 ;$
$a_2x^2a2x2 And B ( x ) B(x)B(x) Medium b 0 b_0b0 , constitute x 2 x^2x2 , 2 22 Power term a 2 b 0 x 2 a_2b_0x^2a2b0x2 ;$
$a_1xa1x And B ( x ) B(x)B(x) Medium b 1 x b_1xb1x , constitute x 2 x^2x2 , 2 22 Power term a 1 b 1 x 2 a_1b_1x^2a1b1x2 ;$