Contents
ix
SECTiOn 4.2 Review
258
ExErCiSES 4.2
259
4.3 PRINCIPLE OF INCLUSION AND
EXCLUSION; PIGEONHOLE
PRINCIPLE
263
Principle of Inclusion and
Exclusion
264
Pigeonhole Principle
269
SECTiOn 4.3 Review
269
ExErCiSES 4.3
270
4.4 PERMUTATIONS AND
COMBINATIONS
272
Permutations
272
Combinations
274
Eliminating Duplicates
277
Permutations and Combinations
with Repetitions
279
Generating Permutations
and Combinations
280
special interest page
Archimedes and the Stomachion
286
SECTiOn 4.4 Review
288
ExErCiSES 4.4
288
4.5 BINOMIAL THEOREM
294
Pascal’s Triangle
294
Binomial Theorem and Its Proof
296
Applying the Binomial Theorem
298
SECTiOn 4.5 Review
299
ExErCiSES 4.5
299
4.6 PROBABILITY
301
Introduction to Finite
Probability
301
Probability Distributions
304
Conditional Probability
306
Bayes’ Theorem
308
Expected Value
310
Binomial Distributions
313
Average Case Analysis of
Algorithms
314
SECTiOn 4.6 Review
315
ExErCiSES 4.6
315
Chapter 4 Review
323
On the Computer
324
CHAPTEr 5
relations, Functions,
and Matrices
327
5.1 RELATIONS
328
Binary Relations
328
Properties of Relations
332
Closures of Relations
334
Partial Orderings
336
Equivalence Relations
339
SECTiOn 5.1 Review
344
ExErCiSES 5.1
345
5.2 TOPOLOGICAL SORTING
356
SECTiOn 5.2 Review
361
ExErCiSES 5.2
362
5.3 RELATIONS AND DATABASES
365
Entity-Relationship Model
365
Relational Model
366
Operations on Relations
369
Null Values and Three-valued Logic 373
Database Integrity
375
SECTiOn 5.3 Review
376
ExErCiSES 5.3
376
5.4 FUNCTIONS
381
Definition
381
Properties of Functions
388
Onto Functions
388
One-to-One Functions
389
Bijections
390
Composition of Functions
390
Inverse Functions
392
Permutation Functions
394
How Many Functions
397
Equivalent Sets
401
SECTiOn 5.4 Review
402
ExErCiSES 5.4
402