当前位置：网站首页>[combinatorics] generating function (commutative property | derivative property | integral property)

[combinatorics] generating function (commutative property | derivative property | integral property)

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

List of articles

One 、 The commutative property of generating function
Two 、 Derivation property of generating function
3、 ... and 、 Integral 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 )
【 Combinatorial mathematics 】 Generating function ( Linear properties | Product properties )
【 Combinatorial mathematics 】 Generating function ( Shift property )
【 Combinatorial mathematics 】 Generating function ( The nature of summation )

One 、 The commutative property of generating function

Summation property of generating function 1 :

b_n = \alpha^n a_n

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

(

)

(

)

B(x) =A( \alpha 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)$ ,

The sequence

{

⋯

}

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

$a_{n} = {a_{0}, a_{1}, a_{2}, \dots}$ , The sequence

{

⋯

}

b_n = \{ \alpha^0a_0 , \alpha^1a_1, \alpha^2a_2 , \cdots \}

$b_{n} = {α^{0} a_{0}, α^{1} a_{1}, α^{2} a_{2}, \dots}$ ;

The sequence

a_n

$a_{n}$ The generating function of

(

)

⋯

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

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

The sequence

b_n

$b_{n}$ The generating function of

(

)

⋯

B(x) = \alpha^0a_0x^0 + \alpha^1a_1x^1 + \alpha^2a_2x^2 + \cdots

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

Method of proof :

stay

b_n

$b_{n}$ The generating function of

(

)

B(x)

$B (x)$ in , take

\alpha^0x^0

$α^{0} x^{0}$ As an item , take

\alpha^1x^1

$α^{1} x^{1}$ As an item , take

\alpha^2x^2

$α^{2} x^{2}$ As an item ,

By observing the above items, we can see ,

\alpha

$α$ And

$x$ The power of is the same ,

So you can take

\alpha x

$α x$ As a variable ,

In this way, you can get

(

)

(

)

B(x) =A( \alpha x)

$B (x) = A (α x)$ The formula ;

Two 、 Derivation property of generating function

Derivation property of generating function :

b_n = n a_n

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

(

)

′

(

)

B(x) =xA'( x)

$B (x) = 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)$ ,

The sequence

{

⋯

}

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

$a_{n} = {a_{0}, a_{1}, a_{2}, \dots, a_{n}, \dots}$ , The sequence

{

⋯

}

b_n = \{ 0a_0 , a_1, 2a_2 , \cdots, na_n ,\cdots \}

$b_{n} = {0 a_{0}, a_{1}, 2 a_{2}, \dots, n a_{n}, \dots}$ ;

The sequence

a_n

$a_{n}$ The generating function of

(

)

⋯

A(x) = a_0x^0 + a_1x + a_2x^2 + \cdots + a_nx^n + \cdots

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

The sequence

b_n

$b_{n}$ The generating function of

(

)

⋯

B(x) = 0a_0x^0 + 1a_1x^1 + 2a_2x^2 + \cdots + na_nx^n + \cdots

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

Prove the above properties :

take The sequence

a_n

$a_{n}$ The generating function of

(

)

A(x)

$A (x)$ Derivation , Again multiply

$x$ , You can get

(

)

B(x)

$B (x)$ ;

(

)

⋯

A(x) = a_0x^0 + a_1x + a_2x^2 + \cdots + a_nx^n + \cdots

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

Use derivative formula :

(

)

′

−

(x^n)' = nx^{n-1}

$(x^{n})^{'} = n x^{n - 1}$

Reference resources : Derivation - Baidu Encyclopedia

′

(

)

⋯

−

⋯

A'(x) = 0 + a_1 + 2a_2x + \cdots + na_nx^{n-1} + \cdots

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

′

(

)

⋯

(

)

xA'(x) = 0 + a_1x + 2a_2x^2 + \cdots + na_nx^{n} + \cdots = B(x)

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

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

b_n = \cfrac{a_n}{n+1}

$b_{n} = \frac{a _{n}}{n + 1}$ , be

(

)

∫

(

)

B(x) =\cfrac{1}{x} \int^{x}_{0} A( x)dx

$B (x) = \frac{1}{x} \int_{0}^{x} A (x) d x$

The above properties are hard to remember , Generate functions from known , Unknown generating functions can be derived , You can deduce when using ;

原网站

版权声明
本文为[Programmer community]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/02/202202150323588467.html