• No results found

CS 207 Discrete Mathematics – 2012-2013

N/A
N/A
Protected

Academic year: 2022

Share "CS 207 Discrete Mathematics – 2012-2013"

Copied!
45
0
0

Loading.... (view fulltext now)

Full text

(1)

CS 207 Discrete Mathematics – 2012-2013

Nutan Limaye

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

Combinatorics

Lecture 9: Counting the same object in two ways August 16, 2012

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

(2)

Last time

(3)

Recap

Counting the same object in two different ways

I Basic counting

I k nk

=n n−1k−1

I n+1 k

= kn

+ k−1n

I The number of people who shake hands odd number of times is even.

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 3 / 13

(4)

Today

How large/small is n!? – approximating n! [Stirling’s approximation]

Counting the number of labelled trees – Cayley’s number.

(5)

Today

How large/small is n!? – approximating n! [Stirling’s approximation]

Counting the number of labelled trees – Cayley’s number.

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 4 / 13

(6)

Estimating n!

Easy to see thatn!≤nn

However, is this tight? Of course not!

Can we quantify how much more is nn as compared ton!?

Can we bound n! by a quantity, say Q, so that for some small enough

α, αQ ≤n!≤Q?

Theorem (Stirling’s approximation)

e(n/e)n≤n!≤ne(n/e)n, i.e. Q =e(n/e)n, andα= 1/n

(7)

Estimating n!

Easy to see thatn!≤nn

However, is this tight? Of course not!

Can we quantify how much more is nn as compared ton!?

Can we bound n! by a quantity, say Q, so that for some small enough

α, αQ ≤n!≤Q?

Theorem (Stirling’s approximation)

e(n/e)n≤n!≤ne(n/e)n, i.e. Q =e(n/e)n, andα= 1/n

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 5 / 13

(8)

Estimating n!

Easy to see thatn!≤nn

However, is this tight? Of course not!

Can we quantify how much more is nn as compared ton!?

Can we bound n! by a quantity, say Q, so that for some small enough

α, αQ ≤n!≤Q?

Theorem (Stirling’s approximation)

e(n/e)n≤n!≤ne(n/e)n, i.e. Q =e(n/e)n, andα= 1/n

(9)

Estimating n!

Easy to see thatn!≤nn

However, is this tight? Of course not!

Can we quantify how much more is nn as compared ton!?

Can we bound n! by a quantity, say Q, so that for some small enough

α, αQ ≤n!≤Q?

Theorem (Stirling’s approximation)

e(n/e)n≤n!≤ne(n/e)n, i.e. Q =e(n/e)n, andα= 1/n

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 5 / 13

(10)

Estimating n!

Easy to see thatn!≤nn

However, is this tight? Of course not!

Can we quantify how much more is nn as compared ton!?

Can we bound n! by a quantity, say Q, so that for some small enough

α, αQ ≤n!≤Q?

Theorem (Stirling’s approximation)

e(n/e)n≤n!≤ne(n/e)n, i.e. Q =e(n/e)n, andα= 1/n

(11)

Estimating n!

Theorem (Stirling’s approximation) e(n/e)n≤n!≤ne(n/e)n

Proof.

Let S = log(n!) =Pn

i=1logi. We will bound S using the natural log.

∴S ≤nlogn−n+ 1 + logn

raising both sides to the power of e, we get

n!≤e(n+1) logn−(n−1)

=nn+1/en−1

=ne(n/e)n

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

(12)

Estimating n!

Theorem (Stirling’s approximation) e(n/e)n≤n!≤ne(n/e)n

Proof.

Let S = log(n!)

=Pn

i=1logi. We will bound S using the natural log.

∴S ≤nlogn−n+ 1 + logn

raising both sides to the power of e, we get

n!≤e(n+1) logn−(n−1)

=nn+1/en−1

=ne(n/e)n

(13)

Estimating n!

Theorem (Stirling’s approximation) e(n/e)n≤n!≤ne(n/e)n

Proof.

Let S = log(n!) =Pn

i=1logi.

We will boundS using the natural log.

∴S ≤nlogn−n+ 1 + logn

raising both sides to the power of e, we get

n!≤e(n+1) logn−(n−1)

=nn+1/en−1

=ne(n/e)n

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

(14)

Estimating n!

Theorem (Stirling’s approximation) e(n/e)n≤n!≤ne(n/e)n

Proof.

Let S = log(n!) =Pn

i=1logi. We will bound S using the natural log.

From the figure on the board:

n−1

X

i=1

i ≤ Z n

1

logx dx

S ≤ Z n

1

logx dx+ logn

= (xlogx−x)|n1+ logn

=nlogn−n+ 1 + logn

∴S ≤nlogn−n+ 1 + logn

raising both sides to the power of e, we get

