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
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