[combinatorics] generating function (example of generating function | calculating generating function with given general term formula | calculating general term formula with given 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 )
• 【 Combinatorial mathematics 】 Generating function ( Commutative properties | Derivative property | Integral properties )
• 【 Combinatorial mathematics 】 Generating function ( Summary of nature | Important generating functions ) *

In sequence General formula Namely Series

One 、 Find the generating function for a given order

---

seek

b

n

=

7

⋅

3

n

b_n = 7\cdot 3^n

bn​=7⋅3n The generating function of ;

The known sequence is

1

n

1^n

1n , The corresponding generating function is

{

a

n

}

\{a_n\}

{ an​} ,

a

n

=

1

n

a_n = 1^n

an​=1n ;

A

(

x

)

=

∑

n

=

0

∞

x

n

=

1

1

−

x

\begin{aligned} A(x) = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x} \end{aligned}

A(x)=n=0∑∞​xn=1−x1​​

First, according to The sequence General term representation , Write the sum of the series :

G

(

x

)

=

7

×

3

0

x

0

+

7

×

3

1

x

1

+

7

×

3

2

x

2

+

⋯

+

7

×

3

n

x

n

+

⋯

G(x) = 7 \times 3^0x^0 + 7 \times 3^1x^1 + 7 \times 3^2x^2 + \cdots + 7 \times 3^nx^n + \cdots

G(x)=7×30x0+7×31x1+7×32x2+⋯+7×3nxn+⋯

Extract constants to the outside :

G

(

x

)

=

7

(

3

0

x

0

+

3

1

x

1

+

3

2

x

2

+

⋯

+

3

n

x

n

+

⋯
 

)

G(x) = 7 ( 3^0x^0 + 3^1x^1 + 3^2x^2 + \cdots + 3^nx^n + \cdots )

G(x)=7(30x0+31x1+32x2+⋯+3nxn+⋯)

Write it in the combined form :

G

(

x

)

=

7

∑

n

=

0

∞

3

n

x

n

G(x) = 7 \sum\limits_{n=0}^\infty 3^nx^n

G(x)=7n=0∑∞​3nxn

According to the commutation property of the generating function : Through exchange , take

3

x

3x

3x As an item :

G

(

x

)

=

7

∑

n

=

0

∞

(

3

x

)

n

G(x) = 7 \sum\limits_{n=0}^\infty (3x)^n

G(x)=7n=0∑∞​(3x)n

according to Common generating functions

A

(

x

)

=

∑

n

=

0

∞

x

n

=

1

1

−

x

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

A(x)=n=0∑∞​xn=1−x1​

We can draw :

∑

n

=

0

∞

(

3

x

)

n

=

1

1

−

3

x

\sum\limits_{n=0}^\infty (3x)^n =\cfrac{1}{1-3x}

n=0∑∞​(3x)n=1−3x1​

According to the linear properties of the generating function , Multiplicative property :

b

n

=

α

a

n

b_n = \alpha a_n

bn​=αan​ , be

B

(

x

)

=

α

A

(

x

)

B(x) = \alpha A(x)

B(x)=αA(x)

We can get the final generating function

G

(

x

)

=

7

∑

n

=

0

∞

(

3

x

)

n

=

7

1

−

3

x

G(x) = 7 \sum\limits_{n=0}^\infty (3x)^n = \cfrac{7}{1-3x}

G(x)=7n=0∑∞​(3x)n=1−3x7​

Two 、 Calculate the series given the generating function

---

Given sequence

{

b

n

}

\{b_n\}

{ bn​} The generating function of

G

(

x

)

=

2

1

−

3

x

+

2

x

2

G(x) = \cfrac{2}{1-3x + 2x^2}

G(x)=1−3x+2x22​ , seek

{

b

n

}

\{b_n\}

{ bn​}

First the Generating function Turn into Other Generating function The sum of the ;

G

(

x

)

=

2

1

−

3

x

+

2

x

2

G(x) = \cfrac{2}{1-3x + 2x^2}

G(x)=1−3x+2x22​

take

1

−

3

x

+

2

x

2

1-3x + 2x^2

1−3x+2x2 Factoring factors , Decompose into

(

1

−

x

)

