Properties of generating functions

(1)

CS 207m: Discrete Structures (Minor)

Lecture 11 – Counting and Combinatorics

Generating functions and Principle of Inclusion-Exclusion

Feb 16 2018

(2)

Last few classes

Basic counting techniques and applications

1. Sum and product, bijection, double counting principles 2. Binomial coefficients and binomial theorem, Pascal’s

triangle

3. Permutations and combinations with/without repetitions 4. Counting subsets, relations, Handshake lemma

5. Stirling’s approximation: Estimating n!

6. Recurrence relations and one method to solve them.

7. Solving recurrence relations via generating functions.

(3)

Properties of generating functions

Definition

The(ordinary) generating function for a sequencea0, a1, . . .∈R is the infinite seriesφ(x) =P∞

k=0a_kx^k.

I Let f(x) =P∞

k=0a_kx^k,g(x) =P∞

k=0b_kx^k. Then 1. Iff(x) =g(x), thenak=bk for allk.

2. f(x) +g(x) =P∞

k=0(ak+bk)x^k, 3. f(x)g(x) =P∞

k=0(Pk

j=0ajbk−j)x^k, 4. _dx^d (P∞

k=0akx^k) =P∞

k=1(kak)x^k−1

I Let u∈R,k∈Z^≥0, Thenextended binomial coefficient ^u_k is defined as ^u_k

= u(u−1)...(u−k+1)

k! ifk >0 and = 1 ifk= 0.

I What if u=−nforn∈N?

The extended binomial theorem Letu∈R, (1 +x)^u =P∞

k=0 u k

x^k. If you don’t like this, takex∈R,|x|<1.

(4)

Properties of generating functions

Definition

k=0a_kx^k.

I Let f(x) =P∞

2. f(x) +g(x) =P∞

k=0(Pk

k=0akx^k) =P∞

k=1(kak)x^k−1

= u(u−1)...(u−k+1)

k=0 u k

x^k. If you don’t like this, takex∈R,|x|<1.

(5)

Properties of generating functions

Definition

k=0a_kx^k.

I Let f(x) =P∞

2. f(x) +g(x) =P∞

k=0(Pk

k=0akx^k) =P∞

k=1(kak)x^k−1

= u(u−1)...(u−k+1)

k=0 u k

x^k.

If you don’t like this, takex∈R,|x|<1.

(6)

Properties of generating functions

Definition

k=0a_kx^k.

I Let f(x) =P∞

2. f(x) +g(x) =P∞

k=0(Pk

k=0akx^k) =P∞

k=1(kak)x^k−1

= u(u−1)...(u−k+1)

I What if u=−nforn∈N? The extended binomial theorem

(7)

Simple examples using generating functions

Standard identities:

I 1

1−ax =P∞ k=0a^kx^k

I 1

1−x^r =P∞ k=0x^rk

I e^x=P∞ k=0x^k

k!

(8)

Solving Catalan numbers using generating functions

Catalan Numbers C(n) =

n−1

X

i=1

C(i)C(n−i) for n >1,C(0) = 0, C(1) = 1.

(9)

Solving Catalan numbers using generating functions

n−1

X

i=1

C(i)C(n−i) for n >1,C(0) = 0, C(1) = 1.

I Let φ(x) =P∞

k=1C(k)x^k.

(10)

Solving Catalan numbers using generating functions

n−1

X

i=1

C(i)C(n−i) for n >1,C(0) = 0, C(1) = 1.

I Let φ(x) =P∞

k=1C(k)x^k.

I Now considerφ(x)².

I φ(x)² = (P∞

k=1C(k)x^k)(P∞

k=1C(k)x^k)

= (P∞ k=2

Pk−1

i=1 C(i)C(k−i)x^k)

= (P∞

k=2C(k)x^k) =φ(x)−x

(11)

Solving Catalan numbers using generating functions

n−1

X

i=1

C(i)C(n−i) for n >1,C(0) = 0, C(1) = 1.

I Let φ(x) =P∞

k=1C(k)x^k.

I Now considerφ(x)².

I φ(x)² = (P∞

k=1C(k)x^k)(P∞

k=1C(k)x^k)

