CS 207 Discrete Mathematics – 2012-2013

(1)

CS 207 Discrete Mathematics – 2012-2013

Nutan Limaye

Indian Institute of Technology, Bombay nutan@cse.iitb.ac.in

Combinatorics

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 1 / 6

(2)

Last time

(3)

Recap

e(n/e)ⁿ≤n!≤ne(n/2)ⁿ

We proved (partially) the following theorem: There are nⁿ⁻² labelled trees.

Definitions:

I Doubly rooted trees

I Skeleton

I pos(x) := distance of x fromu

I ord(x,S) := order ofx in setS.

I A map, sayφ, from doubly rooted trees to

ifuon skeletonS φ(u) = j, where ord(u,S) = pos(j) ifunot on skeleton φ(u) = parent(u)

(4)

Recap

We proved (partially) the following theorem:

There are nⁿ⁻² labelled trees.

Definitions:

I Skeleton

(5)

Recap

Definitions:

I Skeleton

(6)

Recap

Definitions:

I Skeleton

I A map, sayφ, from doubly rooted trees to {f : [n]→[n]}

(7)

Recap

Definitions:

I Skeleton

I A map, sayφ, from doubly rooted trees toa set of functions from {1,2, . . . ,n} to{1,2, . . . ,n}

(8)

Recap

Definitions:

I Skeleton

I A map, sayφ, from doubly rooted trees to {f : [n]→[n]}

(9)

Recap

A map, sayφ, from doubly rooted trees to {f : [n]→[n]}

ifu on skeletonS φ(u) = j, where ord(u,S) = pos(j) ifu not on skeleton φ(u) = parent(u)

A map, sayχ, from{f : [n]→[n]} to doubly rooted trees. Given a functionf : [n]→[n] consider the graph induced by the function. It gives cycles and trees.

Let S denote the vertices on the cycle. LetT denote the nodes on the trees. Leti1 ≤i2 ≤. . .≤i_k be the elements ofS.

I Draw edges (f(ij),f(ij+1)) for 1≤j≤k−1

I Forj ∈T\(T∩S) draw edges (j,f(j))

To prove: For all doubly rooted treesT: χ(φ(T)) =T

(10)

Recap

A map, sayχ, from{f : [n]→[n]} to doubly rooted trees.

Given a functionf : [n]→[n] consider the graph induced by the function. It gives cycles and trees.

(11)

Recap

(12)

Recap

Let S denote the vertices on the cycle. LetT denote the nodes on the trees.

Leti1 ≤i2 ≤. . .≤i_k be the elements ofS.

(13)

Recap

Let S denote the vertices on the cycle. LetT denote the nodes on the trees. Note thatT ∪S\(T∩S) = [n]

Let i1≤i2 ≤. . .≤ik be the elements of S.

(14)

Recap

Let S denote the vertices on the cycle. LetT denote the nodes on the trees. Leti1 ≤i2≤. . .≤i_k be the elements ofS.

(15)

Recap

(16)

Recap

(17)

Recap

(18)

Recap

To prove: For all doubly rooted treesT: χ(φ(T)) =T Lemma ([CW])

Let A and B be two finite sets. Letφ:A→B and χ:B →A be two functions such that ∀a∈Aχ(φ(a)) =a thenφis a bijection from A to B.

(19)

Recap

(20)

Today

Solving recurrences using generating functions Counting using generating functions

(21)

Solving recurrences

Let F(n) denote the nth Fibonacci number. ComputeF(n).

We know that

∀n ≥2 :F(n) =F(n−1) +F(n−2),andF(0) = 1,F(1) = 1.

φ(t) = P∞

n=0F(n)tⁿ

tφ(t) = P∞

n=0F(n)tⁿ⁺¹ = P∞

n≥1F(n−1)tⁿ

t²φ(t) = P∞

n=0F(n)tⁿ⁺² = P∞

n≥2F(n−2)tⁿ (t+t²)φ(t) = P∞

n=0F(n)tⁿ−1 (t+t²)φ(t) = φ(t)−1

φ(t) = _1−t−t¹ 2 = (1−αt)(1−βt)¹ = _(1−αt)^a +_(1−βt)^b Solving we getα= ¹⁺

√ 5