(

1

−

2

x

)

(1-x)(1-2x)

(1−x)(1−2x)

Turn it into And in the following form , molecular

A

,

B

A,B

A,B Is a undetermined constant ;

G

(

x

)

=

2

1

−

3

x

+

2

x

2

=

A

1

−

x

+

B

1

−

2

x

G(x) = \cfrac{2}{1-3x + 2x^2} = \cfrac{A}{1-x} + \cfrac{B}{1-2x}

G(x)=1−3x+2x22​=1−xA​+1−2xB​

Divide the above formula into two parts , Express into

A

,

B

A, B

A,B The fraction of :

G

(

x

)

=

A

1

−

x

+

B

1

−

2

x

=

A

(

1

−

2

x

)

+

B

(

1

−

x

)

(

1

−

x

)

(

1

−

2

x

)

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

G(x)=1−xA​+1−2xB​=(1−x)(1−2x)A(1−2x)+B(1−x)​

          

=

A

−

2

A

x

+

B

−

B

x

(

1

−

x

)

(

1

−

2

x

)

\ \ \ \ \ \ \ \ \ \ = \cfrac{A-2Ax + B- Bx}{(1-x)(1-2x)}

          =(1−x)(1−2x)A−2Ax+B−Bx​

          

=

(

A

+

B

)

−

(

2

A

+

B

)

x

(

1

−

x

)

(

1

−

2

x

)

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

          =(1−x)(1−2x)(A+B)−(2A+B)x​

          

=

(

A

+

B

)

−

(

2

A

+

B

)

x

1

−

3

x

+

2

x

2

\ \ \ \ \ \ \ \ \ \ = \cfrac{(A + B) - (2A + B ) x}{1-3x + 2x^2}

          =1−3x+2x2(A+B)−(2A+B)x​

And

G

(

x

)

=

2

1

−

3

x

+

2

x

2

G(x) = \cfrac{2}{1-3x + 2x^2}

G(x)=1−3x+2x22​ Molecular

x

x

x term And Constant term contrast :

x

x

x The first power term is

0

0

0 , namely

2

A

+

B

=

0

2A + B = 0

2A+B=0

The constant term is

2

2

2 , namely

A

+

B

=

2

A + B = 2

A+B=2

Get the equations :

{

A

+

B

=

2

2

A

+

B

=

0

\begin{cases} A + B = 2 \\\\ 2A + B = 0 \end{cases}

⎩⎪⎨⎪⎧​A+B=22A+B=0​

Solve the above equations , Get the results :

{

A

=

−

2

B

=

4

\begin{cases} A = -2 \\\\ B = 4 \end{cases}

⎩⎪⎨⎪⎧​A=−2B=4​

Then the generating function is finally decomposed into :

G

(

x

)

=

2

1

−

3

x

+

2

x

2

=

−

2

1

−

x

+

4

1

−

2

x

G(x) = \cfrac{2}{1-3x + 2x^2} = \cfrac{-2}{1-x} + \cfrac{4}{1-2x}

G(x)=1−3x+2x22​=1−x−2​+1−2x4​

Use linear properties :

−

2

1

−

x

\cfrac{-2}{1-x}

1−x−2​ The corresponding series is :

∑

n

=

0

∞

(

−

2

)

x

n

\sum\limits_{n=0}^\infty(-2)x^n

n=0∑∞​(−2)xn , The general term of the sequence is

c

n

=

−

2

c_n=-2

cn​=−2 ;

Use linear properties , Commutative properties :

4

1

−

2

x

\cfrac{4}{1-2x}

1−2x4​ The corresponding series is :

∑

n

=

0

∞

4

(

2

x

)

n

=

∑

n

=

0

∞

4

⋅

2

n

x

n

\sum\limits_{n=0}^\infty4(2x)^n=\sum\limits_{n=0}^\infty4\cdot 2^nx^n

n=0∑∞​4(2x)n=n=0∑∞​4⋅2nxn , The general term of the sequence is

4

⋅

2

n

4\cdot 2^n

4⋅2n

The final sequence is :

b

n

=

−

2

+

4

⋅

2

n

b_n = -2 + 4\cdot 2^n

bn​=−2+4⋅2n