= (P∞ k=2

Pk−1

i=1 C(i)C(k−i)x^k)

= (P∞

k=2C(k)x^k) =φ(x)−x

I Solving for φ(x) we get, φ(x) = ¹₂(1±(1−4x)^1/2)

I But since φ(0) = 0, we have

φ(x) = ¹₂(1−(1−4x)^1/2) = ¹₂+ (−¹₂(1−4x)^1/2).

(12)

Catalan numbers

Recall: Extended binomial theorem Letα∈R,(1 +x)^α=P∞

n=0 α n

xⁿ, where ^α_n

= α(α−1)...(α−n+1)

n! .

(13)

Catalan numbers

n=0 α n

xⁿ, where ^α_n

= α(α−1)...(α−n+1)

n! .

I P∞

k=1C(k)x^k=φ(x) = ¹₂ + (−¹₂(1−4x)^1/2) =

1

2 + (−¹₂P∞ k=0

1/2 k

(−4x)^k).

(14)

Catalan numbers

n=0 α n

xⁿ, where ^α_n

= α(α−1)...(α−n+1)

n! .

I P∞

k=1C(k)x^k=φ(x) = ¹₂ + (−¹₂(1−4x)^1/2) =

1

2 + (−¹₂P∞ k=0

1/2 k

(−4x)^k).

I The coefficient of x^k is C(k) =−¹₂ ^1/2_k (−4)^k

=−¹₂(¹₂(¹₂−1)(¹₂ −2). . .(¹₂ −k+ 1))⁽⁻⁴⁾_k!^k

=−¹₂(¹₂)(−³₂)(−⁵₂). . .(−^2k−3₂ ))⁽⁻⁴⁾_k!^k

(15)

Catalan numbers

n=0 α n

xⁿ, where ^α_n

= α(α−1)...(α−n+1)

n! .

I P∞

k=1C(k)x^k=φ(x) = ¹₂ + (−¹₂(1−4x)^1/2) =

1

2 + (−¹₂P∞ k=0

1/2 k

(−4x)^k).

=−¹₂(¹₂(¹₂−1)(¹₂ −2). . .(¹₂ −k+ 1))⁽⁻⁴⁾_k!^k

=−¹₂(¹₂)(−³₂)(−⁵₂). . .(−^2k−3₂ ))⁽⁻⁴⁾_k!^k

I C(k) =⁽⁻¹⁾₂_k+1^k⁽⁻⁴⁾_k! ^k ·1·3· · ·(2k−3)

(16)

Catalan numbers

n=0 α n

xⁿ, where ^α_n

= α(α−1)...(α−n+1)

n! .

I P∞

k=1C(k)x^k=φ(x) = ¹₂ + (−¹₂(1−4x)^1/2) =

1

2 + (−¹₂P∞ k=0

1/2 k

(−4x)^k).

=−¹₂(¹₂(¹₂−1)(¹₂ −2). . .(¹₂ −k+ 1))⁽⁻⁴⁾_k!^k

=−¹₂(¹₂)(−³₂)(−⁵₂). . .(−^2k−3₂ ))⁽⁻⁴⁾_k!^k

I C(k) =⁽⁻¹⁾₂_k+1^k⁽⁻⁴⁾_k! ^k ·1·3· · ·(2k−3)

I C(k) =₂k+1^1·4^k·k!·1.2....(2k−3)(2k−2)

2^k−1(k−1)! = _k!(k−1)!^(2k−2)!.

(17)

Catalan numbers

n=0 α n

xⁿ, where ^α_n

= α(α−1)...(α−n+1)

n! .

I P∞

k=1C(k)x^k=φ(x) = ¹₂ + (−¹₂(1−4x)^1/2) =

1

2 + (−¹₂P∞ k=0

1/2 k

(−4x)^k).

=−¹₂(¹₂(¹₂−1)(¹₂ −2). . .(¹₂ −k+ 1))⁽⁻⁴⁾_k!^k

=−¹₂(¹₂)(−³₂)(−⁵₂). . .(−^2k−3₂ ))⁽⁻⁴⁾_k!^k

I C(k) =⁽⁻¹⁾₂_k+1^k⁽⁻⁴⁾_k! ^k ·1·3· · ·(2k−3)

