Feb 02, 06, 2018
1
1. Proofs and structures 2. Counting and combinatorics 3. Introduction to graph theory
4. Elements of number theory/abstract algebra
I Proofs and proof techniques: contradiction, contrapositive, (strong) induction, well-ordering principle, diagonalization.
I Basic mathematical structures: (finite and infinite) sets, functions, relations.
I Relations: equivalence relations, partial orders, lattices
I Some applications
2. Counting and combinatorics 3. Introduction to graph theory
4. Elements of number theory/abstract algebra
2
1. Proofs and structures
I Propositions, predicates
I Proofs and proof techniques: contradiction, contrapositive, (strong) induction, well-ordering principle, diagonalization.
I Basic mathematical structures: (finite and infinite) sets, functions, relations.
I Relations: equivalence relations, partial orders, lattices
I Some applications
I Functions: To compare infinite sets
I Using diagonalization to prove impossibility results.
I Equivalences: Defining “like” partitions.
I Posets: Topological sort, (parallel) task scheduling, lattices
2. Counting and combinatorics 3. Introduction to graph theory
4. Elements of number theory/abstract algebra
I Proofs and proof techniques: contradiction, contrapositive, (strong) induction, well-ordering principle, diagonalization.
I Basic mathematical structures: (finite and infinite) sets, functions, relations.
I Relations: equivalence relations, partial orders, lattices
I Some applications
2.
Counting and combinatorics
3. Introduction to graph theory
4. Elements of number theory/abstract algebra
2
I Basics of counting
I Subsets, partitions, Permutations and combinations
I Recurrence relations and generating functions
I Principle of Inclusion and Exclusion and its applications
I Pigeonhole Principle and its extensions
Introduction to combinatorics
Does it really need an introduction
I Constructive combinatorics: construct interesting configurations...
4
I Enumerative combinatorics: counting
combinatorial/discrete objects e.g., sets, numbers, structures...
I Existential combinatorics: show that there exist some combinatorial “configurations”.
I Constructive combinatorics: construct interesting configurations...
Two examples
Letters and envelopes
Givennletters and naddressed envelopes, in how many ways can letters be placed in envelopes so that none of them is in its correctly addressed envelope.
A Ramsey game
I There are six points on board and two colored chalks.
I Divide class into 2 groups. Group 1 draws white lines and Group 2 draws blue lines between points.
I You lose if you are first to draw a triangle of your color.
I Can you ever have a draw?
5
Two examples
Letters and envelopes
Givennletters and naddressed envelopes, in how many ways can letters be placed in envelopes so that none of them is in its correctly addressed envelope.
I Total no. of ways of putting nletters innenvelopes is
the natural logarithm! A Ramsey game
I There are six points on board and two colored chalks.
I Divide class into 2 groups. Group 1 draws white lines and Group 2 draws blue lines between points.
I You lose if you are first to draw a triangle of your color.
I Can you ever have a draw?
Two examples
Letters and envelopes
Givennletters and naddressed envelopes, in how many ways can letters be placed in envelopes so that none of them is in its correctly addressed envelope.
I Total no. of ways of putting nletters innenvelopes is n!.
I We will see that the fraction which are incorrectly
addressed is close to 1/e, wheree= 2.71828...is the base of the natural logarithm!
I Can you ever have a draw?
5
Two examples
Letters and envelopes
Givennletters and naddressed envelopes, in how many ways can letters be placed in envelopes so that none of them is in its correctly addressed envelope.
I Total no. of ways of putting nletters innenvelopes is n!.
I We will see that the fraction which are incorrectly
addressed is close to 1/e, wheree= 2.71828...is the base of the natural logarithm!
A Ramsey game
I There are six points on board and two colored chalks.
I Can you ever have a draw?
Two examples
Letters and envelopes
Givennletters and naddressed envelopes, in how many ways can letters be placed in envelopes so that none of them is in its correctly addressed envelope.
I Total no. of ways of putting nletters innenvelopes is n!.
I We will see that the fraction which are incorrectly
addressed is close to 1/e, wheree= 2.71828...is the base of the natural logarithm!
A Ramsey game
I There are six points on board and two colored chalks.
I Divide class into 2 groups. Group 1 draws white lines and Group 2 draws blue lines between points.
5
Two examples
Letters and envelopes
Givennletters and naddressed envelopes, in how many ways can letters be placed in envelopes so that none of them is in its correctly addressed envelope.
I Total no. of ways of putting nletters innenvelopes is n!.
I We will see that the fraction which are incorrectly
addressed is close to 1/e, wheree= 2.71828...is the base of the natural logarithm!
A Ramsey game
I There are six points on board and two colored chalks.
I Divide class into 2 groups. Group 1 draws white lines and Group 2 draws blue lines between points.
I You lose if you are first to draw a triangle of your color.
correctly addressed envelope.
I Total no. of ways of putting nletters innenvelopes is n!.
I We will see that the fraction which are incorrectly
addressed is close to 1/e, wheree= 2.71828...is the base of the natural logarithm!
A Ramsey game
I There are six points on board and two colored chalks.
I Divide class into 2 groups. Group 1 draws white lines and Group 2 draws blue lines between points.
I You lose if you are first to draw a triangle of your color.
I Can you ever have a draw?
5
I Of the remaining, we can choose any of them to be in or out.
I there aren2−nof them, so 2n2−n of them.
I We used the so-called “product principle”...
6
I Reflexive relations are ordered pairs of which there aren2.
I Of these, allnpairs of (a, a) have be present.
I Of the remaining, we can choose any of them to be in or out.
I there aren2−nof them, so 2n2−n of them.
I We used the so-called “product principle”...
The product principle
If there aren1 ways of doing something and n2 ways of doing another thing, then there aren1·n2 ways of performing both actions.
I If 20 teams play in the IITB-premier league and every game has a winner/loser and loser is always eliminated. How many games are played before a champion is chosen?
I How many subsets does a set A ofnelements have?
6
I How many functions are there from a set of sizen to itself?
I If 20 teams play in the IITB-premier league and every game has a winner/loser and loser is always eliminated. How many games are played before a champion is chosen?
I How many subsets does a set A ofnelements have?
I Product principle: two choices for each element, hence 2·2· · ·2·2 (n-times).
I Bijection: betweenP(X) andn-length sequences over{0,1}
(characteristic vector).
I Induction: Since we already know the answer!
I Recurrence: F(n) = 2·F(n−1), F(0) = 1. solve it?
I Sum principle: Subsets of size 0 + subsets of size 1 +. . .+ subsets of sizen= Total number of subsets.
I How many subsets does a set A ofnelements have?
I Product principle: two choices for each element, hence 2·2· · ·2·2 (n-times).
I Bijection: betweenP(X) andn-length sequences over{0,1}
(characteristic vector).
I Induction: Since we already know the answer!
I Recurrence: F(n) = 2·F(n−1), F(0) = 1. solve it?
I Sum principle: Subsets of size 0 + subsets of size 1 +. . .+ subsets of sizen= Total number of subsets.
Sum Principle
If something can be done inn1 orn2 ways such that none of the n1 ways is the same as any of then2 ways, then the total number of ways to do this isn1+n2.
6
I How many functions are there from a set of sizen to itself?
I How many subsets does a set A ofnelements have?
I Product principle: two choices for each element, hence 2·2· · ·2·2 (n-times).
I Bijection: betweenP(X) andn-length sequences over{0,1}
(characteristic vector).
I Induction: Since we already know the answer!
I Recurrence: F(n) = 2·F(n−1), F(0) = 1. solve it?
I Sum principle: Subsets of size 0 + subsets of size 1 +. . .+ subsets of sizen= Total number of subsets.
I But, how many subsets of size k does a set ofn elements have? This number, denoted nk
, is called abinomial coefficient.
I How many subsets does a set A ofnelements have?
I Product principle: two choices for each element, hence 2·2· · ·2·2 (n-times).
I Bijection: betweenP(X) andn-length sequences over{0,1}
(characteristic vector).
I Induction: Since we already know the answer!
I Recurrence: F(n) = 2·F(n−1), F(0) = 1. solve it?
I Sum principle: Subsets of size 0 + subsets of size 1 +. . .+ subsets of sizen= Total number of subsets.
I But, how many subsets of size k does a set ofn elements have? This number, denoted nk
, is called abinomial coefficient.
I We all know(?) that nk
= k!(n−k)!n! . Prove it!
6
How many subsets of sizekdoes a set of nelements have? This number, denoted nk
, is called a binomial coefficient.
One proof of nk
= k!(n−k)!n! is as follows:
One proof of nk
= k!(n−k)!n! is as follows: Let us count the number of“ordered”subsets of size k.
7
How many subsets of sizekdoes a set of nelements have? This number, denoted nk
, is called a binomial coefficient.
One proof of nk
= k!(n−k)!n! is as follows: Let us count the number of“ordered”subsets of size k.
I No. of orderedsubsets of sizek=n·(n−1)· · ·(n−k+ 1).
One proof of nk
= k!(n−k)!n! is as follows: Let us count the number of“ordered”subsets of size k.
I No. of orderedsubsets of size k=n·(n−1)· · ·(n−k+ 1).
I No. of orderedsubsets of size k= (no. of unordered subsets)×(no. of ways to order them)= nk
×k!.
7
How many subsets of sizekdoes a set of nelements have? This number, denoted nk
, is called a binomial coefficient.
One proof of nk
= k!(n−k)!n! is as follows: Let us count the number of“ordered”subsets of size k.
I No. of orderedsubsets of size k=n·(n−1)· · ·(n−k+ 1).
I No. of orderedsubsets of size k= (no. of unordered subsets)×(no. of ways to order them)= nk
×k!.
I Equate them! Principle of double counting.
I if you can’t count something, count something else and count it twice over!
One proof of nk
= k!(n−k)!n! is as follows: Let us count the number of“ordered”subsets of size k.
I No. of orderedsubsets of size k=n·(n−1)· · ·(n−k+ 1).
I No. of orderedsubsets of size k= (no. of unordered subsets)×(no. of ways to order them)= nk
×k!.
I Equate them! Principle of double counting.
Permutations and combinations
I No. of k-size subsets of set of size n= No. of
k-combinations of a set of n(distinct) elements = nk .
I No. of k-size ordered subsets of set of sizen = No. of k-permutations of a set ofn (distinct) elements.
7
Simple examples to illustrate “double counting”
Prove the following identities (by only using double counting!)
1.
n
X
k=0
n k
= 2n.
2.
n k
= n
n−k
. 3. k
n k
=n n−1
k−1
4.
n+ 1 k
= n
k−1
+ n
k
1.
k=0 k = 2 . 2.
n k
= n
n−k
. 3. k
n k
=n n−1
k−1
4.
n+ 1 k
= n
k−1
+ n
k
The latter two are in fact recursive definitions for nk
. What are the boundary conditions?
8
A more interesting example with double counting
Handshake Lemma
At a meeting withnpeople, the number of people who shake hands an odd number of times is even.
What will you count here?
3. Let mi be the number of times ishakes hands. i.e., mi is the number of directed edges going out from i.
4. Therefore, Total no. of directed edges =P
imi.
5. But now, let X be the total number of handshakes. Clearly this is an integer. Total no. of directed edges = 2·X. 6. This implies, P
imi = 2·X. Which means that number of isuch that mi is odd is even!
A more interesting example with double counting
Handshake Lemma
At a meeting withnpeople, the number of people who shake hands an odd number of times is even.
Proof in six steps:
1. Define a relation R: iRj ifiand j shook hands.
2. Is this relation symmetric (trans/refl.)? Draw its graph.
6. This implies, P
imi = 2·X. Which means that number of isuch that mi is odd is even!
9
A more interesting example with double counting
Handshake Lemma
At a meeting withnpeople, the number of people who shake hands an odd number of times is even.
Proof in six steps:
1. Define a relation R: iRj ifiand j shook hands.
2. Is this relation symmetric (trans/refl.)? Draw its graph.
3. Let mi be the number of times ishakes hands.
5. But now, let X be the total number of handshakes. Clearly this is an integer. Total no. of directed edges = 2·X. 6. This implies, P
imi = 2·X. Which means that number of isuch that mi is odd is even!
A more interesting example with double counting
Handshake Lemma
At a meeting withnpeople, the number of people who shake hands an odd number of times is even.
Proof in six steps:
1. Define a relation R: iRj ifiand j shook hands.
2. Is this relation symmetric (trans/refl.)? Draw its graph.
3. Let mi be the number of times ishakes hands. i.e., mi is the number of directed edges going out from i.
9
A more interesting example with double counting
Handshake Lemma
At a meeting withnpeople, the number of people who shake hands an odd number of times is even.
Proof in six steps:
1. Define a relation R: iRj ifiand j shook hands.
2. Is this relation symmetric (trans/refl.)? Draw its graph.
3. Let mi be the number of times ishakes hands. i.e., mi is the number of directed edges going out from i.
4. Therefore, Total no. of directed edges =P
imi.
isuch that mi is odd is even!
A more interesting example with double counting
Handshake Lemma
At a meeting withnpeople, the number of people who shake hands an odd number of times is even.
Proof in six steps:
1. Define a relation R: iRj ifiand j shook hands.
2. Is this relation symmetric (trans/refl.)? Draw its graph.
3. Let mi be the number of times ishakes hands. i.e., mi is the number of directed edges going out from i.
4. Therefore, Total no. of directed edges =P
imi.
5. But now, let X be the total number of handshakes. Clearly this is an integer.
9
A more interesting example with double counting
Handshake Lemma
At a meeting withnpeople, the number of people who shake hands an odd number of times is even.
Proof in six steps:
1. Define a relation R: iRj ifiand j shook hands.
2. Is this relation symmetric (trans/refl.)? Draw its graph.
3. Let mi be the number of times ishakes hands. i.e., mi is the number of directed edges going out from i.
4. Therefore, Total no. of directed edges =P
imi.
5. But now, let X be the total number of handshakes. Clearly this is an integer. Total no. of directed edges = 2·X.
Proof in six steps:
1. Define a relation R: iRj ifiand j shook hands.
2. Is this relation symmetric (trans/refl.)? Draw its graph.
3. Let mi be the number of times ishakes hands. i.e., mi is the number of directed edges going out from i.
4. Therefore, Total no. of directed edges =P
imi.
5. But now, let X be the total number of handshakes. Clearly this is an integer. Total no. of directed edges = 2·X.
6. This implies, P
imi = 2·X. Which means that number of isuch that mi is odd is even!
9
1. Binomial coefficients and Binomial theorem 2. Pascal’s triangle
3. Permutations and combinations with repetitions 4. Estimatingn!
11
k=0
We generalize this...
Binomial Theorem
Letx, y be variables andn∈Z≥0. Then, (x+y)n=
n
X
j=0
n j
xn−jyj
(x+y)n=X
j=0
n
j xn−jyj (H.W-1) Prove this by induction.
11
Letx, y be variables andn∈Z≥0. Then, (x+y)n=
n
X
j=0
n j
xn−jyj
Proof (combinatorial):
1. Consider any term xiyj, where i+j=n.
2. To get xiyj term in
(x+y)(x+y)· · ·(x+y) (n times) we need to pick j y0sfrom nsums and remainingx’s.
(x+y)n=X
j=0
n
j xn−jyj
Proof (combinatorial):
1. Consider any term xiyj, where i+j=n.
2. To get xiyj term in
(x+y)(x+y)· · ·(x+y) (n times) we need to pick j y0sfrom nsums and remainingx’s.
3. Thus, the coefficient of this term = number of ways to get this term = number of ways to pickj y’s from nelts = nj
.
11
Letx, y be variables andn∈Z≥0. Then, (x+y)n=
n
X
j=0
n j
xn−jyj
(x+y)n=X
j=0
n
j xn−jyj
Corollaries:
1. nj
= n−jn , 2.
n
X
j=0
n j
2j = 3n.
3. No. of subsets ofn-element set having even cardinality = ? (H.W-2)
11
n+ 1 k
= n
k−1
+ n
k
Some simple observations. Recall: n+1k
= k−1n + nk 1. Rowiadds up to 2i, Rowi+ 1 adds up to twice of rowi.
2. Sequence of numbers, squares, cubes?
13
Some simple observations. Recall: n+1k
= k−1n + nk 1. Rowiadds up to 2i, Rowi+ 1 adds up to twice of rowi.
2. Sequence of numbers, squares, cubes?
3. Hockey stick patterns
Some simple observations. Recall: n+1k
= k−1n + nk 1. Rowiadds up to 2i, Rowi+ 1 adds up to twice of rowi.
2. Sequence of numbers, squares, cubes?
3. Hockey stick patterns: (H.W-3)
n+1 m
= mn
+ m−1n−1
. . .+ n−m0
13
Somenot so simple observations
I For some rows, all values in the row (except first and last) are divisible by the second!
Somenot so simple observations
I For some rows, all values in the row (except first and last) are divisible by the second!
I In fact, for all prime rows? why should pdivide pr
,r < p?
13
Somenot so simple observations
I For some rows, all values in the row (except first and last) are divisible by the second!
I In fact, for all prime rows? why should pdivide pr
,r < p?
I Corollary: 2p−2 is a multiple of p, for any primep.
Somenot so simple observations
I For some rows, all values in the row (except first and last) are divisible by the second!
I In fact, for all prime rows? why should pdivide pr
,r < p?
I Corollary: 2p−2 is a multiple of p, for any primep.
I Interesting Ex.: Count no. of odd numbers in each row...
13
elements?
I Depends on whether order is significant: If yes permutations, else combinations.
I What if repetitions are allowed?
Order significant Order not significant Repetitions
not allowed
n!
(n−k)!
n k
Repetitions are allowed
nk ??
Combinations with repetitions
Theorem
The no. of wayskelements can be chosen fromn-elements, when repetition is allowed is n+k−1k
= n+k−1n−1 .
n-elements with repetitions allowed (why?).
4. Thus, question reduces to no. of ways to choose kstars or n−1 bars from a set of n−k+ 1 positions = n+k−1k
.
I H.W-5: How many solutions does the equation
x1+x2+x3+x4= 17 have such that x1, x2, x3, x4∈Z≥0 ?
15
Combinations with repetitions
Theorem
The no. of wayskelements can be chosen fromn-elements, when repetition is allowed is n+k−1k
= n+k−1n−1 .
1. Represent them as a list of n−1 separators of kobjects.
3. There is a bijection between such lists andk-sets of n-elements with repetitions allowed (why?).
4. Thus, question reduces to no. of ways to choose kstars or n−1 bars from a set of n−k+ 1 positions = n+k−1k
.
I H.W-5: How many solutions does the equation
x1+x2+x3+x4= 17 have such that x1, x2, x3, x4∈Z≥0 ?
Combinations with repetitions
Theorem
The no. of wayskelements can be chosen fromn-elements, when repetition is allowed is n+k−1k
= n+k−1n−1 .
1. Represent them as a list of n−1 separators of kobjects.
2. e.g., suppose we want to select 5 elts from a set of 4 with repetitions. Then,∗ ∗ | ∗ || ∗ ∗ represents: 2 of the first element, 1 of the second, none of third and 2 of fourth.
I H.W-5: How many solutions does the equation
x1+x2+x3+x4= 17 have such that x1, x2, x3, x4∈Z≥0 ?
15
Combinations with repetitions
Theorem
The no. of wayskelements can be chosen fromn-elements, when repetition is allowed is n+k−1k
= n+k−1n−1 .
1. Represent them as a list of n−1 separators of kobjects.
2. e.g., suppose we want to select 5 elts from a set of 4 with repetitions. Then,∗ ∗ | ∗ || ∗ ∗ represents: 2 of the first element, 1 of the second, none of third and 2 of fourth.
3. There is a bijection between such lists andk-sets of n-elements with repetitions allowed (why?).
x1+x2+x3+x4= 17 have such that x1, x2, x3, x4∈Z≥0 ?
Combinations with repetitions
Theorem
The no. of wayskelements can be chosen fromn-elements, when repetition is allowed is n+k−1k
= n+k−1n−1 .
1. Represent them as a list of n−1 separators of kobjects.
2. e.g., suppose we want to select 5 elts from a set of 4 with repetitions. Then,∗ ∗ | ∗ || ∗ ∗ represents: 2 of the first element, 1 of the second, none of third and 2 of fourth.
3. There is a bijection between such lists andk-sets of n-elements with repetitions allowed (why?).
4. Thus, question reduces to no. of ways to choose kstars or n−1 bars from a set of n−k+ 1 positions = n+k−1k
.
15
The no. of wayskelements can be chosen fromn-elements, when repetition is allowed is n+k−1k
= n+k−1n−1 .
1. Represent them as a list of n−1 separators of kobjects.
2. e.g., suppose we want to select 5 elts from a set of 4 with repetitions. Then,∗ ∗ | ∗ || ∗ ∗ represents: 2 of the first element, 1 of the second, none of third and 2 of fourth.
3. There is a bijection between such lists andk-sets of n-elements with repetitions allowed (why?).
4. Thus, question reduces to no. of ways to choose kstars or n−1 bars from a set of n−k+ 1 positions = n+k−1k
.
I H.W-5: How many solutions does the equation
x1+x2+x3+x4= 17 have such that x1, x2, x3, x4∈Z≥0 ?
Estimating n!
How big isn!?
I It is clearly bigger than nand n2.
I Can we do better?
Can we quantify how much more nn is compared ton!? Theorem (Stirling’s Approximation)
e n
e n
≤n!≤ne n
e n
whereeis the base of natural logarithms, log(e) =elog(e)= 1.
16
Estimating n!
How big isn!?
I It is clearly bigger than nand n2.
I Is it bigger than 2n,nn?
I Can we do better?
Can we quantify how much more nn is compared ton!? Theorem (Stirling’s Approximation)
e n
e n
≤n!≤ne n
e n
whereeis the base of natural logarithms, log(e) =elog(e)= 1.
Estimating n!
How big isn!?
I It is clearly bigger than nand n2.
I Is it bigger than 2n,nn?
I Easy to see: for all n≥4,
2n≤n!≤nn
e e
whereeis the base of natural logarithms, log(e) =elog(e)= 1.
16
Estimating n!
How big isn!?
I It is clearly bigger than nand n2.
I Is it bigger than 2n,nn?
I Easy to see: for all n≥4,
2n≤n!≤nn
I Can we do better?
Can we quantify how much more nn is compared ton!?
whereeis the base of natural logarithms, log(e) =elog(e)= 1.
I Easy to see: for all n≥4,
2n≤n!≤nn
I Can we do better?
Can we quantify how much more nn is compared ton!?
Theorem (Stirling’s Approximation) e
n e
n
≤n!≤ne n
e n
whereeis the base of natural logarithms, log(e) =elog(e)= 1.
16
en e
n
≤n!≤nen e
n
whereeis the base of natural logarithms, log(e) =elog(e)= 1.
whereeis the base of natural logarithms, log(e) =elog(e)= 1.
Proof: Let S = log(n!) = Pn
i=1log(i). Thus, eS =n!
17
e n
e ≤n!≤ne n e
whereeis the base of natural logarithms, log(e) =elog(e)= 1.
Proof: Let S = log(n!) = Pn
i=1log(i). Thus, eS =n!
Now, we relate it to natural log function as shown in the figure.
n
X
i=1
log(i)≥ Z n
1
log(x)dx≥
n−1
X
i=1
log(i)
Approximating the factorial
Theorem (Stirling’s Approximation) en
e n
≤n!≤nen e
n
whereeis the base of natural logarithms, log(e) =elog(e)= 1.
Proof: Let S = log(n!) = Pn
i=1log(i). Thus, eS =n!
n
X
i=1
log(i)≥ Z n
1
log(x)dx≥
n−1
X
i=1
log(i)
17
Approximating the factorial
Theorem (Stirling’s Approximation) en
e n
≤n!≤nen e
n
whereeis the base of natural logarithms, log(e) =elog(e)= 1.
Proof: Let S = log(n!) = Pn
i=1log(i). Thus, eS =n!
n
X
i=1
log(i)≥ Z n
1
log(x)dx≥
n−1
X
i=1
log(i) S≥xlog(x)−x|n1 ≥S−log(n)
whereeis the base of natural logarithms, log(e) =elog(e)= 1.
Proof: Let S = log(n!) = Pn
i=1log(i). Thus, eS =n!
n
X
i=1
log(i)≥ Z n
1
log(x)dx≥
n−1
X
i=1
log(i) S≥xlog(x)−x|n1 ≥S−log(n) S≥nlog(n)−n+ 1≥S−log(n).
17
en e
n
≤n!≤nen e
n
whereeis the base of natural logarithms, log(e) =elog(e)= 1.
Proof: Let S = log(n!) = Pn
i=1log(i). Thus, eS =n!
n
X
i=1
log(i)≥ Z n
1
log(x)dx≥
n−1
X
i=1
log(i) S≥xlog(x)−x|n1 ≥S−log(n) S≥nlog(n)−n+ 1≥S−log(n).
Raising both sides to power ofewe get
I l.h.s. n!≥enlog(n)−n+1 = (n/e)neand
whereeis the base of natural logarithms, log(e) =elog(e)= 1.
Proof: Let S = log(n!) = Pn
i=1log(i). Thus, eS =n!
n
X
i=1
log(i)≥ Z n
1
log(x)dx≥
n−1
X
i=1
log(i) S≥xlog(x)−x|n1 ≥S−log(n) S≥nlog(n)−n+ 1≥S−log(n).
Raising both sides to power ofewe get
I l.h.s. n!≥enlog(n)−n+1 = (n/e)neand
I r.h.s. n!≤e(n+1) log(n)−n+1 =nn+1/en−1 =ne(n/e)n.
17