n!≤e(n+1) logn−(n−1)

=nn+1/en−1

=ne(n/e)n

(15)

Estimating n!

Theorem (Stirling’s approximation) e(n/e)n≤n!≤ne(n/e)n

Proof.

Let S = log(n!) =Pn

i=1logi. We will bound S using the natural log.

∴S ≤nlogn−n+ 1 + logn

raising both sides to the power of e, we get

n!≤e(n+1) logn−(n−1)

=nn+1/en−1

=ne(n/e)n

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

(16)

Estimating n!

Theorem (Stirling’s approximation) e(n/e)n≤n!≤ne(n/e)n

Proof.

Let S = log(n!) =Pn

i=1logi. We will bound S using the natural log.

∴S ≤nlogn−n+ 1 + logn

raising both sides to the power of e, we get

n!≤e(n+1) logn−(n−1)

=nn+1/en−1

=ne(n/e)n

(17)

Estimating n!

Theorem (Stirling’s approximation) e(n/e)n≤n!≤ne(n/e)n

Proof.

Let S = log(n!) =Pn

i=1logi. We will bound S using the natural log.

∴S ≥nlogn−n+ 1

raising both sides to the power of e, we get

n!≥enlogn−(n−1)

=e(n/e)n

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 7 / 13

(18)

Estimating n!

Theorem (Stirling’s approximation) e(n/e)n≤n!≤ne(n/e)n

Proof.

Let S = log(n!)

=Pn

i=1logi. We will bound S using the natural log.

∴S ≥nlogn−n+ 1

raising both sides to the power of e, we get

n!≥enlogn−(n−1)

=e(n/e)n

(19)

Estimating n!

Theorem (Stirling’s approximation) e(n/e)n≤n!≤ne(n/e)n

Proof.

Let S = log(n!) =Pn

i=1logi.

We will boundS using the natural log.

∴S ≥nlogn−n+ 1

raising both sides to the power of e, we get

n!≥enlogn−(n−1)

=e(n/e)n

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 7 / 13

(20)

Estimating n!

Theorem (Stirling’s approximation) e(n/e)n≤n!≤ne(n/e)n

Proof.

Let S = log(n!) =Pn

i=1logi. We will bound S using the natural log.

From the figure on the board:

n

X

i=1

i ≥ Z n

1

logx dx

S ≥ Z n

1

logx dx

= (xlogx−x)|n1

=nlogn−n+ 1

∴S ≥nlogn−n+ 1

raising both sides to the power of e, we get

n!≥enlogn−(n−1)

=e(n/e)n

(21)

Estimating n!

Theorem (Stirling’s approximation) e(n/e)n≤n!≤ne(n/e)n

Proof.

Let S = log(n!) =Pn

i=1logi. We will bound S using the natural log.

∴S ≥nlogn−n+ 1

raising both sides to the power of e, we get

n!≥enlogn−(n−1)

=e(n/e)n

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 7 / 13

(22)

Estimating n!

Theorem (Stirling’s approximation) e(n/e)n≤n!≤ne(n/e)n

Proof.

Let S = log(n!) =Pn

i=1logi. We will bound S using the natural log.

∴S ≥nlogn−n+ 1

raising both sides to the power of e, we get

n!≥enlogn−(n−1)

=e(n/e)n

(23)

Counting labeled trees – Cayley’s number

Recall

What is a graph?

What are directed and undirected graphs?

What is a cycle in a graph?

What is a tree?

What is a labeled tree?

Example: Labeled trees on 3 vertices

1 2

3 2

1

3 1

3 2

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 8 / 13

(24)

Counting labeled trees – Cayley’s number

Recall

What is a graph?

What are directed and undirected graphs?

What is a cycle in a graph?

What is a tree?

What is a labeled tree?

Example: Labeled trees on 3 vertices

1 2

3 2

1

3 1

3 2

(25)

Counting labeled trees – Cayley’s number

Recall

What is a graph?

What are directed and undirected graphs?

What is a cycle in a graph?

What is a tree?

What is a labeled tree?

Example: Labeled trees on 3 vertices

1 2

3 2

1

3 1

3 2

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 8 / 13

(26)

How many labeled trees on n vertices?

Theorem (Cayley)

There are nn−2 labeled tree on n vertices.

Proof (by Joyal).

Let an is the number of labeled tree. Then in terms ofan

the number of doubly rooted trees = n2an Suppose we prove that

the number of doubly = total number of functions rooted labeled trees from{1,2, . . . ,n} to{1,2, . . . ,n}

= nn

then we are done.

(27)

How many labeled trees on n vertices?

Theorem (Cayley)

There are nn−2 labeled tree on n vertices.

Proof (by Joyal).

Let an is the number of labeled tree. Then in terms ofan