I C(k) =₂_k+1^1·4^k_·k!·1.2....(2k−3)(2k−2)

2^k−1(k−1)! = _k!(k−1)!^(2k−2)!. Thus, then^th Catalan number is given by C(n) = _n!(n−1)!^(2n−2)! = ¹_n ²ⁿ⁻²_n−1

(18)

Other applications of generating functions

I What is the number of ways a_k of selecting kelements from an nelement set if repetitions are allowed?

I Letφ(x) =P∞ k=0akx^k.

I Observe thatφ(x) = (1 +x+x²+. . .)ⁿ= (1−x)⁻ⁿ

I Expand this by the extended binomial theorem and compare coefficients ofx^k.

I a_k= ⁻ⁿ_k

(−1)^k = (−1)^{k n+k−1}_k

(−1)^k= ^n+k−1_k .

I (H.W)What if there must be ≥1 element of each type?

I Proving binomial identities: Show thatPn k=0

n k

2

= ²ⁿ_n .

I Compare coefficients ofxⁿ in (1 +x)²ⁿ= ((1 +x)ⁿ)².

(19)

Other applications of generating functions

I a_k= ⁻ⁿ_k

(−1)^k = (−1)^{k n+k−1}_k

(−1)^k= ^n+k−1_k .

n k

2

= ²ⁿ_n .

(20)

Other applications of generating functions

I a_k= ⁻ⁿ_k

(−1)^k = (−1)^{k n+k−1}_k

(−1)^k= ^n+k−1_k .

n k

2

= ²ⁿ_n .

(21)

Other applications of generating functions

I a_k= ⁻ⁿ_k

(−1)^k = (−1)^{k n+k−1}_k

(−1)^k= ^n+k−1_k .

n k

2

= ²ⁿ_n .

(22)

Other applications of generating functions

I a_k= ⁻ⁿ_k

(−1)^k = (−1)^{k n+k−1}_k

(−1)^k= ^n+k−1_k .

n k

2

= ²ⁿ_n .

(23)

Other applications of generating functions

I a_k= ⁻ⁿ_k

(−1)^k = (−1)^{k n+k−1}_k

(−1)^k= ^n+k−1_k .

n k

2

= ²ⁿ_n .

(24)

Other applications of generating functions

I a_k= ⁻ⁿ_k

(−1)^k = (−1)^{k n+k−1}_k

(−1)^k= ^n+k−1_k .

n k

2

= ²ⁿ_n .

(25)

Other applications of generating functions

I a_k= ⁻ⁿ_k

(−1)^k = (−1)^{k n+k−1}_k

(−1)^k= ^n+k−1_k .

n k

2

= ²ⁿ_n .

(26)

Applications of generating functions

Solving recurrence relations

I Number of subsets of a set of size n,

I Fibonacci sequence,

I Catalan numbers: C(n) = _n!(n−1)!^(2n−2)! = _n¹ ²ⁿ⁻²_n−1

Some more practice problems:

1. (H.W) How many ways can a convex n-sided polygon be cut into triangles by adding non-intersecting diagonals (i.e., connecting vertices with non-crossing lines)? Write a recurrence and solve it!

2. (H.W) Write a recurrence for the number of derrangements. That is, no. of ways to arrange nletters inton addressed envelopes such that no letter goes to the correct envelope.

(27)

Applications of generating functions

2. (H.W) Write a recurrence for the number of derrangements. That is, no. of ways to arrange nletters inton addressed envelopes such that no letter goes to the correct envelope.

(28)

Applications of generating functions

2. (H.W) Write a recurrence for the number of derrangements.

That is, no. of ways to arrange nletters inton addressed envelopes such that no letter goes to the correct envelope.

(29)

Principle of Inclusion-Exclusion (PIE)

A simple example:

