Combinatorics

Cover......Page 1
Contents......Page 8
Preface......Page 10
The Mathematics of Choice......Page 14
1.1.1 Fundamental Counting Principle. Consider a (finite) sequence of deci-sions.......Page 15
1.1.3 Example. After cancellation,......Page 18
1.1. EXERCISES......Page 19
1.2.1 Example. By definition, there are C ð 5 2 Þ ways to select two elements......Page 23
1.2.3 The Second Counting Principle. If a set can be expressed as the disjoint......Page 24
1.2.4 Example. In the basic version of poker, each player is dealt five cards (as......Page 27
1.2.5 Example. The game of bridge uses the same 52 cards as poker. The......Page 28
1.2. EXERCISES......Page 29
*1.3. ELEMENTARY PROBABILITY......Page 34
1.3.2 Example. A popular game at charity fundraisers is Chuck- a- Luck. The......Page 35
1.3.3 Example. If 10 (fair) coins are tossed, what is the probability that half of......Page 36
1.3.4 Definition. A nonempty finite set E of equally likely outcomes is called a......Page 37
1.3.9 Example. Suppose a single (fair) die is rolled twice. What is the probabil-ity......Page 38
1.3.10 Definition. Let E be a fixed but arbitrary sample space. If A and B are......Page 39
1.3.14 Example. Suppose a card is drawn from a standard 52- card deck. Let K......Page 40
1.3.16 Example. In the popular game Yahtzee, five dice are rolled in hopes of......Page 41
1.3. EXERCISES......Page 42
*1.4. ERROR- CORRECTING CODES......Page 46
1.4.3 Definition. An r- error- correcting code is one for which nearest- neighbor......Page 47
1.4.6 Example. The code fg 00000 11111 , is evidently a (5, 2, 5) code. While......Page 48
1.4.9 Example. Let C be a ð 10 M 7 Þ code and suppose c 2 C. Because there......Page 49
1.4.11 Example. Suppose you were asked to design a three- error- correcting......Page 50
1.4.13 Definition. An n M d code is perfect if 2 M C n 0 ð Þ ¼ ½ ð Þþ......Page 51
1.4. EXERCISES......Page 52
1.5. COMBINATORIAL IDENTITIES......Page 56
1.5.3 Definition. Let Cn be the n n Pascal matrix whose ð i j Þ -entry is bino-mial......Page 62
1.5.7 Example. When n ¼ 4,......Page 63
1.5.9 Example. With n ¼ 5, Lemma 1.5.8 becomes......Page 64
1.5. EXERCISES......Page 65
1.6. FOUR WAYS TO CHOOSE......Page 69
1.6.4 Example. Door prizes are a common feature of fundraising luncheons.......Page 70
1.6.6 Example. In how many ways can r ¼ 10 items be chosen from......Page 71
1.6.8 Example. Let’s return to the door prizes of Example 1.6.4, but, this time,......Page 72
1.6.12 Example. The C ð 6 1 3 1 Þ ¼ C ð 5 2 Þ ¼ 10 three- part compositions......Page 73
1.6.15 Example. Some people are suspicious when consecutive integers occur......Page 74
1.6. EXERCISES......Page 75
1.7. THE BINOMIAL AND MULTINOMIAL THEOREMS......Page 79
1.7.4 Example. What is the coefficient of xy in the expansion of 1 x y ? ð þ þ Þ......Page 82
1.7.8 Example. The fifth power of a three- term sum was expanded in......Page 85
1.7. EXERCISES......Page 86
1.8.2 Example. The number 6 is said to be perfect because it is the sum of its......Page 89
1.8.4 Example. The three- part partitions of 6 are [4, 1, 1], [3, 2, 1], and [2, 2, 2].......Page 90
1.8.8 Definition. Denote the number of partitions of n by p ð n Þ ¼ p1 ð n Þþ......Page 91
1.8.9 Definition. The conjugate of p n is the partition p n whose jth part is......Page 92
1.8.13 Definition. Let k and n be positive integers. Suppose p is an m- part parti-tion......Page 93
1.8.14 Example. From Fig. 1.8.2, there are p1 ð 6 Þþ p2 ð 6 Þþ p3 ð 6 Þ ¼ 1 þ 3 þ......Page 94
1.8. EXERCISES......Page 95
1.9. ELEMENTARY SYMMETRIC FUNCTIONS......Page 100
1.9.3 Example. Suppose f x x x 2x 2. Then, counting multiplicities, ð Þ ¼ þ þ......Page 101
1.9.5 Example. If ai ¼ i, 1 i 4, then......Page 102
1.9.7 Definition. The elementary number......Page 103
1.9.10 Definition. The minimal symmetric polynomial corresponding to ½ t is......Page 106
1.9.13 Example. Let’s see how to express elementary symmetric functions as......Page 107
1.9.15 Example. The first four of Newton’s identities are equivalent to......Page 108
1.9. EXERCISES......Page 109
*1.10. COMBINATORIAL ALGORITHMS......Page 113
1.10.4 Definition. Let X x1 x2 . . . xp and Y y1 y2 . . . yq be words containing p ¼ ¼......Page 118
1.10.6 Example. In the spirit of Example 1.10.5, consider the 4 ¼ 24 four-letter......Page 119
1.10.9 Example. The conversion of Algorithm 1.10.7 in Example 1.10.8 was......Page 121
1.10.10 Example. A systematic listing of the seven partitions of 5 might be......Page 122
1.10. EXERCISES......Page 124
2.1. STIRLING NUMBERS OF THE SECOND KIND......Page 130
2.1.3 Example. The set of all possible functions from f 1 2 3 g into f 1 2 g is......Page 131
2.1.7 Definition. Denote by Qm Fm the set of (strictly) increasing func-tions,......Page 132
2.1.11 Definition. If y 1 2 . . . ; n and f Fm , then f y x : f x y}. 2f g 2 ð Þ ¼ f ð Þ ¼......Page 133
2.1.15 Example. Two partitions are equal if and only if they have the same......Page 134
2.1.18 Example. In Example 2.1.15 we saw, e. g., that S ð 3 2 Þ ¼ 3. the two-block......Page 135
2.1.21 Example. Observe that......Page 137
2.1. EXERCISES......Page 138
2.2. BELLS, BALLS, AND URNS......Page 141
2.2.1 Example. Let’s confirm Equation (2.4). From Fig. 1.9.2,......Page 142
2.2.6 Definition. The Bell numbers are defined by B0 1 and ¼......Page 145
2.2.8 Definition. Let S be a set. A binary relation on S is an equivalence......Page 146
2.2.10 Example. In how many ways can four labeled balls be distributed among......Page 147
2.2.13 Example. In how many ways can five labeled balls be distributed among......Page 148
2.2. EXERCISES......Page 150
2.3. THE PRINCIPLE OF INCLUSION AND EXCLUSION......Page 153
2.3.3 Definition. A permutation with no fixed points is called a derangement.......Page 154
2.3.4 Example. If A ¼ f 1 2 3 4 g , B ¼ f 3 4 5 6 g , and C ¼ f 2 4 6 7 g , then......Page 155
2.3.5 Principle of Inclusion and Exclusion (PIE). If A1 A2 . . . ; An are finite......Page 156
2.3.7 Example. From Equation (2.18),......Page 158
2.3.8 Example. Let F ð p Þ be the number of fixed points of p 2 S3 ¼ fð 1 2 3 Þ ;......Page 159
2.3.10 Example. The positive integers less than 9 and relatively prime to 9......Page 160
2.3.12 Example. A favorite number of the Babylonians was 60 2 3 5. ¼......Page 161
2.3. EXERCISES......Page 162
2.4. DISJOINT CYCLES......Page 165
2.4.3 Example. Suppose p ¼ ð 16 Þð 24 Þð 357 Þ and q ¼ ð 124 Þð 357 Þð 6 Þ . Then......Page 168
2.4.7 Example. Using disjoint cycle notation, S3 ¼ fð 1 Þð 2 Þð 3 Þ ; ð 1 Þð 23 Þ ;......Page 169
2.4.10 Example. How many permutations in S12 have cycle type 3 ; 2 ½ ¼......Page 170
2.4.11 Example. Of the permutations in S7 , how many have disjoint cycle......Page 171
2.4.12 Definition. The number of permutations in Sm whose disjoint cycle......Page 172
2.4. EXERCISES......Page 173
2.5. STIRLING NUMBERS OF THE FIRST KIND......Page 174
2.5.3 Example. From Fig. 2.5.2, s ð 6 2 Þ ¼ 274. By Equation (2.28), s ð 6 2 Þ is......Page 177
2.5.7 Example. Consider the 5 5 matrix F5 whose ð i j Þ -entry is the Stirling......Page 180
2.5. EXERCISES......Page 183
3.1.1 Definition. Let f : D ! R be a function. The image of f is the set......Page 188
3.1.3 Example. Suppose f ¼ ð 3 2 1 1 2 Þ2 F5 and g ¼ ð 2 1 1 Þ2 F3 .Then......Page 189
3.1.4. Definition. Suppose f : D ! R and g : R ! D are functions. Then g is......Page 190
3.1.6 Definition. Let em 2 Sm be the function defined by em ð i Þ ¼ i 1 i m.......Page 191
3.1.9 Example. Let p 1524 3 and q 143 25 . Then p 4251 3 ¼ ð Þð Þ ¼ ð Þð Þ ¼ ð Þð Þ ¼......Page 192
3.1.11 Convention. If f ; g 2 Sm, then the composition g f ¼ gf is also known......Page 193
3.1.15 Definition. Let G be a (nonempty) closed subset of Sm .ThenG is a......Page 194
3.1. EXERCISES......Page 195
3.2.1 Example. A Cayley table for S3 with the 1- cycles suppressed can be found......Page 197
3.2.2 Definition. A cycle is nontrivial if its length is greater than 1. A......Page 198
3.2.4 Example. Let p ¼ ð 123456 Þ2 Sm (where m 6). Then (check the com-putations)......Page 199
3.2.7 Example. Let f ¼ ð 3 8 5 6 7 2 9 4 1 Þ2 S9 . Apart from establishing......Page 200
3.2.10 Example. If o p k, then p em ,so ð Þ ¼ ¼......Page 201
3.2.13 Definition. Let G be a permutation group of degree m. Thestabilizer......Page 202
3.2.17 Definition. Let G be a permutation group of degree m and suppose......Page 203
3.2.20 Example. Let G ¼ f e4 ð 12 Þ ; ð 34 Þ ; ð 12 Þð 34 Þg . (Confirm that G is closed......Page 204
3.2. EXERCISES......Page 205
3.3. BURNSIDE’S LEMMA......Page 207
3.3.4 Example. If G ¼ f e4 ð 12 Þ ; ð 34 Þ ; ð 12 Þð 34 Þg , then O1 ¼ f p ð 1 Þ : p 2 G g ¼......Page 208
3.3.6 Example. While the group......Page 209
3.3.11 Example. Because Sm is transitive, it has just one orbit. It follows from......Page 210
3.3.13 Example. From Example 3.3.4, the orbits of G ¼ f e4 ð 12 Þ ; ð 34 Þ ;......Page 211
3.3.14 Definition. Let G be a subgroup of Sm . Suppose 1 r m. ThenG is......Page 212
3.3.17 Example. Let’s see what we get when we average the fourth powers of......Page 213
3.3. EXERCISES......Page 216
3.4. SYMMETRY GROUPS......Page 219
3.4.1 Example. Suppose we follow 90 clockwise rotation p ¼ ð 1243 Þ with q, a......Page 221
3.4.3 Definition. Let G be a subgroup of Sm. If it is possible to label some object......Page 222
3.4.4 Example. Let’s say a die (numbered as in Fig. 3.4.4) is in standard......Page 223
3.4.5 Example. As a permutation of die numbered faces, p ¼ ð 2453 Þ2 S6 is a......Page 225
3.4.6 Example. Whatever its manifestation, the octahedral group G contains......Page 226
3.4. EXERCISES......Page 227
3.5. COLOR PATTERNS......Page 231
3.5.1 Definition. Denote by Cm (not to be confused with C ð m n Þ ) the set of all......Page 232
3.5.5 Example. Suppose each face of a cube is painted red, white, or blue.......Page 236
3.5. EXERCISES......Page 237
3.6. PO LYA’S THEOREM......Page 241
3.6.1 Definition. Treating the colors x1 x2 . . . ; xn that comprise the range of......Page 243
3.6.4 Definition. Suppose G is a permutation group of degree m. Let P1 P2 . . . ;......Page 244
3.6.6 Example. Let’s apply Po´lya’s theorem to red– white– blue colorings of the......Page 247
3.6.7 Example. Let’s work out the pattern inventory for the 57 red– white– blue......Page 248
3.6. EXERCISES......Page 250
3.7. THE CYCLE INDEX POLYNOMIAL......Page 254
3.7.2 Example. If G ¼ f e4 ð 12 Þ ; ð 34 Þ ; ð 12 Þð 34 Þg , then......Page 255
3.7.3 Definition. To simplify the notation, denote the cycle index polynomial......Page 256
3.7.5 Example. From Equation (3.58),......Page 257
3.7.7 Definition. The mth homogeneous symmetric function Hm ð x1 x2 . . . ; xn Þ......Page 258
3.7.11 Definition. Let V 1 2 . . . ; m , and define V to be the family of all ¼ f g......Page 259
3.7.12 Example. If m 4, then V 1 2 ; 1 3 ; 1 4 ; 2 3 ; 2 4 ; ¼ ¼ ff g f g f g f g f g......Page 260
3.7. EXERCISES......Page 261
4.1. DIFFERENCE SEQUENCES......Page 266
4.1.2 Definition. The sequence f an g is arithmetic if, for all n 0, the difference......Page 267
4.1.3 Definition. Let f an g be a fixed but arbitrary sequence. Its difference......Page 268
4.1.4 Example. The difference array for n is f g......Page 269
4.1.9 Example. Consider the sequence f an g the first few terms of which are......Page 271
4.1.12 Example. Let m be a fixed positive integer and f an g be the sequence......Page 274
4.1.13 Example. Perhaps the techniques of this section can be made to yield......Page 275
4.1. EXERCISES......Page 276
4.2.2 Definition. The (ordinary) generating function for the sequence f an g is......Page 281
4.2.3 Definition. A formal power series in x is an infinite sum of the form......Page 284
4.2.5 Definition. Let g ð x Þ and h ð x Þ be formal power series. If g ð x Þ h ð x Þ ¼ 1, then......Page 285
4.2.8 Example. For a fixed but arbitrary positive integer m, let gm ð x Þ be the gen-erating......Page 287
4.2.10 Example. Consider the sequence......Page 289
4.2.13 Example. Let a, b, and c be the lengths of the sides of a triangle. Then......Page 292
4.2. EXERCISES......Page 294
4.3. APPLICATIONS OF GENERATING FUNCTIONS......Page 297
4.3.2 Example. If m is a positive integer, then, taking u ¼ m,......Page 298
4.3.4 Example. Suppose f x x 1 . From computations summarized in ð Þ ¼ ð þ Þ......Page 299
4.3.6 Example. From Equation (4.35),......Page 301
4.3.8 Example. The coefficient of x in the infinite product......Page 302
4.3.9 Example. In how many ways can change be made for a dollar? Not......Page 303
4.3.10 Example. The p 6 11 partitions of 6 are 6 ; 5 1 ; 4 2 ; 4 1 ; 3 ; ð Þ ¼ ½ ½ ½ ½ ½......Page 304
4.3.11 Example. Let podd ð n Þ be the number of partitions of n each of whose......Page 305
4.3.14 Example. Apart from historical footnotes, what good is Equation (4.47)?......Page 307
4.3. EXERCISES......Page 308
4.4. EXPONENTIAL GENERATING FUNCTIONS......Page 314
4.4.1 Definition. The exponential generating function for the sequence f an g is......Page 316
4.4.3 Example. Of what use is the formula exp e 1 ? Observe that ð Þ......Page 317
4.4.4 Example. Without recognizing them as such, we have already seen many......Page 318
4.4.8 Example. If the truth be known, it is a rare sequence for which even......Page 322
4.4.9 Definition. The Dirichlet generating function of an is the formal series f g......Page 323
4.4.10 Example. Let an be the trivial sequence defined by an 1 for all n. Its f g ¼......Page 324
4.4.15 Lemma. Let f be a multiplicative number- theoretic function. If......Page 325
4.4.18 Example. The multiplicative number- theoretic Mo¨bius function m is......Page 326
4.4.20 Example. Let s ð n Þ ¼ d, the sum of the divisors of n. (Then, e. g., n is P......Page 327
4.5. RECURSIVE TECHNIQUES......Page 333
4.5.2 Example. As we saw in Theorem 2.2.7, the Bell numbers satisfy the recur-rence......Page 334
4.5.4 Example. Consider the sequence......Page 335
4.5.5 Definition. The characteristic polynomial afforded by the homogeneous......Page 336
4.5.9 Example. Consider the sequence f an g defined by a0 ¼ 11, a1 ¼ 6, a2 ¼ 18,......Page 338
4.5.10 Example. Consider a recurrence of the form an ¼ an þ w ð n Þ , n 1,......Page 339
4.5.11 Example. Consider the sequence......Page 340
4.5.12 Example. Consider the sequence defined by a0 ¼ 9, a1 ¼ 17, a2 ¼ 24, and......Page 341
4.5.13 Example. Let f bn g be the sequence defined by b0 ¼ 9, b1 ¼ 17, b2 ¼ 24,......Page 342
4.5.15 Example. Consider the sequence f an g defined by a0 ¼ 3 andan ¼ 3an þ......Page 343
4.5. EXERCISES......Page 344
Enumeration in Graphs......Page 350
5.1.2 Definition. A graph consists of two things, a nonempty finite set V and a......Page 351
5.1.6 Example. If G1 and G2 are the graphs in Examples 5.1.3 and 5.1.4, respec-tively,......Page 352
5.1.8 Example. Take another look at the illustration of graph G2 in Fig. 5.1.2.......Page 353
5.1.9 Definition. Let G ¼ ð V E Þ be a graph. Suppose v 2 V. The degree of v,......Page 354
5.1.14 Example. In Fig. 5.1.3, G2 is connected but G1 is not. A little care should......Page 355
5.1.18 Example. The graphs illustrated in Fig. 5.1.6 are both complementary......Page 356
5.1. EXERCISES......Page 357
*5.2. EDGE COLORINGS AND RAMSEY THEORY......Page 360
5.2.1 Definition. Let G ¼ ð V E Þ and H ¼ ð W F Þ be graphs. If W V and......Page 361
5.2.2 Definition. Let s and t be positive integers. The Ramsey number N s t is ð Þ......Page 362
5.2.6 Example. The 11 nonisomorphic graphs on four vertices from Fig. 5.1.5......Page 364
5.2.8 Example. If n ¼ 4 then, from Equation (3.60),......Page 365
5.2.9 Example. From Example 3.7.16, the cycle index polynomial for S is......Page 366
5.2. EXERCISES......Page 367
5.3.4 Definition. Suppose e ¼ f u v g is an edge of G ¼ ð V E Þ . The edge sub-graph......Page 370
5.3.6 Example. Let’s use chromatic reduction to work out p ð G r Þ for the graph......Page 371
5.3.10 Definition. If G1 ¼ ð V1 E1 Þ and G2 ¼ ð V2 E2 Þ are graphs on disjoint......Page 373
5.3.14 Definition. If G1 and G2 are graphs on disjoint sets of vertices, their join......Page 374
5.3.15 Definition. Suppose k 3. A cycle in G of length k is a sequence of......Page 375
5.3.22 Example. Graphs G and H in Figure 5.3.5 are two (nonisomorphic)......Page 377
5.3.24 Example. The graph G illustrated in Fig. 5.3. 6 is an overlap of......Page 378
5.3. EXERCISES......Page 379
*5.4. PLANAR GRAPHS......Page 385
5.4.1 Definition. A graph is planar if it can be illustrated in the plane in such a......Page 386
5.4.5 Definition. Graphs G1 and G2 are homeomorphic if they have isomorphic......Page 388
5.4.10 Example. It is frequently convenient to draw G right on top of G. In......Page 391
5.4. EXERCISES......Page 392
5.5.4 Definition. Let G be a graph on n vertices. A perfect matching is a......Page 396
5.5.7 Example. From Example 5.5.5, the matching polynomial M ð C6 x Þ ¼......Page 397
5.5.8 Definition. Suppose u 2 V, where G ¼ ð V E Þ is a graph with at least two......Page 398
5.5.13 Example. Let’s compute the matching polynomial of Kn . From Equation......Page 399
5.5.14 Definition. Let G ¼ ð V E Þ be a graph with vertex set V ¼ f 1 2 . . . ; n g .......Page 400
5.5.19 Example. If G ¼ K3 ¼ C3 then......Page 402
5.5. EXERCISES......Page 403
5.6. ORIENTED GRAPHS......Page 407
5.6.3 Definition. A directed path of length r in the oriented graph G is a path......Page 408
5.6.8 Definition. Suppose G ¼ ð V E Þ is an oriented graph with vertex set......Page 409
5.6.9 Example. Let G ¼ K4, numbered and oriented as in Fig. 5.6.1a, following.......Page 410
5.6.13 Example. If H is the graph in Fig. 5.6.2a, then......Page 411
5.6.15 Definition. Let H ¼ ð W F Þ be a subgraph of G ¼ ð V E Þ .IfW ¼ V, then......Page 412
5.6.18 Example. If H is the graph in Fig. 5.6.2a, then, by Example 5.6.16, the......Page 413
5.6.20 Example. Computations show that the (Laplacian) characteristic polyno-......Page 414
5.6.23 Definition. Suppose ð a Þ ¼ ð a1 a2 . . . ; as Þ and ð b Þ ¼ ð b1 b2 . . . ; bt Þ are......Page 415
5.6.24 Example. The degree sequence for the graph H in Fig. 5.6.2a is d ð H Þ ¼......Page 416
5.6. EXERCISES......Page 417
5.7.1 Definition. Partition p is graphic if there exists a graph G with degree......Page 421
5.7.2 Definition. If p k, the trace of p is f ð p Þ ¼ o ðf r : pr r gÞ .......Page 422
5.7.4 Example. Consider the partition t ¼ ½ 5 4 3 3 2 1 . Because t 18, the......Page 423
5.7.6 Definition. Suppose p k. Let r ð p Þ be the partition whose parts are the......Page 424
5.7.11 Example. Consider the partition t 5 4 3 ; 2 1 in Example 5.7.4. ¼ ½......Page 425
5.7.13 Definition. A threshold graph is one whose degree sequence is, apart......Page 426
5.7.16 Example. The 12 nonisomorphic connected threshold graphs with......Page 428
5.7. EXERCISES......Page 429
Codes and Designs......Page 434
6.1. LINEAR CODES......Page 435
6.1.5 Example. Among the linear codes is F , the set of all 2 binary words of......Page 436
6.1.6 Definition. If S is a nonempty subset of F , the subspace generated (or......Page 437
6.1.9 Example. Consider the (3,4,1) linear code C ¼ f 000 001 100 101 g .......Page 438
6.1.17 Example. Let’s return to Example 6.1. 12, where S ¼ f 000 101 010 g......Page 439
6.1.19 Example. Let B ¼ f 11010 01101 01110 g . We claim that B is linearly......Page 440
6.1.20 Definition. Let B be a fixed but arbitrary basis of the linear n 2 ; d code ð Þ......Page 442
6.1. EXERCISES......Page 443
6.2. DECODING ALGORITHMS......Page 445
6.2.3 Example Definition 6.2.1 gives an implicit (back- door) description of......Page 446
6.2.4 Example. To find the codeword c 2 H3 nearest to v ¼ 0101100, observe......Page 448
6.2.8 Definition. Let H be a fixed but arbitrary parity check matrix for the linear......Page 449
6.2.9 Example. From Example 6.2.4, with respect to H3 the syndrome of......Page 450
6.2.10 Definition. Let H be a fixed but arbitrary parity check matrix for the......Page 451
6.2.13 Example. Suppose S ¼ f 11100 01011 01110 11001 g . Let C ¼ L ð S Þ .......Page 452
6.2.15 Definition. A systematic linear code is one that has a generating matrix......Page 454
6.2.17 Example. This section begain with the construction of Hamming codes......Page 455
6.2. EXERCISES......Page 457
6.3. LATIN SQUARES......Page 460
6.3.1 Definition. A magic square of order n is an n n array in which the......Page 461
6.3.3 Example. Matrices A ¼ ð aij Þ and B ¼ ð bij Þ in Fig. 6.3.6 are Latin squares......Page 462
6.3.4 Definition. Let A aij and B bij be Latin squares of order n based ¼ ð Þ ¼ ð Þ......Page 463
6.3.5 Example. The Latin squares of order 4 exhibited in Fig. 6.3.6 are ortho-gonal.......Page 464
6.3.10 Definition. A projective plane consists of three things, a set of points, a......Page 466
6.3.15 Example. Together with Axiom 3 of Definition 6.3.10, Corollary 6.3.14......Page 467
6.3.17 Example. In the midst of the proof of Theorem 6.3.16, we evaluated c23......Page 469
6.3.18 Example. Let’s use the mutually orthogonal Latin squares of order 3......Page 470
6.3. EXERCISES......Page 471
6.4.1 Definition. Let P1 P2 . . . ; Pm and L1 L2 . . . ; Lm be the points and lines,......Page 474
6.4.2 Example. The incidence matrix for the plane of order 3 constructed in......Page 475
6.4.5 Example. Given a finite projective plane of order n, let V be its set of......Page 476
6.4.8 Example. Let V ¼ f P1 P2 P3 g be a set of points. If B1 ¼ f P1 P2 g ,......Page 477
6.4.10 Definition. A balanced incomplete block design is symmetric if v ¼ b,......Page 478
6.4.14 Example. If A is the ð 0 1 Þ -matrix exhibited in Fig. 6.4. 3, then computa-tions......Page 480
6.4.16 Example. The unique normalized Hadamard matrices of orders 1 and 2......Page 481
6.4.20 Example. When t ¼ 2, the parameters from Theorem 6.4.19 are ð 7 3 1 Þ .......Page 483
6.4. EXERCISES......Page 484
A1.1 Example. Suppose p x x x 6x 2x 9 and c 3. Dividing ð Þ ¼ þ þ ¼......Page 490
BookmarkTitle:......Page 0
A1.3 Definition. Suppose a ¼ ½ a1 a2 . . . ; a and b ¼ ½ b1 ; b2 ; . . . ; bs are two......Page 493
A1.4 Definition. Suppose a ¼ ½ a1 a2 . . . ; a and b ¼ ½ b1; b2; . . . ; bs are two......Page 495
Sorting Algorithms......Page 498
A2.4 Example. How does insertion sorting compare with smallest first sorting?......Page 501
A2.5 Definition. Suppose f and g are real- valued functions defined on the set of......Page 502
A2.7 Example. Nearly three times as long as insertion (Algorithm A2.3), fast......Page 503
A2.9 Example. Zircon is a mineral whose appearance can vary from colorless to......Page 505
EXERCISES A2......Page 506
Matrix Theory......Page 508
A3.4 Definition. Suppose A is an n n matrix. If f ; g 2 Qt , denote by A ½ f j g......Page 512
SPECIAL TOPICS......Page 514
1.1. The Fundamental Counting Principle......Page 516
1.3. Elementary Probability......Page 517
1.4. Error- Correcting Codes......Page 518
1.5. Combinatorial Identities......Page 519
1.6. Four Ways to Choose......Page 520
1.7. The Binomial and Multinomial Theorems......Page 521
1.8. Partitions......Page 522
1.10. Combinatorial Algorithms......Page 523
2.1. Stirling Numbers of the Second Kind......Page 525
2.2. Bells, Balls, and Urns......Page 526
2.3. The Principle of Inclusion and Exclusion......Page 528
2.5. Stirling Numbers of the First Kind......Page 529
3.2. Permutation Groups......Page 531
3.3. Burnside’s Lemma......Page 533
3.5. Color Patterns......Page 534
3.6. Po´lya’s Theorem......Page 535
3.7. The Cycle Index Polynomial......Page 536
4.1. Difference Sequences......Page 537
4.2. Ordinary Generating Functions......Page 538
4.3. Applications of Generating Functions......Page 539
4.4. Exponential Generating Functions......Page 540
4.5. Recursive Techniques......Page 541
5.1. The Pigeonhole Principle......Page 542
5.3. Chromatic Polynomials......Page 543
5.5. Matching Polynomials......Page 545
5.6. Oriented Graphs......Page 547
5.7. Graphic Partitions......Page 548
6.2. Decoding Algorithms......Page 549
6.3. Latin Squares......Page 550
6.4. Balanced Incomplete Block Designs......Page 551
Appendix A2 Sorting Algorithms......Page 552
Index of Notation......Page 554
Index......Page 560