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

[combinatorics] generating function (shift property)

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

List of articles

One 、 Shift property of generating function 1 ( To shift backward )
Two 、 Shift property of generating function 2 ( Forward shift )

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 )

One 、 Shift property of generating function 1 ( To shift backward )

Shift property of generating function 1 ( To shift backward ) :

(

)

{

−

≥

b(n) = \begin{cases} 0, & n < l \\\\ a_{n-l}, & n \geq l \end{cases}

$b (n) = ⎩ ⎪ ⎨ ⎪ ⎧ 0, a_{n - l}, n < l n \geq l$ , be

(

)

(

)

B(x) = x^l A(x)

$B (x) = x^{l} A (x)$

from Known sequence

a_n

$a_{n}$ Of Generating function

(

)

A(x)

$A (x)$ , seek Another series

b_n

$b_{n}$ Of Generating function

(

)

B(x)

$B (x)$ ;

Known sequence

{

⋯

}

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

$a_{n} = {a_{0}, a_{1}, \dots, a_{n}, \dots}$ , The generating function is

(

)

A(x)

$A (x)$ ;

The sequence

b_n

$b_{n}$ And

a_n

$a_{n}$ The relationship is ,

b_n

$b_{n}$ stay

a_n

$a_{n}$ Added in front of

$l$ individual

$0$ ;

The sequence

a_n

$a_{n}$ :

⋯

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ a_0, a_1 , \cdots , a_n , \cdots

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

The sequence

b_n

$b_{n}$ :

⋯

⏟

individual

\begin{matrix} \underbrace{ 0, 0, \cdots , 0 } \\ l individual 0 \end{matrix} ,

$0, 0, \dots, 0 l individual 0,$

⋯

a_0, a_1 , \cdots , a_n , \cdots

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

The sequence

b_n

$b_{n}$ The generating function of , front

$l$ The coefficients of the terms are

$0$ , So you can omit ,

The first $B (x) B(x) B (x) The generating function item of is a 0 x l a_0x^l a_{0} x^{l}, Corresponding A (x) A(x) A (x) The generating function item in is a 0 a_0 a_{0}$
$l$ term ,
The first $l + 1 l+1 B ( x ) B(x) The generating function item of is a 1 x l + 1 a_1x^{l+1} , Corresponding A ( x ) A(x) The generating function item in is a 1 x a_1x$
$l + 1$ term ,

(

)

B(x)

$B (x)$ Generating function Each of them is just The sequence

a_n

$a_{n}$ Of Generating function

(

)

A(x)

$A (x)$ Each On the basis of , multiply

x^l

$x^{l}$ that will do ;

Two 、 Shift property of generating function 2 ( Forward shift )

Shift property of generating function 2 ( Forward shift ) :

b_n = a_{n+1}

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

(

)

(

)

−

∑

−

B(x) = \cfrac{A(x) - \sum\limits_{n=0}^{l-1} a_nx^n }{x^l}

$B (x) = \frac{A ( x ) - n = 0 \sum l - 1 a _{n} x ^{n}}{x ^{l}}$

from Known sequence

a_n

$a_{n}$ Of Generating function

(

)

A(x)

$A (x)$ , seek Another series

b_n

$b_{n}$ Of Generating function

(

)

B(x)

$B (x)$ ;

Known sequence

{

⋯

}

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

$a_{n} = {a_{0}, a_{1}, \dots, a_{n}, \dots}$ , The generating function is

(

)

A(x)

$A (x)$ ;

The sequence

b_n

$b_{n}$ And

a_n

$a_{n}$ The relationship is ,

b_n

$b_{n}$ stay

a_n

$a_{n}$ It moves backwards on the basis of

$l$ position ,

b_0

$b_{0}$ And

a_l

$a_{l}$ Same value ,

b_1

$b_{1}$ And

a_{l+1}

$a_{l + 1}$ Same value ;

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \,

The sequence

a_n

$a_{n}$ :

⋯

a_0, a_1 , \cdots , a_l , a_{l+1} \cdots

$a_{0}, a_{1}, \dots, a_{l}, a_{l + 1} \dots$

The sequence

b_n

$b_{n}$ :

⋯

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ b_0 , b_1 , \cdots

$b_{0}, b_{1}, \dots$

according to

(

)

A(x)

$A (x)$ seek

(

)

B(x)

$B (x)$ :

stay

(

)

A(x)

$A (x)$ On the basis of , Before subtraction

$l$ term , namely from

$0$ To

−

l-1

$l - 1$ term ,

⋯

−

a_0 , a_1x , a_2x^2 , \cdots a_{l-1}x^{l-1}

$a_{0}, a_{1} x, a_{2} x^{2}, \dots a_{l - 1} x^{l - 1}$ , So there is

(

)

−

∑

−

A(x) - \sum\limits_{n=0}^{l-1} a_nx^n

$A (x) - n = 0 \sum l - 1 a_{n} x^{n}$ ;

(

)

A(x)

$A (x)$ Generating function Of Remaining items , Each item is better than

(

)

B(x)

$B (x)$ many

x^l

$x^{l}$ times , Divide

x^l

$x^{l}$ that will do ;

In the above

(

)

−

∑

−

A(x) - \sum\limits_{n=0}^{l-1} a_nx^n

$A (x) - n = 0 \sum l - 1 a_{n} x^{n}$ On the basis of , Divide

x^l

$x^{l}$ , obtain

(

)

(

)

−

∑

−

B(x) = \cfrac{A(x) - \sum\limits_{n=0}^{l-1} a_nx^n }{x^l}

$B (x) = \frac{A ( x ) - n = 0 \sum l - 1 a _{n} x ^{n}}{x ^{l}}$ ;

原网站

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

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

[combinatorics] generating function (shift property)

List of articles

One 、 Shift property of generating function 1 ( To shift backward )

Two 、 Shift property of generating function 2 ( Forward shift )

边栏推荐

猜你喜欢

随机推荐