ete M |
Math |
|
|
|
|
|
|
|
|
Note |
|
D |
|
Discrete |
|
|
Mathe |
|
|
|
|
|
No |
Notes |
|
|
Discr |
|
|
|
|
Mathem |
|
|
|
|
|
Notes |
|
|
Discre |
|
|
M |
Math |
|
|
|
|
|
|
N |
Note |
|
D |
|
Discrete |
|
|
Mathe |
|
|
|
|
|
No |
Notes |
|
|
Discr |
|
|
|
|
Mathem |
|
|
|
|
|
Notes |
|
|
Discre |
|
|
M |
Math |
|
|
|
|
|
N |
Note |
|
D |
Discrete |
|||||||||||||||||||||||||
|
Mathem |
|
|
|
|
|
N |
|
Notes |
|
|
|
M |
|
Mathema |
|
|
|
|
Notes |
D |
|
Discrete |
|
Ma |
|
Mathemat |
|
|
|
Not |
Notes |
Dis |
Discrete |
|
Mathem |
|
|
|
|
|
Notes |
|
|
|
M |
|
Mathema |
|
|
|
|
Notes |
D |
|
Discrete |
|
Ma |
|
Mathemat |
|
|
|
Not |
Notes |
Dis |
Discrete |
|
Mathem |
|
|
|
|
Notes |
|
||||||||||||||||||||||||||||||||||||||||||||||||
iscrete |
|
|
Mathematic |
|
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
Mathematic |
|
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
Mathematic |
|
|
|
|
Notes |
|
||||||||||||||||||||||||||||||||||||||||||
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
|
|
|
|
|
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
|
|
|
|
|
|
|
|
Mathematics |
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
tes |
Discrete |
|
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||
|
Discrete |
|
|
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
||||||||||||||||||||||||||||||||||||||||||
Notes |
|
Discrete |
|
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
|
|
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
|
|
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|||||||||||||||||||||||||||||||||||||||||||||
|
|
Discrete |
|
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
Notes |
|
|
|
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
Notes |
|
|
|
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||
tics |
Notes |
|
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
Notes |
|
|
|
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
Notes |
|
|
|
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||
|
Notes |
|
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
Notes |
|
|
|
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
Notes |
|
|
|
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||
|
|
|
Notes |
|
|
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
Notes |
|
|
|
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
Notes |
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
Notes |
|
|
|
Discrete |
|
|
Mathematics |
|
|
|
|
Notes |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
|
|
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
|
|
|
|
|
|
|
|
|
Mathematics |
|
|
|
|
|
|
|
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
|
|
|
|
Discrete |
|
|
|
Mathematics |
|
|
|
|
|
|
|
|
|
|
|
|
|
Mathematics |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mathematics |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mathematics |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mathematics |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mathematics |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mathematics |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mathematics |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
David A. SANTOS
dsantos@ccp.edu
July 17, 2008 REVISION
ii
Contents
Preface |
|
iii |
4 |
Relations and Functions |
38 |
||||
GNU Free Documentation License |
v |
|
4.1 |
Partitions and Equivalence Relations . . . . . . . . . |
38 |
||||
|
4.2 |
Functions . . . . . . . . . . . . . . . . . . . . . . . |
40 |
||||||
|
1. |
APPLICABILITY AND DEFINITIONS . . . . . . . . |
v |
|
|
|
|
|
|
|
2. |
VERBATIM COPYING . . . . . . . . . . . . . . . . . |
v |
5 |
Number Theory |
44 |
|||
|
3. |
COPYING IN QUANTITY . . . . . . . . . . . . . . . |
v |
|
5.1 |
Division Algorithm . . . . . . . . . . . . . . . . . . |
44 |
||
|
4. |
MODIFICATIONS . . . . . . . . . . . . . . . . . . . . |
v |
|
5.2 |
Greatest Common Divisor . . . . . . . . . . . . . . |
46 |
||
|
5. |
COMBINING DOCUMENTS . . . . . . . . . . . . . . |
vi |
|
5.3 |
Non-decimal Scales . . . . . . . . . . . . . . . . . . |
48 |
||
|
6. |
COLLECTIONS OF DOCUMENTS . . . . . . . . . . |
vi |
|
5.4 |
Congruences . . . . . . . . . . . . . . . . . . . . . |
49 |
||
|
7. |
AGGREGATION WITH INDEPENDENT WORKS . . |
vi |
|
5.5 |
Divisibility Criteria . . . . . . . . . . . . . . . . . . |
51 |
||
|
8. |
TRANSLATION . . . . . . . . . . . . . . . . . . . . . |
vi |
|
Homework . |
. . . . . . . . . . . . . . . . . . . . . . . . . |
53 |
||
|
9. |
TERMINATION . . . . . . . . . . . . . . . . . . . . . |
vi |
|
Answers . . |
. . . . . . . . . . . . . . . . . . . . . . . . . |
54 |
||
|
10. FUTURE REVISIONS OF THIS LICENSE . . . . . . |
vi |
6 |
Enumeration |
57 |
||||
|
|
|
|
|
|||||
1 |
Pseudocode |
1 |
|
6.1 |
The Multiplication and Sum Rules . . . . . . . . . . |
57 |
|||
|
1.1 |
Operators . . . . . . . . . . . . . . . . . . . . . . . |
1 |
|
6.2 |
Combinatorial Methods . . . . . . . . . . . . . . . . |
59 |
||
|
1.2 |
Algorithms . . . . . . . . . . . . . . . . . . . . . . |
2 |
|
|
6.2.1 |
Permutations without Repetitions . . . . . . |
60 |
|
|
1.3 |
Arrays . . . . . . . . . . . . . . . . . . . . . . . . . |
3 |
|
|
6.2.2 |
Permutations with Repetitions . . . . . . . . |
62 |
|
|
1.4 |
If-then-else Statements . . . . . . . . . . . . . |
4 |
|
|
6.2.3 |
Combinations without Repetitions . . . . . . |
64 |
|
|
1.5 |
The for loop . . . . . . . . . . . . . . . . . . . . . |
5 |
|
|
6.2.4 |
Combinations with Repetitions . . . . . . . . |
66 |
|
|
1.6 |
The while loop . . . . . . . . . . . . . . . . . . . |
8 |
|
6.3 |
Inclusion-Exclusion . . . . . . . . . . . . . . . . . . |
67 |
||
|
Homework . . . . . . . . . . . . . . . . . . . . . . . . . . |
10 |
|
Homework . |
. . . . . . . . . . . . . . . . . . . . . . . . . |
72 |
|||
|
Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . |
11 |
|
Answers . . |
. . . . . . . . . . . . . . . . . . . . . . . . . |
73 |
|||
2 |
Proof Methods |
14 |
7 |
Sums and Recursions |
78 |
||||
|
2.1 |
Proofs: Direct Proofs . . . . . . . . . . . . . . . . . |
14 |
|
7.1 |
Famous Sums . . . . . . . . . . . . . . . . . . . . . |
78 |
||
|
2.2 |
Proofs: Mathematical Induction . . . . . . . . . . . |
15 |
|
7.2 |
First Order Recursions . . . . . . . . . . . . . . . . |
82 |
||
|
2.3 |
Proofs: Reductio ad Absurdum . . . . . . . . . . . . |
17 |
|
7.3 |
Second Order Recursions . . . . . . . . . . . . . . . |
85 |
||
|
2.4 |
Proofs: Pigeonhole Principle . . . . . . . . . . . . . |
19 |
|
7.4 |
Applications of Recursions . . . . . . . . . . . . . . |
86 |
||
|
Homework . . . . . . . . . . . . . . . . . . . . . . . . . . |
20 |
|
Homework . |
. . . . . . . . . . . . . . . . . . . . . . . . . |
87 |
|||
|
Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . |
22 |
|
Answers . . |
. . . . . . . . . . . . . . . . . . . . . . . . . |
88 |
|||
3 Logic, Sets, and Boolean Algebra |
26 |
8 |
Graph Theory |
89 |
|||||
|
3.1 |
Logic . . . . . . . . . . . . . . . . . . . . . . . . . |
26 |
|
8.1 |
Simple Graphs . . . . . . . . . . . . . . . . . . . . |
89 |
||
|
3.2 |
Sets . . . . . . . . . . . . . . . . . . . . . . . . . . |
29 |
|
8.2 |
Graphic Sequences . . . . . . . . . . . . . . . . . . |
92 |
||
|
3.3 |
Boolean Algebras and Boolean Operations . . . . . . |
31 |
|
8.3 |
Connectivity . . . . . . . . . . . . . . . . . . . . . |
93 |
||
|
3.4 |
Sum of Products and Products of Sums . . . . . . . . |
33 |
|
8.4 |
Traversability . . . . . . . . . . . . . . . . . . . . . |
93 |
||
|
3.5 |
Logic Puzzles . . . . . . . . . . . . . . . . . . . . . |
34 |
|
8.5 |
Planarity . . . . . . . . . . . . . . . . . . . . . . . . |
95 |
||
|
Homework . . . . . . . . . . . . . . . . . . . . . . . . . . |
36 |
|
Homework . |
. . . . . . . . . . . . . . . . . . . . . . . . . |
97 |
|||
|
Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . |
36 |
|
Answers . . |
. . . . . . . . . . . . . . . . . . . . . . . . . |
97 |
|||
Preface
These notes started in the Spring of 2004, but contain material that I have used in previous years.
I would appreciate any comments, suggestions, corrections, etc., which can be addressed at the email below.
David A. Santos dsantos@ccp.edu
Things to do:
• Weave functions into counting, a` la twelfold way. . .
iii
iv
Copyright c 2007 David Anthony SANTOS. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled “GNU Free Docume ntation License”.