[combinatorics] generating function (summation property)

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 )

One 、 Summation property of generating function 1 ( Sum forward )

---

Summation property of generating function 1 :

b

n

=

∑

i

=

0

n

a

i

b_n = \sum\limits_{i=0}^{n}a_i

bn​=i=0∑n​ai​ , be

B

(

x

)

=

A

(

x

)

1

−

x

B(x) = \cfrac{A(x)}{1-x}

B(x)=1−xA(x)​

The sequence

a

n

a_n

an​ The generating function of is

A

(

x

)

A(x)

A(x) , The sequence

b

n

b_n

bn​ The generating function of is

B

(

x

)

B(x)

B(x) ,

The sequence

a

n

=

{

a

0

,

a

1

,

a

2

,

⋯
 

}

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

an​={ a0​,a1​,a2​,⋯} , The sequence

b

n

=

{

b

0

,

b

1

,

b

2

,

⋯
 

}

b_n = \{ b_0 , b_1, b_2 , \cdots \}

bn​={ b0​,b1​,b2​,⋯} ;

The sequence

a

n

a_n

an​ The generating function of

A

(

x

)

=

a

0

+

a

1

x

+

a

2

x

2

+

⋯

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

A(x)=a0​+a1​x+a2​x2+⋯

The sequence

b

n

b_n

bn​ The generating function of

B

(

x

)

=

b

0

+

b

1

x

+

b

2

x

2

+

⋯

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

B(x)=b0​+b1​x+b2​x2+⋯

b

n

b_n

bn​ The second in a series

n

n

n term , be equal to

a

n

a_n

an​ The first in a sequence

n

n

n Sum of items ;

deduction

b

n

b_n

bn​ Items of sequence :

b

0

=

a

0

b_0 = a_0

b0​=a0​

b

1

=

a

0

+

a

1

b_1 = a_0 + a_1

b1​=a0​+a1​

b

2

=

a

0

+

a

1

+

a

2

b_2 = a_0 + a_1 + a_2

b2​=a0​+a1​+a2​

⋮

\vdots

⋮

b

n

=

a

0

+

a

1

+

a

2

+

⋯

+

a

n

b_n = a_0 + a_1 + a_2 + \cdots + a_n

bn​=a0​+a1​+a2​+⋯+an​

Derive the terms of the generating function :

B

(

x

)

B(x)

B(x) Medium

x

0

x^0

x0 term ( Constant term ) :

b

0

   

=

a

0

b_0 \ \ \ = a_0

b0​   =a0​

B

(

x

)

B(x)

B(x) Medium

x

1

x^1

x1 term ( Constant term ) :

b

1

x

 

=

(

a

0

+

a

1

)

x

b_1x \ = (a_0 + a_1)x

b1​x =(a0​+a1​)x

B

(

x

)

B(x)

B(x) Medium

x

2

x^2

x2 term ( Constant term ) :

b

2

x

2

=

(

a

0

+

a

1

+

a

2

)

x

2

b_2x^2 = (a_0 + a_1 + a_2)x^2

b2​x2=(a0​+a1​+a2​)x2

⋮

\vdots

⋮

B

(

x

)

B(x)

B(x) Medium

x

n

x^n

xn term ( Constant term ) :

b

n

x

n

=

(

a

0

+

a

1

+

a

2

+

⋯

+

a

n

)

x

n

b_nx^n = (a_0 + a_1 + a_2 + \cdots + a_n)x^n

bn​xn=(a0​+a1​+a2​+⋯+an​)xn

Put the above

B

(

x

)

B(x)

B(x) Add the items in : The strategy of addition is vertical addition , As shown in the figure below :

The first

1

1

1 Column addition :

a

0

+

a

0

x

+

a

0

x

2

+

⋯

+

a

0

x

n

=

a

0

1

1

−

x

a_0 + a_0 x + a_0x^2 + \cdots + a_0x^n = a_0\cfrac{1}{1-x}

a0​+a0​x+a0​x2+⋯+a0​xn=a0​1−x1​

The first

2

2

2 Column addition :

a

1

x

+

a

1

x

2

+

⋯

+

a

1

x

n

=

a

1

x

1

1

−

x

a_1 x + a_1x^2 + \cdots + a_1x^n = a_1x\cfrac{1}{1-x}

a1​x+a1​x2+⋯+a1​xn=a1​x1−x1​

⋮

\vdots

⋮

The first

n

n

n Column addition :

a

n

x

n

=

a

n

x

n

1

1

−

x

a_nx^n = a_nx^n\cfrac{1}{1-x}

an​xn=an​xn1−x1​

The resulting :

B

(

x

)

=

a

0

1

1

−

x

+

a

1

x

1

1

−

x

+

⋯

+

a

n

x

n

1

1

−

x

+

⋯

B(x) = a_0\cfrac{1}{1-x} + a_1x\cfrac{1}{1-x} + \cdots + a_nx^n\cfrac{1}{1-x} + \cdots

B(x)=a0​1−x1​+a1​x1−x1​+⋯+an​xn1−x1​+⋯

Will be one of the

1

1

−

x

\cfrac{1}{1-x}

1−x1​ extracted , You can get :

B

(

x

)

=

1

1

−

x

(

a

0

+

a

1

x

+

+

⋯

+

a

n

x

n

+

⋯
 

)

B(x) = \cfrac{1}{1-x} ( a_0 + a_1x + + \cdots + a_nx^n + \cdots )

B(x)=1−x1​(a0​+a1​x++⋯+an​xn+⋯)

B

(

x

)

=

1

1

−

x

A

(

x

)

B(x) = \cfrac{1}{1-x} A(x)

B(x)=1−x1​A(x)

Two 、 Summation property of generating function 2 ( Backward summation )

---

Summation property of generating function 2 :

b

n

=

∑

i

=

n

∞

a

i

b_n = \sum\limits_{i=n}^{\infty}a_i

bn​=i=n∑∞​ai​ , also

A

(

1

)

=

∑

i

=

n

∞

a

i

A(1) =\sum\limits_{i=n}^{\infty}a_i

A(1)=i=n∑∞​ai​ convergence , be

B

(

x

)

=

A

(

1

)

−

x

A

(

x

)

1

−

x

B(x) = \cfrac{A(1) - xA(x)}{1-x}

B(x)=1−xA(1)−xA(x)​