596 Index
circuit, 341 congruent, 181 difference, 20
directed, 394 conjunction, 91 relative, 20
circular permutations, 439 conjuncts, (^91) digraph, 393
clause, 125 connected, (^353) directed
cliques, 335 component, (^353) bipartite graph, 393
closed form, 55, 69, 224 constant predicate, 135 circuit, 394
closure constructing permutations, (^446) cycle, 394
rule, 589 contained, 2 edge, 393
reflexive, 173, (^175) continuum, 273 Eulerian circuit, 405
reflexive and transitive, 175 hypothesis, 272 graph, 393
symmetric, 173, 175 contradiction, 106, 108 path, 394
transitive, 175 contrapositive, 25, 108 subgraph, 393
code control structures, 301, 509 trail, 394
comment, (^57) converse, 25 Diricblet drawer principle, 255
code conventions, 57 countable, (^266) discrete, 478
comment, 57 countably infinite, 266 random variable, 520
condition, 57 countably infinite sample space, 491 sample space, 478
loop, 57 counting, (^482) disjoint, 18
recursion, 73 complement, (^443) events, 485, 508
while loop, 57 methods, 482 union, 483
codomain, 221, 222 decomposition into subproblems, disjunction, 91
collision resolution strategy, (^236 444) disjuncts, 91
combination, 440 Counting Principles, (^423) distance
with repetitions, 455 Addition Principle, 426 graphs, 392
combinatorial Multiplication Principle, 424 distribution, 521
circuit, 98 counting problems binomial, 522
identities, 457 counting the complement, 429 hypergeometric, 522
network, 98 cross product, 495 distributive law, 17, 108
proof, 457 event, 500 Distributive Law for Join, 29
combinatorics, (^483) sample space, 495, 496 Distributive Law for Meet, 29
communication channel reliability, size, 496 divide and conquer, 568
514 cross product event solving, 576
commutative law, (^108) probability, 504 divides, 192, 217
Commutative Law for Join, (^29) cubic graph, 335 divisible by, 181
Commutative Law for Meet, 29 cycle, 341 divisor, 4, 39
comparable, 196 directed, 394 domain, 221, 222
complement, 21, 488 double negative, 108
graph, 336 dags, 400
complete, 131, 151 database, 202 edge, 334
bipartite graph, 335 database Cartesian product, 208 directed, 393
graph K., 335 deadlock state, 396 ends, 334
complexity decidable, 318 head, 393
average time, 312 decimal expansion of rational, 257 incident, 393
complexity decision algorithm, 318 tail, 393
if ... then ... else, 552 decision problem, 309 element, 2
repetition, (^306) decision tree, 387 empty relation, 161
selection, 303 decreasing, 238 empty string, 587
sequence, 302 decryption, 236 encryption, 236
space, 312 degree, 291, 334 equal cardinality, 265
time, (^308) DeMorgan's Law equally likely events, 491
component intersection, 23 equijoin, 208
strongly connected, 402, 403 union, 23 equivalence class, 184, 403
composition, 165, 243 density, 479 equivalence proposition, 91
composition of functions, 243 dependent trials, 516, 518 equivalent, 110
computer representation depth first search, 354 Eulerian
sets, 22 tree, (^355) circuit, 362
conclusion, 7, (^91) derangement, 445,469 directed circuit, 405
condition, 57 descendant, 191, (^379) trail, 362, 366
conditional, 91 diagonal argument even integer, 75
conditional probability, 507 Cantor's first, 270 even vertex, 334
Bayes' Rule, 514 Cantor's second, 271 event, 478
frequency interpretation, 510 dictionary order, 194, 446 cross product