2 ,β = ¹⁻

√ 5 2 ,a=

√ 5+1 2√

5 ,b=

√5−1 2√

5

φ(t) =a(1 +αt+α²t²+. . .) +b(1 +βt+β²t²+. . .) Equating coefficients oftⁿ we get F(n) =aαⁿ+bβⁿ

F(n) = ^√

5+1 2√

5

1+√ 5 2

n

+ ^√

5−1 2√

5

1−√ 5 2

n

(22)

Solving recurrences

We know that

∀n≥2 :F(n) =F(n−1) +F(n−2),andF(0) = 1,F(1) = 1.

φ(t) = P∞

n=0F(n)tⁿ

tφ(t) = P∞

n=0F(n)tⁿ⁺¹ = P∞

n≥1F(n−1)tⁿ

t²φ(t) = P∞

n=0F(n)tⁿ⁺² = P∞

n≥2F(n−2)tⁿ (t+t²)φ(t) = P∞

n=0F(n)tⁿ−1 (t+t²)φ(t) = φ(t)−1

√ 5

2 ,β = ¹⁻

√ 5 2 ,a=

√ 5+1 2√

5 ,b=

√5−1 2√

5

F(n) = ^√

5+1 2√

5

1+√ 5 2

n

+ ^√

5−1 2√

5

1−√ 5 2

n

(23)

Solving recurrences

We know that

∀n≥2 :F(n) =F(n−1) +F(n−2),andF(0) = 1,F(1) = 1.

φ(t) = P∞

n=0F(n)tⁿ

tφ(t) = P∞

n=0F(n)tⁿ⁺¹ = P∞

n≥1F(n−1)tⁿ

t²φ(t) = P∞

n=0F(n)tⁿ⁺² = P∞

n≥2F(n−2)tⁿ (t+t²)φ(t) = P∞

n=0F(n)tⁿ−1 (t+t²)φ(t) = φ(t)−1

√ 5

2 ,β = ¹⁻

√ 5 2 ,a=

√ 5+1 2√

5 ,b=

√5−1 2√

5

F(n) = ^√

5+1 2√

5

1+√ 5 2

n

+ ^√

5−1 2√

5

1−√ 5 2

n

(24)

Solving recurrences

We know that

∀n≥2 :F(n) =F(n−1) +F(n−2),andF(0) = 1,F(1) = 1.

φ(t) = P∞

n=0F(n)tⁿ

tφ(t) = P∞

n=0F(n)tⁿ⁺¹ = P∞

n≥1F(n−1)tⁿ

t²φ(t) = P∞

n=0F(n)tⁿ⁺² = P∞

n≥2F(n−2)tⁿ (t+t²)φ(t) = P∞

n=0F(n)tⁿ−1 (t+t²)φ(t) = φ(t)−1

√ 5

2 ,β = ¹⁻

√ 5 2 ,a=

√ 5+1 2√

5 ,b=

√5−1 2√

5

F(n) = ^√

5+1 2√

5

1+√ 5 2

n

+ ^√

5−1 2√

5

1−√ 5 2

n

(25)

Solving recurrences

We know that

∀n≥2 :F(n) =F(n−1) +F(n−2),andF(0) = 1,F(1) = 1.

φ(t) = P∞

n=0F(n)tⁿ

tφ(t) = P∞

n=0F(n)tⁿ⁺¹ = P∞

n≥1F(n−1)tⁿ

t²φ(t) = P∞

n=0F(n)tⁿ⁺² = P∞

n≥2F(n−2)tⁿ

(t+t²)φ(t) = P∞

n=0F(n)tⁿ−1 (t+t²)φ(t) = φ(t)−1

√ 5

2 ,β = ¹⁻

√ 5 2 ,a=

√ 5+1 2√

5 ,b=

√5−1 2√

5

F(n) = ^√

5+1 2√

5

1+√ 5 2

n

+ ^√

5−1 2√

5

1−√ 5 2

n

(26)

Solving recurrences

We know that

∀n≥2 :F(n) =F(n−1) +F(n−2),andF(0) = 1,F(1) = 1.

φ(t) = P∞

n=0F(n)tⁿ

tφ(t) = P∞

n=0F(n)tⁿ⁺¹ = P∞

