[combinatorics] generating function (property summary | important 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 )

One 、 Summary of generated function properties

---

1 . Generating function Linear properties :

Multiplication :

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)

Add :

c

n

=

a

n

+

b

n

c_n = a_n + b_n

cn​=an​+bn​ , be

C

(

x

)

=

A

(

x

)

+

B

(

x

)

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

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

2 . Shift property of generating function :

To shift backward :

b

(

n

)

=

{

0

,

n

<

l

a

n

−

l

,

n

≥

l

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

b(n)=⎩⎪⎨⎪⎧​0,an−l​,​n<ln≥l​ , be

B

(

x

)

=

x

l

A

(

x

)

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

B(x)=xlA(x)

Forward shift :

b

n

=

a

n

+

1

b_n = a_{n+1}

bn​=an+1​ , be

B

(

x

)

=

A

(

x

)

−

∑

n

=

0

l

−

1

a

n

x

n

x

l

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

B(x)=xlA(x)−n=0∑l−1​an​xn​

3 . Generating function Product properties :

c

n

=

∑

i

=

0

n

a

i

b

n

−

i

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

cn​=i=0∑n​ai​bn−i​ , Then there are

C

(

x

)

=

A

(

x

)

⋅

B

(

x

)

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

C(x)=A(x)⋅B(x)

Summation property of generating function :

Sum forward :

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)​

Backward summation :

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)​

4 . The commutative property of generating function :

b

n

=

α

n

a

n

b_n = \alpha^n a_n

bn​=αnan​ , be

B

(

x

)

=

A

(

α

x

)

B(x) =A( \alpha x)

B(x)=A(αx)

5 . Derivation property of generating function :

b

n

=

n

a

n

b_n = n a_n

bn​=nan​ , be

B

(

x

)

=

x

A

′

(

x

)

B(x) =xA'( x)

B(x)=xA′(x)

6 . Integral property of generating function :

b

n

=

a

n

n

+

1

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

bn​=n+1an​​ , be

B

(

x

)

=

1

x

∫

0

x

A

(

x

)

d

x

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

B(x)=x1​∫0x​A(x)dx

Two 、 Generate the correspondence between the function and the sequence

---

Given sequence

{

a

n

}

\{a_n\}

{ an​} or

a

n

a_n

an​ The recursion equation of , Find the generating function

G

(

x

)

G(x)

G(x) , We need to use the properties of series and Some important series ;

Commonly used generation function values :

1

1

1 Sequence correlation :

{

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​​

{

a

n

}

\{a_n\}

{ an​} ,

a

n

=

(

−

1

)

n

a_n = (-1)^n

an​=(−1)n ;

A

(

x

)

=

∑

n

=

0

∞

(

−

1

)

n

x

n

=

1

1

+

x

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

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

{

a

n

}

\{a_n\}

{ an​} ,

a

n

=

k

n

a_n = k^n

an​=kn ,

k

k

k As a positive integer ;

A

(

x

)

=

∑

n

=

0

∞

k

n

x

n

=

1

1

−

k

x

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

A(x)​=n=0∑∞​knxn=1−kx1​​

Binomial coefficient correlation :

{

a

n

}

\{a_n\}

{ an​} ,

a

n

=

(

m

n

)

a_n = \dbinom{m}{n}

an​=(nm​) ;

A

(

x

)

=

∑

n

=

0

∞

(

m

n

)

x

n

=

(

1

+

x

)

m

\begin{aligned} A(x) & = \sum_{n=0}^{\infty} \dbinom{m}{n} x^n = ( 1 + x ) ^m \end{aligned}

A(x)​=n=0∑∞​(nm​)xn=(1+x)m​

Combination number correlation :

{

a

n

}

\{a_n\}

{ an​} ,

a

n

=

(

m

+

n

−

1

n

)

a_n = \dbinom{m+n-1}{n}

an​=(nm+n−1​) ,

m

,

n

m,n

m,n As a positive integer ;

A

(

x

)

=

∑

n

=

0

∞

(

m

+

n

−

1

n

)

x

n

=

1

(

1

−

x

)

m

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

A(x)​=n=0∑∞​(nm+n−1​)xn=(1−x)m1​​

{

a

n

}

\{a_n\}

{ an​} ,

a

n

=

(

−

1

)

n

(

m

+

n

−

1

n

)

a_n = (-1)^n \dbinom{m+n-1}{n}

an​=(−1)n(nm+n−1​) ,

m

,

n

m,n

m,n As a positive integer ;

A

(

x

)

=

∑

n

=

0

∞

(

−

1

)

n

(

m

+

n

−

1

n

)

x

n

=

1

(

1

+

x

)

m

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

A(x)​=n=0∑∞​(−1)n(nm+n−1​)xn=(1+x)m1​​

{

a

n

}

\{a_n\}

{ an​} ,

a

n

=

(

n

+

1

n

)

a_n = \dbinom{n+1}{n}

an​=(nn+1​) ,

n

n

n As a positive integer ;

A

(

x

)

=

∑

n

=

0

∞

(

n

+

1

n

)

x

n

=

∑

n

=

0

∞

(

n

+

1

)

x

n

=

1

(

1

−

x

)

2

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

A(x)​=n=0∑∞​(nn+1​)xn=n=0∑∞​(n+1)xn=(1−x)21​​