the number of doubly rooted trees = n2an Suppose we prove that

the number of doubly = total number of functions rooted labeled trees from{1,2, . . . ,n} to{1,2, . . . ,n}

= nn

then we are done.

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 9 / 13

(28)

How many labeled trees on n vertices?

Theorem (Cayley)

There are nn−2 labeled tree on n vertices.

Count one quantity in order to count the other

Proof (by Joyal).

Let an is the number of labeled tree. Then in terms ofan the number of doubly rooted trees = n2an

Suppose we prove that

the number of doubly = total number of functions rooted labeled trees from{1,2, . . . ,n} to{1,2, . . . ,n}

= nn

then we are done.

(29)

How many labeled trees on n vertices?

Theorem (Cayley)

There are nn−2 labeled tree on n vertices.

Count one quantity in order to count the other What is this other quantity that we will count?

Proof (by Joyal).

Let an is the number of labeled tree. Then in terms ofan

the number of doubly rooted trees = n2an Suppose we prove that

the number of doubly = total number of functions rooted labeled trees from{1,2, . . . ,n} to{1,2, . . . ,n}

= nn

then we are done.

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 9 / 13

(30)

How many labeled trees on n vertices?

Theorem (Cayley)

There are nn−2 labeled tree on n vertices.

Count one quantity in order to count the other What is this other quantity that we will count?

Doubly rooted trees: labelled trees with two special nodes (both may be the same vertex)

Proof (by Joyal).

Let an is the number of labeled tree. Then in terms ofan the number of doubly rooted trees = n2an

Suppose we prove that

the number of doubly = total number of functions rooted labeled trees from{1,2, . . . ,n} to{1,2, . . . ,n}

= nn

then we are done.

(31)

How many labeled trees on n vertices?

Theorem (Cayley)

There are nn−2 labeled tree on n vertices.

Proof (by Joyal).

Let an is the number of labeled tree. Then in terms ofan

the number of doubly rooted trees = n2an Suppose we prove that

the number of doubly = total number of functions rooted labeled trees from{1,2, . . . ,n} to{1,2, . . . ,n}

= nn

then we are done.

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 9 / 13

(32)

How many labeled trees on n vertices?

Theorem (Cayley)

There are nn−2 labeled tree on n vertices.

Proof (by Joyal).

Let an is the number of labeled tree. Then in terms ofan

the number of doubly rooted trees = [CW]

n2an Suppose we prove that

the number of doubly = total number of functions rooted labeled trees from{1,2, . . . ,n} to{1,2, . . . ,n}

= nn

then we are done.

(33)

How many labeled trees on n vertices?

Theorem (Cayley)

There are nn−2 labeled tree on n vertices.

Proof (by Joyal).

Let an is the number of labeled tree. Then in terms ofan

the number of doubly rooted trees = n2an

Suppose we prove that

the number of doubly = total number of functions rooted labeled trees from{1,2, . . . ,n} to{1,2, . . . ,n}

= nn

then we are done.

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 9 / 13

(34)

How many labeled trees on n vertices?

Theorem (Cayley)

There are nn−2 labeled tree on n vertices.

Proof (by Joyal).

Let an is the number of labeled tree. Then in terms ofan

the number of doubly rooted trees = n2an Suppose we prove that

the number of doubly = total number of functions rooted labeled trees from{1,2, . . . ,n} to{1,2, . . . ,n}

= nn

then we are done.

(35)

How many doubly rooted labeled trees on n vertices?

Lemma

There is a bijection between

the number of doubly rooted labeled trees on n vertices the number of functions from {1,2, . . . ,n} to {1,2, . . . ,n}

Proof.

u a b c v 2 1 7 9 4

1 2 4 7 9

2 1 7 9 4

f(1) = 2,f(2) = 1,f(4) = 7,f(7) = 9,f(9) = 4

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 10 / 13

(36)

How many doubly rooted labeled trees on n vertices?

Lemma

There is a bijection between

the number of doubly rooted labeled trees on n vertices the number of functions from {1,2, . . . ,n} to {1,2, . . . ,n}

Proof.

From each doubly rooted labeled tree T define a unique functions:

Let u,v be the two roots ofT.

u a b c v 2 1 7 9 4

1 2 4 7 9

2 1 7 9 4

f(1) = 2,f(2) = 1,f(4) = 7,f(7) = 9,f(9) = 4

(37)

How many doubly rooted labeled trees on n vertices?

Lemma

There is a bijection between

the number of doubly rooted labeled trees on n vertices the number of functions from {1,2, . . . ,n} to {1,2, . . . ,n}

Proof.

From each doubly rooted labeled tree T define a unique functions:

Let u,v be the two roots ofT. [CW] How many paths betweenu,v in T?

u a b c v 2 1 7 9 4