n≥1F(n−1)tⁿ

t²φ(t) = P∞

n=0F(n)tⁿ⁺² = P∞

n≥2F(n−2)tⁿ (t+t²)φ(t) = ^P^∞n=0(F(n−1) +F(n−2))tⁿ

(t+t²)φ(t) = ^P^∞_n=0F(n)tⁿ

(t+t²)φ(t) = φ(t)

(t+t²)φ(t) = P∞

n=0F(n)tⁿ−1 (t+t²)φ(t) = φ(t)−1

√ 5

2 ,β = ¹⁻

√ 5 2 ,a=

√ 5+1 2√

5 ,b=

√5−1 2√

5

F(n) =^√

5+1 2√

5

1+√ 5 2

n

+^√

5−1 2√

5

1−√ 5 2

n

(27)

Solving recurrences

We know that

∀n≥2 :F(n) =F(n−1) +F(n−2),andF(0) = 1,F(1) = 1.

φ(t) = P∞

n=0F(n)tⁿ

tφ(t) = P∞

n=0F(n)tⁿ⁺¹ = P∞

n≥1F(n−1)tⁿ

t²φ(t) = P∞

n=0F(n)tⁿ⁺² = P∞

n≥2F(n−2)tⁿ (t+t²)φ(t) = P∞

n=0F(n)tⁿ−1 (t+t²)φ(t) = φ(t)−1

√ 5

2 ,β = ¹⁻

√ 5 2 ,a=

√ 5+1 2√

5 ,b=

√5−1 2√

5

F(n) = ^√

5+1 2√

5

1+√ 5 2

n

+ ^√

5−1 2√

5

1−√ 5 2

n

(28)

Solving recurrences

We know that

∀n≥2 :F(n) =F(n−1) +F(n−2),andF(0) = 1,F(1) = 1.

φ(t) = P∞

n=0F(n)tⁿ

tφ(t) = P∞

n=0F(n)tⁿ⁺¹ = P∞

n≥1F(n−1)tⁿ

t²φ(t) = P∞

n=0F(n)tⁿ⁺² = P∞

n≥2F(n−2)tⁿ (t+t²)φ(t) = P∞

n=0F(n)tⁿ−1 (t+t²)φ(t) = φ(t)−1

φ(t) = _1−t−t¹ 2

= (1−αt)(1−βt)¹ = _(1−αt)^a +_(1−βt)^b Solving we getα= ¹⁺

√ 5

2 ,β = ¹⁻

√ 5 2 ,a=

√ 5+1 2√

5 ,b=

√5−1 2√

5

F(n) = ^√

5+1 2√

5

1+√ 5 2

n

+ ^√

5−1 2√

5

1−√ 5 2

n

(29)

Solving recurrences

We know that

∀n≥2 :F(n) =F(n−1) +F(n−2),andF(0) = 1,F(1) = 1.

φ(t) = P∞

n=0F(n)tⁿ

tφ(t) = P∞

n=0F(n)tⁿ⁺¹ = P∞

n≥1F(n−1)tⁿ

t²φ(t) = P∞

n=0F(n)tⁿ⁺² = P∞

n≥2F(n−2)tⁿ (t+t²)φ(t) = P∞

n=0F(n)tⁿ−1 (t+t²)φ(t) = φ(t)−1

φ(t) = _1−t−t¹ 2 = (1−αt)(1−βt)¹

= _(1−αt)^a +_(1−βt)^b Solving we getα= ¹⁺

√ 5

2 ,β = ¹⁻

√ 5 2 ,a=

√ 5+1 2√

5 ,b=

√5−1 2√

5

F(n) = ^√

5+1 2√

5

1+√ 5 2

n

+ ^√

5−1 2√

5

1−√ 5 2

n

(30)

Solving recurrences

We know that

∀n≥2 :F(n) =F(n−1) +F(n−2),andF(0) = 1,F(1) = 1.

φ(t) = P∞

n=0F(n)tⁿ

tφ(t) = P∞

n=0F(n)tⁿ⁺¹ = P∞

n≥1F(n−1)tⁿ

t²φ(t) = P∞

n=0F(n)tⁿ⁺² = P∞

n≥2F(n−2)tⁿ (t+t²)φ(t) = P∞

