Lecture Notes Yale University Spring

Microsoft Research #1 (Redmond Wa) 2343 2000 Jun 23 11:51:51

Description

Niveau: Supérieur, Doctorat, Bac+8
Discrete Mathematics Lecture Notes, Yale University, Spring 1999 L. Lovasz and K. Vesztergombi Parts of these lecture notes are based on L. Lovasz – J. Pelikan – K. Vesztergombi: Kombinatorika (Tankonyvkiado, Budapest, 1972); Chapter 14 is based on a section in L. Lovasz – M.D. Plummer: Matching theory (Elsevier, Amsterdam, 1979) 1

• counting regions


• subset counting


• fibonacci numbers


• distributing presents


• mathematical cryptography


• most people


• another matching


• mathematics cannot


• counting subsets

Sujets

• Yale University
• Triangle
• Arthur's
• Fibonacci number

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 11
• Langue: English

Extrait

Discrete Mathematics
Lecture Notes, Yale University, Spring 1999
L. Lov´asz and K. Vesztergombi
Parts of these lecture notes are based on
´ ´L. Lovasz – J. Pelikan – K. Vesztergombi: Kombinatorika
(Tank¨onyvkiad´o, Budapest, 1972);
Chapter 14 is based on a section in
´L. Lovasz – M.D. Plummer: Matching theory
(Elsevier, Amsterdam, 1979)
12Contents
1 Introduction 5
2 Let us count! 7
2.1 A party . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Sets and the like . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 The number of subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Induction 21
3.1 The sum of odd numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Subset counting revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3 Counting regions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 Counting subsets 27
4.1 The number of ordered subsets . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 The number of subsets of a given size . . . . . . . . . . . . . . . . . . . . . 28
4.3 The Binomial Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.4 Distributing presents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.5 Anagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.6 money . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5 Pascal’s Triangle 35
5.1 Identities in the Pascal Triangle . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2 A bird’s eye view at the Pascal Triangle . . . . . . . . . . . . . . . . . . . . 38
6 Fibonacci numbers 45
6.1 Fibonacci’s exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.2 Lots of identities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6.3 A formula for the Fibonacci numbers . . . . . . . . . . . . . . . . . . . . . . 47
7 Combinatorial probability 51
7.1 Events and probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
7.2 Independent repetition of an experiment . . . . . . . . . . . . . . . . . . . . 52
7.3 The Law of Large Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
8 Integers, divisors, and primes 55
8.1 Divisibility of integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
8.2 Primes and their history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
8.3 Factorization into primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
8.4 On the set of primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
8.5 Fermat’s “Little” Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
8.6 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
8.7 Testing for primality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
39 Graphs 73
9.1 Even and odd degrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
9.2 Paths, cycles, and connectivity . . . . . . . . . . . . . . . . . . . . . . . . . 77
10 Trees 81
10.1 How to grow a tree? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
10.2 Rooted trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
10.3 How many trees are there? . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
10.4 How to store a tree? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
11 Finding the optimum 93
11.1 Finding the best tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
11.2 Traveling Salesman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
12 Matchings in graphs 98
12.1 A dancing problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
12.2 Another matching problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
12.3 The main theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
12.4 How to find a perfect matching? . . . . . . . . . . . . . . . . . . . . . . . . 104
12.5 Hamiltonian cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
13 Graph coloring 110
13.1 Coloring regions: an easy case . . . . . . . . . . . . . . . . . . . . . . . . . . 110
14 A Connecticut class in King Arthur’s court 114
15 A glimpse of cryptography 117
15.1 Classicaly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
16 One-time pads 117
16.1 How to save the last move in chess? . . . . . . . . . . . . . . . . . . . . . . 118
16.2 How to verify a password—without learning it? . . . . . . . . . . . . . . . . 120
16.3 How to find these primes? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
16.4 Public key cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
41 Introduction
For most students, the first and often only area of mathematics in college is calculus. And
it is true that calculus is the single most important field of mathematics, whose emergence
in the 17th century signalled the birth of modern and was the key to the
successful applications of mathematics in the sciences.
But calculus (or analysis) is also very technical. It takes a lot of work even to introduce
its fundamental notions like continuity or derivatives (after all, it took 2 centuries just
to define these properly). To get a feeling for the power of its methods, say by
describing one of its important applications in detail, takes years of study.
Ifyouwanttobecomeamathematician,computerscientist,orengineer,thisinvestment
is necessary. But if your goal is to develop a feeling for what mathematics is all about,
where is it that mathematical methods can be helpful, and what kind of questions do
mathematicians work on, you may want to look for the answer in some other fields of
mathematics.
There are many success stories of applied mathematics outside calculus. A recent hot
topicismathematicalcryptography, whichisbasedonnumbertheory(thestudyofpositive
integers1,2,3,...), andiswidelyapplied, amongothers, incomputersecurityandelectronic
banking. Otherimportantareasinappliedmathematicsincludelinearprogramming,coding
theory, theory of computing. The mathematics in these applications is collectively called
discrete mathematics. (“Discrete” here is used as the opposite of “continuous”; it is also
often used in the more restrictive sense of “finite”.)
The aim of this book is not to cover “discrete mathematics” in depth (it should be clear
from the description above that such a task would be ill-defined and impossible anyway).
Rather, we discuss a number of selected results and methods, mostly from the areas of
combinatorics, graph theory, and combinatorial geometry, with a little elementary number
theory.
At the same time, it is important to realize that mathematics cannot be done without
proofs. Merely stating the facts, without saying something about why these facts are valid,
would be terribly far from the spirit of mathematics and would make it impossible to give
any idea about how it works. Thus, wherever possible, we’ll give the proofs of the theorems
we state. Sometimes this is not possible; quite simple, elementary facts can be extremely
difficult to prove, and some such proofs may take advanced courses to go through. In these
cases, we’ll state at least that the proof is highly technical and goes beyond the scope of
this book.
Another important ingredient of mathematics is problem solving. You won’t be able
to learn any mathematics without dirtying your hands and trying out the ideas you learn
about in the solution of problems. To some, this may sound frightening, but in fact most
people pursue this type of activity almost every day: everybody who plays a game of chess,
orsolvesapuzzle,issolvingdiscretemathematicalproblems. Thereaderisstronglyadvised
to answer the questions posed in the text and to go through the problems at the end of
each chapter of this book. Treat it as puzzle solving, and if you find some idea that you
come up with in the solution to play some role later, be satisfied that you are beginning to
get the essence of how mathematics develops.
We hope that we can illustrate that mathematics is a building, where results are built
5on earlier results, often going back to the great Greek mathematicians; that mathematics
is alive, with more new ideas and more pressing unsolved problems than ever; and that
mathematics is an art, where the beauty of ideas and methods is as important as their
difficulty or applicability.
62 Let us count!
2.1 A party
Alice invites six guests to her birthday party: Bob, Carl, Diane, Eve, Frank and George.
When they arrive, they shake hands with each other (strange European custom). This
group is strange anyway, because one of them asks: “How many handshakes does this
mean?”
“I shook 6 hands altogether” says Bob, “and I guess, so did everybody else.”<