1 2 4 7 9

2 1 7 9 4

f(1) = 2,f(2) = 1,f(4) = 7,f(7) = 9,f(9) = 4

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 10 / 13

(38)

How many doubly rooted labeled trees on n vertices?

Lemma

There is a bijection between

the number of doubly rooted labeled trees on n vertices the number of functions from {1,2, . . . ,n} to {1,2, . . . ,n}

Proof.

u a b c v

2 1 7 9 4

1 2 4 7 9

2 1 7 9 4

f(1) = 2,f(2) = 1,f(4) = 7,f(7) = 9,f(9) = 4

(39)

How many doubly rooted labeled trees on n vertices?

Lemma

There is a bijection between

the number of doubly rooted labeled trees on n vertices the number of functions from {1,2, . . . ,n} to {1,2, . . . ,n}

Proof.

u a b c v 2 1 7 9 4

1 2 4 7 9

2 1 7 9 4

f(1) = 2,f(2) = 1,f(4) = 7,f(7) = 9,f(9) = 4

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 10 / 13

(40)

How many doubly rooted labeled trees on n vertices?

Lemma

There is a bijection between

the number of doubly rooted labeled trees on n vertices the number of functions from {1,2, . . . ,n} to {1,2, . . . ,n}

Proof.

u a b c v 2 1 7 9 4 pos(x) :=

distance of x from u

ord(x,S) := order of x in set S.

1 2 4 7 9

2 1 7 9 4

f(1) = 2,f(2) = 1,f(4) = 7,f(7) = 9,f(9) = 4

(41)

How many doubly rooted labeled trees on n vertices?

Lemma

There is a bijection between

the number of doubly rooted labeled trees on n vertices the number of functions from {1,2, . . . ,n} to {1,2, . . . ,n}

Proof.

u a b c v 2 1 7 9 4

1 2 4 7 9

2 1 7 9 4

f(1) = 2,f(2) = 1,f(4) = 7,f(7) = 9,f(9) = 4

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 10 / 13

(42)

How many doubly rooted labeled trees on n vertices?

Lemma

There is a bijection between

the number of doubly rooted labeled trees on n vertices the number of functions from {1,2, . . . ,n} to {1,2, . . . ,n}

Proof.

Each doubly rooted labelled tree gives rise to a function such that: The skeleton abels are permutated among themselves and tree nodes are mapped to their parent.

if u on skeleton S f(u) = j, where ord(u,S) = pos(j) if u not on skeleton f(u) = parent(u)

(43)

How many doubly rooted labeled trees on n vertices?

Lemma

There is a bijection between

the number of doubly rooted labeled trees on n vertices the number of functions from {1,2, . . . ,n} to {1,2, . . . ,n}

Proof.

Each doubly rooted labelled tree gives rise to a function such that:

The skeleton abels are permutated among themselves and tree nodes are mapped to their parent.

if u on skeleton S f(u) = j, where ord(u,S) = pos(j) if u not on skeleton f(u) = parent(u)

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 11 / 13

(44)

How many doubly rooted labeled trees on n vertices?

Lemma

There is a bijection between

the number of doubly rooted labeled trees on n vertices the number of functions from {1,2, . . . ,n} to {1,2, . . . ,n}

Proof.

Each doubly rooted labelled tree gives rise to a function such that:

The skeleton abels are permutated among themselves and tree nodes are mapped to their parent.

x is a parent ofy if (x,y) is an edge andx is closer to the root thany

if u on skeleton S f(u) = j, where ord(u,S) = pos(j) if u not on skeleton f(u) = parent(u)

(45)

How many doubly rooted labeled trees on n vertices?

Lemma

There is a bijection between

the number of doubly rooted labeled trees on n vertices the number of functions from {1,2, . . . ,n} to {1,2, . . . ,n}

Proof.

Each doubly rooted labelled tree gives rise to a function such that:

The skeleton abels are permutated among themselves and tree nodes are mapped to their parent.

if u on skeleton S f(u) = j, where ord(u,S) = pos(j) if u not on skeleton f(u) = parent(u)

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 11 / 13

References

Related documents

Today we will see two theorems which prove two properties of infinite sets that they share with finite sets.. Theorem

It can be derived using another heavy hammer... It can be derived using another

A binary tree is made up of a finite set of nodes that is either empty or consists of a node called the root together with two binary trees called the left and right subtrees which

An interesting game and an open problem (If time permits).. Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 4

I Sets, relations, functions, partial orders, graphs Combinatorics.. Elements of graph theory Elements of

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 July 2012 3

Today we will see two theorems which prove two properties of infinite sets that they share with finite sets. Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 5

• Lightening: Generally, forest fire is started by the sudden fall of lighting on the dry forest or old trees or grasses.. • Combustion: sometimes, fire may