The Handbook of Discrete and Combinatorial Mathematics Book

1	Foundations	1
1.1	Propositional and Predicate Logic	12
1.2	Set Theory	21
1.3	Functions	31
1.4	Relations	40
1.5	Proof Techniques	50
1.6	Axiomatic Program Verification	61
1.7	Logic-Based Computer Programming Paradigms	67
2	Counting Methods	81
2.1	Summary of Counting Problems	84
2.2	Basic Counting Techniques	90
2.3	Permutations and Combinations	96
2.4	Inclusion/Exclusion	107
2.5	Partitions	113
2.6	Burnside/Polya Counting Formula	120
2.7	Mobius Inversion Counting	127
2.8	Young Tableaux	129
3	Sequences	135
3.1	Special Sequences	138
3.2	Generating Functions	171
3.3	Recurrence Relations	178
3.4	Finite Differences	189
3.5	Finite Sums and Summation	195
3.6	Asymptotics of Sequences	201
3.7	Mechanical Summation Procedures	204
4	Number Theory	213
4.1	Basic Concepts	219
4.2	Greatest Common Divisors	226
4.3	Congruences	231
4.4	Prime Numbers	236
4.5	Factorization	255
4.6	Arithmetic Functions	259
4.7	Primitive Roots and Quadratic Residues	268
4.8	Diophantine Equations	281
4.9	Diophantine Approximation	289
4.10	Quadratic Fields	295
5	Algebraic Structures	299
5.1	Algebraic Models	305
5.2	Groups	307
5.3	Permutation Groups	319
5.4	Rings	323
5.5	Polynomial Rings	329
5.6	Fields	331
5.7	Lattices	341
5.8	Boolean Algebras	344
6	Linear Algebra	355
6.1	Vector Spaces	361
6.2	Linear Transformations	371
6.3	Matrix Algebra	377
6.4	Linear Systems	392
6.5	Eigenanalysis	405
6.6	Combinatorial Matrix Theory	417
7	Discrete Probability	427
7.1	Fundamental Concepts	432
7.2	Independence and Dependence	435
7.3	Random Variables	441
7.4	Discrete Probability Computations	448
7.5	Random Walks	452
7.6	System Reliability	459
7.7	Discrete-Time Markov Chains	468
7.8	Queueing Theory	477
7.9	Simulation	484
8	Graph Theory	495
8.1	Introduction to Graphs	509
8.2	Graph Models	525
8.3	Directed Graphs	526
8.4	Distance, Connectivity, Traversability	539
8.5	Graph Invariants and Isomorphism Types	549
8.6	Graph and Map Coloring	557
8.7	Planar Drawings	567
8.8	Topological Graph Theory	574
8.9	Enumerating Graphs	580
8.10	Algebraic Graph Theory	586
8.11	Analytic Graph Theory	590
8.12	Hypergraphs	595
9	Trees	603
9.1	Characterizations and Types of Trees	607
9.2	Spanning Trees	616
9.3	Enumerating Trees	622
10	Networks and Flows	629
10.1	Minimum Spanning Trees	633
10.2	Matchings	641
10.3	Shortest Paths	652
10.4	Maximum Flows	663
10.5	Minimum Cost Flows	673
10.6	Communication Networks	683
10.7	Difficult Routing and Assignment Problems	692
10.8	Network Representations and Data Structures	706
11	Partially Ordered Sets	717
11.1	Basic Poset Concepts	724
11.2	Poset Properties	738
12	Combinatorial Designs	753
12.1	Block Designs	759
12.2	Symmetric Designs & Finite Geometries	770
12.3	Latin Squares and Orthogonal Arrays	778
12.4	Matroids	786
13	Discrete and Computational Geometry	797
13.1	Arrangements of Geometric Objects	805
13.2	Space Filling	824
13.3	Combinatorial Geometry	830
13.4	Polyhedra	839
13.5	Algorithms and Complexity in Computational Geometry	844
13.6	Geometric Data Structures and Searching	853
13.7	Computational Techniques	861
13.8	Applications of Geometry	867
14	Coding Theory and Cryptology	889
14.1	Communication Systems and Information Theory	896
14.2	Basics of Coding Theory	900
14.3	Linear Codes	903
14.4	Bounds for Codes	915
14.5	Nonlinear Codes	917
14.6	Convolutional Codes	918
14.7	Basics of Cryptography	923
14.8	Symmetric-Key Systems	927
14.9	Public-Key Systems	935
15	Discrete Optimization	955
15.1	Linear Programming	959
15.2	Location Theory	986
15.3	Packing and Covering	996
15.4	Activity Nets	1006
15.5	Game Theory	1016
15.6	Sperner's Lemma and Fixed Points	1027
16	Theoretical Computer Science	1039
16.1	Computational Models	1048
16.2	Computability	1062
16.3	Languages and Grammars	1066
16.4	Algorithmic Complexity	1077
16.5	Complexity Classes	1085
16.6	Randomized Algorithms	1091
17	Information Structures	1101
17.1	Abstract Datatypes	1108
17.2	Concrete Data Structures	1117
17.3	Sorting and Searching	1125
17.4	Hashing	1139
17.5	Dynamic Graph Algorithms	1142
	Biographies	1153
	Index	1173