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
Last time
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
Today
How large/small is n!? – approximating n! [Stirling’s approximation]
Counting the number of labelled trees – Cayley’s number.
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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.
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
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.
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
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.
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
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.
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
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.
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
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
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
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
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
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
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
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)
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
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)
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