I If in a class nstudents like physics,m students like biology and k students who like both, and` like neither, then how many students are there in the class?

I Of course, this also counts the no. who were too lazy to lift their hands!

Theorem: Principle of Inclusion-Exclusion (PIE) LetA1, A2, . . . , Anbe finite sets. Then,

|A₁∪. . .∪A_n|= X

1≤i≤n

|A_i| − X

1≤i<j≤n

|A_i∩A_j|

+ X

1≤i<j<k≤n

|A_i∩Aj ∩A_k| −. . .+ (−1)ⁿ⁺¹|A₁∩. . .∩An|

(30)

Principle of Inclusion-Exclusion (PIE)

A simple example:

Theorem: Principle of Inclusion-Exclusion (PIE) LetA1, A2, . . . , Anbe finite sets. Then,

|A₁∪. . .∪A_n|= X

1≤i≤n

|A_i| − X

1≤i<j≤n

|A_i∩A_j|

+ X

1≤i<j<k≤n

|A_i∩Aj ∩A_k| −. . .+ (−1)ⁿ⁺¹|A₁∩. . .∩An|

(31)

Principle of Inclusion-Exclusion (PIE)

A simple example:

Theorem: Principle of Inclusion-Exclusion (PIE) LetA1, A2, . . . , An be finite sets. Then,

|A₁∪. . .∪A_n|= X

1≤i≤n

|A_i| − X

1≤i<j≤n

|A_i∩A_j|

+ X

1≤i<j<k≤n

|A_i∩Aj ∩A_k| −. . .+ (−1)ⁿ⁺¹|A₁∩. . .∩An|

(32)

Number of surjections

I How many surjections are there from [n] ={1, . . . , n}to [m] ={1, . . . , m}?

(33)

Number of surjections

I # surjections = total #functions - those that miss some element in range.

(34)

Number of surjections

I Let A_i={f : [n]→[m]|i6∈Range(f)}

I Then, # surjections =mⁿ− | ∪_i∈[m]A_i|.

(35)

Number of surjections

Theorem: Principle of Inclusion-Exclusion (PIE) LetA₁, A₂, . . . , A_n be finite sets. Then,

|A₁∪. . .∪A_n|= X

1≤i≤n

|A_i| − X

1≤i<j≤n

|A_i∩A_j|

+ X

1≤i<j<k≤n

|A_i∩A_j ∩A_k| −. . .+ (−1)ⁿ⁺¹|A₁∩. . .∩A_n|

(36)

Number of surjections

I | ∪_i∈[m]Ai|=P

1≤i≤m|A_i| −P

1≤i<j≤m|A_i∩Aj|+ P

1≤i<j<k≤m|A_i∩Aj∩A_k| −. . .+ (−1)^m+1|A₁∩. . .∩Am|

(37)

Number of surjections

I | ∪_i∈[m]Ai|=P

1≤i≤m|A_i| −P

1≤i<j<k≤m|A_i∩Aj∩A_k| −. . .+ (−1)^m+1|A₁∩. . .∩Am|

I But now what is |A_i|,|A_i∩Aj|,|A_i∩Aj∩Ak|, . . .?

(38)

Number of surjections

I | ∪_i∈[m]Ai|=P

1≤i≤m|A_i| −P

1≤i<j<k≤m|A_i∩Aj∩A_k| −. . .+ (−1)^m+1|A₁∩. . .∩Am|

I |A_i|= (m−1)ⁿ,|A_i∩A_j|= (m−2)ⁿ...

(39)

Number of surjections

I | ∪_i∈[m]Ai|=P

1≤i≤m|A_i| −P

1≤i<j<k≤m|A_i∩Aj∩A_k| −. . .+ (−1)^m+1|A₁∩. . .∩Am|

I |A_i|= (m−1)ⁿ,|A_i∩A_j|= (m−2)ⁿ...

I What about the summation? terms 1≤i < j ≤m=

(40)

Number of surjections

I Let Ai={f : [n]→[m]|i6∈Range(f)}

I | ∪_i∈[m]Ai|=P

1≤i≤m|A_i| −P

1≤i<j<k≤m|A_i∩A_j∩A_k| −. . .+ (−1)^m+1|A₁∩. . .∩A_m|

I |A_i|= (m−1)ⁿ,|A_i∩A_j|= (m−2)ⁿ...

I What about the summation? terms 1≤i < j ≤m= ^m₂

(41)

Proof of PIE

|A₁∪. . .∪An|= X

1≤i≤n

|A_i| − X

1≤i<j≤n

|A_i∩Aj|

+ X

1≤i<j<k≤n

|A_i∩Aj ∩Ak| −. . .+ (−1)ⁿ⁺¹|A₁∩. . .∩An|

Proof: (H.W): Prove PIE by induction.

I We will show that each element in the union is counted exactly once in the r.h.s

I Let abelong to exactlyr of the setsA1, . . . , An.

I Then ais counted ₁^r

times byP

|A_i|, etc.

I Thus, overall count = ^r₁

− ^r₂

+. . .(−1)^r+1 ^r_r .

I What is this number?! =1!

(42)

Proof of PIE

|A₁∪. . .∪An|= X

1≤i≤n

|A_i| − X

1≤i<j≤n

|A_i∩Aj|

+ X

1≤i<j<k≤n

|A_i∩Aj ∩Ak| −. . .+ (−1)ⁿ⁺¹|A₁∩. . .∩An|

Proof:

I Let abelong to exactlyr of the setsA1, . . . , An.

times byP

|A_i|, etc.

− ^r₂

+. . .(−1)^r+1 ^r_r .

(43)

Proof of PIE

|A₁∪. . .∪An|= X

1≤i≤n

|A_i| − X

1≤i<j≤n

|A_i∩Aj|

+ X

1≤i<j<k≤n

|A_i∩Aj ∩Ak| −. . .+ (−1)ⁿ⁺¹|A₁∩. . .∩An|

Proof:

I Let abelong to exactlyr of the setsA₁, . . . , A_n.

times byP

|A_i|, etc.

− ^r₂

+. . .(−1)^r+1 ^r_r .

(44)

Proof of PIE

|A₁∪. . .∪An|= X

1≤i≤n

|A_i| − X

1≤i<j≤n

|A_i∩Aj|

+ X

1≤i<j<k≤n

|A_i∩Aj ∩Ak| −. . .+ (−1)ⁿ⁺¹|A₁∩. . .∩An|

Proof:

times byP

|A_i|, etc.

− ^r₂

+. . .(−1)^r+1 ^r_r .

(45)

Proof of PIE

|A₁∪. . .∪An|= X

1≤i≤n

|A_i| − X

1≤i<j≤n

|A_i∩Aj|

+ X

1≤i<j<k≤n

|A_i∩Aj ∩Ak| −. . .+ (−1)ⁿ⁺¹|A₁∩. . .∩An|

Proof:

times byP

|A_i|, etc.

− ^r₂

+. . .(−1)^r+1 ^r_r .

(46)

Proof of PIE

|A₁∪. . .∪An|= X

1≤i≤n

|A_i| − X

1≤i<j≤n

|A_i∩Aj|

+ X

1≤i<j<k≤n

|A_i∩Aj ∩Ak| −. . .+ (−1)ⁿ⁺¹|A₁∩. . .∩An|

Proof:

times byP

|A_i|, etc.

=1!

(47)

Proof of PIE

|A₁∪. . .∪An|= X

1≤i≤n

|A_i| − X

1≤i<j≤n

|A_i∩Aj|

+ X

1≤i<j<k≤n

|A_i∩Aj ∩Ak| −. . .+ (−1)ⁿ⁺¹|A₁∩. . .∩An|

Proof:

times byP

|A_i|, etc.

− ^r₂

+. . .(−1)^r+1 ^r_r .

(48)

Applications of PIE

I How many integral solutions does x₁+x₂+x₃ = 11 have where 0≤x1 ≤3,0≤x2≤4,0≤x3 ≤6?

I Number of derangements of a set with nelements

I That is, no. of ways to arrange n letters into n addressed envelopes such that no letter goes to the correct envelope.

(49)

Number of derangements

Formally, aderangement is a permutation of objects that leaves no object in its original position.

Theorem

LetDn denote the number of derangements of [n].

D_n=n!

n

X

i=0

(−1)ⁱ i!

I D_n = (total # permutations of [n]) - (# permutations of [n] that fix at least 1 element)

I Apply PIE on latter term, lets call itP, let P(i, j) denote permutations which fixi, j and so on.

I P = X

1≤i≤n

P(i)− X

1≤i<j≤n

P(i, j) +. . .+ (−1)ⁿP(1, . . . , n).

I But P(i) = (n−1)!,P(i, j) = (n−2)!, . . .

I P = n

1

(n−1)!− n

2

(n−2)!. . .+ (−1)ⁿ⁺¹ n

n

(n−n)!

I Thus,Dn=n!(1−_1!¹ +_2!¹ . . .+ (−1)ⁿ_n!¹)

(50)

Number of derangements

Formally, aderangement is a permutation of objects that leaves no object in its original position.

Theorem

LetDn denote the number of derangements of [n].

D_n=n!

n

X

i=0

(−1)ⁱ i!

I P = X

1≤i≤n

P(i)− X

1≤i<j≤n

P(i, j) +. . .+ (−1)ⁿP(1, . . . , n).

I But P(i) = (n−1)!,P(i, j) = (n−2)!, . . .

I P = n

1

(n−1)!− n

2

(n−2)!. . .+ (−1)ⁿ⁺¹ n

n

(n−n)!

I Thus,Dn=n!(1−_1!¹ +_2!¹ . . .+ (−1)ⁿ_n!¹)

(51)

Number of derangements

Theorem

LetD_n denote the number of derangements of [n].

D_n=n!

n

X

i=0

(−1)ⁱ i!

I P = X

1≤i≤n

P(i)− X

1≤i<j≤n

P(i, j) +. . .+ (−1)ⁿP(1, . . . , n).

I But P(i) = (n−1)!,P(i, j) = (n−2)!, . . .

I P = n

1

(n−1)!− n

2

(n−2)!. . .+ (−1)ⁿ⁺¹ n

n

(n−n)!

I Thus,D_n=n!(1−_1!¹ +_2!¹ . . .+ (−1)ⁿ_n!¹)

(52)

Number of derangements

Theorem

D_n=n!

n

X

i=0

(−1)ⁱ i!

I P = X

1≤i≤n

P(i)− X

1≤i<j≤n

P(i, j) +. . .+ (−1)ⁿP(1, . . . , n).

I But P(i) = (n−1)!,P(i, j) = (n−2)!, . . .

I P = n

1

(n−1)!− n

2

(n−2)!. . .+ (−1)ⁿ⁺¹ n

n

(n−n)!

I Thus,D_n=n!(1−_1!¹ +_2!¹ . . .+ (−1)ⁿ_n!¹)

(53)

Number of derangements

Theorem

D_n=n!

n

X

i=0

(−1)ⁱ i!

I P = X

1≤i≤n

P(i)− X

1≤i<j≤n

P(i, j) +. . .+ (−1)ⁿP(1, . . . , n).

I But P(i) = (n−1)!,P(i, j) = (n−2)!, . . .

I P = n

1

(n−1)!− n

2

(n−2)!. . .+ (−1)ⁿ⁺¹ n

n

(n−n)!

I Thus,D_n=n!(1−_1!¹ +_2!¹ . . .+ (−1)ⁿ_n!¹)

(54)

Number of derangements

Theorem

D_n=n!

n

X

i=0

(−1)ⁱ i!

I P = X

1≤i≤n

P(i)− X

1≤i<j≤n

P(i, j) +. . .+ (−1)ⁿP(1, . . . , n).

I But P(i) = (n−1)!,P(i, j) = (n−2)!, . . .

I P = n

1

(n−1)!− n

2

(n−2)!. . .+ (−1)ⁿ⁺¹ n

n

(n−n)!

I Thus,D_n=n!(1−_1!¹ +_2!¹ . . .+ (−1)ⁿ_n!¹)

(55)

Number of derangements

Theorem

D_n=n!

n

X

i=0

(−1)ⁱ i!

I P = X

1≤i≤n

P(i)− X

1≤i<j≤n

P(i, j) +. . .+ (−1)ⁿP(1, . . . , n).

I But P(i) = (n−1)!,P(i, j) = (n−2)!, . . .

I P = n

1

(n−1)!− n

2

(n−2)!. . .+ (−1)ⁿ⁺¹ n

n

(n−n)!

I Thus,D_n=n!(1−_1!¹ +_2!¹ . . .+ (−1)ⁿ_n!¹)