n=0F(n)tⁿ−1 (t+t²)φ(t) = φ(t)−1

φ(t) = _1−t−t¹ 2 = (1−αt)(1−βt)¹ = _(1−αt)^a +_(1−βt)^b

Solving we getα= ¹⁺

√ 5

2 ,β = ¹⁻

√ 5 2 ,a=

√ 5+1 2√

5 ,b=

√5−1 2√

5

F(n) = ^√

5+1 2√

5

1+√ 5 2

n

+ ^√

5−1 2√

5

1−√ 5 2

n

(31)

Solving recurrences

We know that

∀n≥2 :F(n) =F(n−1) +F(n−2),andF(0) = 1,F(1) = 1.

φ(t) = P∞

n=0F(n)tⁿ

tφ(t) = P∞

n=0F(n)tⁿ⁺¹ = P∞

n≥1F(n−1)tⁿ

t²φ(t) = P∞

n=0F(n)tⁿ⁺² = P∞

n≥2F(n−2)tⁿ (t+t²)φ(t) = P∞

n=0F(n)tⁿ−1 (t+t²)φ(t) = φ(t)−1

√ 5

2 ,β = ¹⁻

√ 5 2 ,a=

√ 5+1 2√

5 ,b =

√5−1 2√

5

F(n) = ^√

5+1 2√

5

1+√ 5 2

n

+ ^√

5−1 2√

5

1−√ 5 2

n

(32)

Solving recurrences

We know that

∀n≥2 :F(n) =F(n−1) +F(n−2),andF(0) = 1,F(1) = 1.

φ(t) = P∞

n=0F(n)tⁿ

tφ(t) = P∞

n=0F(n)tⁿ⁺¹ = P∞

n≥1F(n−1)tⁿ

t²φ(t) = P∞

n=0F(n)tⁿ⁺² = P∞

n≥2F(n−2)tⁿ (t+t²)φ(t) = P∞

n=0F(n)tⁿ−1 (t+t²)φ(t) = φ(t)−1

√ 5

2 ,β = ¹⁻

√ 5 2 ,a=

√ 5+1 2√

5 ,b =

√5−1 2√

5

φ(t) =a(1 +αt+α²t²+. . .) +b(1 +βt+β²t²+. . .)

Equating coefficients oftⁿ we get F(n) =aαⁿ+bβⁿ F(n) =

^√

5+1 2√

5

1+√ 5 2

n

+ ^√

5−1 2√

5

1−√ 5 2

n

(33)

Solving recurrences

We know that

∀n≥2 :F(n) =F(n−1) +F(n−2),andF(0) = 1,F(1) = 1.

φ(t) = P∞

n=0F(n)tⁿ

tφ(t) = P∞

n=0F(n)tⁿ⁺¹ = P∞

n≥1F(n−1)tⁿ

t²φ(t) = P∞

n=0F(n)tⁿ⁺² = P∞

n≥2F(n−2)tⁿ (t+t²)φ(t) = P∞

n=0F(n)tⁿ−1 (t+t²)φ(t) = φ(t)−1

√ 5

2 ,β = ¹⁻

√ 5 2 ,a=

√ 5+1 2√

5 ,b =

√5−1 2√

5

F(n) = ^√

5+1 2√

5

1+√ 5 2

n

+ ^√

5−1 2√

5

1−√ 5 2

n

(34)

Solving recurrences

We know that

∀n≥2 :F(n) =F(n−1) +F(n−2),andF(0) = 1,F(1) = 1.

φ(t) = P∞

n=0F(n)tⁿ

tφ(t) = P∞

n=0F(n)tⁿ⁺¹ = P∞

n≥1F(n−1)tⁿ

t²φ(t) = P∞

n=0F(n)tⁿ⁺² = P∞

n≥2F(n−2)tⁿ (t+t²)φ(t) = P∞

n=0F(n)tⁿ−1 (t+t²)φ(t) = φ(t)−1

√ 5

2 ,β = ¹⁻

√ 5 2 ,a=

√ 5+1 2√

5 ,b =

√5−1 2√

5

F(n) = ^√

5+1 2√

5

1+√ 5 2

n

+ ^√

5−1 2√

5

1−√ 5 2

n