Discrete mathematics is an important tool for the investigation of various models of functioning of technical devices, especially in the field of cybernetics. Here the author presents some complex problems of discrete mathematics in a simple and unified form using an original, general combinatorial scheme. Professor Sachkov's aim is to focus attention on results that illustrate the methods described. A distinctive aspect of the book is the large number of asymptotic formulae derived. Professor Sachkov begins with a discussion of block designs and Latin squares before proceeding to treat transversals, devoting much attention to enumerative problems. The main role in these problems is played by generating functions, considered in Chapter 4. The general combinatorial scheme is then introduced and in the last chapter Polya's enumerative theory is discussed. This is an important book for graduate students and professionals that describes many ideas not previously available in English; the author has updated the text and references where appropriate.
Author(s): Vladimir N. Sachkov
Series: Encyclopedia of Mathematics and its Applications 55
Publisher: Cambridge University Press
Year: 1996
Language: English
Pages: 320
Contents......Page 5
Preface......Page 7
Preface to the English edition......Page 9
Introduction......Page 11
1.1.1 Boolean operations on sets......Page 15
1.1.2 Binary correspondences and binary relations......Page 17
1.2.1 Mappings......Page 19
1.2.2 Composition laws......Page 20
1.2.3 Transformations......Page 25
1.2.4 Substitutions......Page 26
1.2.5 Linear transformations of a vector space......Page 27
1.3.1 Configurations......Page 29
1.3.2 Combinations, arrangements, permutations......Page 30
1.3.3 Allocations of particles to cells; urn models......Page 32
1.4.1 Discordant mappings, Latin squares......Page 33
1.4.2 Orthogonal Latin squares......Page 35
1.4.3 The Bose-Stevens method......Page 38
1.5.1 Definition and properties of (v, k, λ)-configurations......Page 39
1.5.2 The Bruck-Chowla-Ryser theorem......Page 41
1.5.3 Perfect difference sets......Page 45
1.5.4 Hadamard matrices and Hadamard configurations......Page 46
1.6.1 Main properties of finite projective planes......Page 50
1.6.2 Orthogonal Latin squares and finite projective planes......Page 51
1.7.1 (b, v, r, k, λ)-configurations......Page 56
1.7.2 Steiner triples......Page 58
1.7.3 Block designs and their applications......Page 59
1.8 Sperner's theorem and completely separating families of sets......Page 61
2.1.1 The main theorems......Page 63
2.1.3 An existence theorem for Latin squares......Page 68
2.1.4 Common transversals......Page 70
2.2.1 Birkhofl s theorem......Page 72
2.2.2 The convex polytope of doubly stochastic matrices......Page 74
2.2.3 Linearly independent permutation matrices......Page 79
2.2.4 König's theorems......Page 81
2.3.1 Probabilistic automata......Page 82
2.3.2 Decomposition......Page 83
2.3.3 Probabilistic transformers......Page 85
2.4.1 Definition and properties of a permanent......Page 87
2.4.3 The ménage problem......Page 89
2.4.4 The Fibonacci numbers......Page 90
2.4.6 The dimer problem......Page 91
2.4.7 König's theorem......Page 94
2.5.1 The permanent of a linear combination of two permutation matrices......Page 96
2.5.2 The permanent of a linear combination of three permutation matrices......Page 97
2.5.3 Matrix factorization......Page 99
2.6.1 Derivation of the formulae......Page 101
2.6.2 A metric in the symmetric group......Page 102
2.6.4 The Ryser formula......Page 103
2.6.5 The Bonferroni inequalities......Page 104
2.7.1 Bounds for the permanents of non-negative matrices......Page 107
2.7.2 Bounds for the permanents of (0,1)-matrices......Page 109
2.7.3 The van der Waerden conjecture......Page 112
3 Generating functions......Page 116
3.1.1 Convergent series......Page 117
3.1.2 The ring of formal power series......Page 119
3.1.3 Incidence algebras......Page 122
3.2.1 The Nörlund and Vandermonde relations......Page 124
3.2.2 Inversion formulae......Page 125
3.2.3 The Appell, Bernoulli, Euler, Hermite polynomials......Page 127
3.2.4 The finite difference operators; de Morgan and Stirling numbers......Page 129
3.2.5 A combinatorial interpretation of Stirling numbers......Page 131
3.2.6 The Euler-Maclaurin summation formula......Page 133
3.2.7 The Bruno and Lagrange formulae......Page 135
3.2.8 Asymptotic formulae......Page 138
3.3.1 Non-regenerative substitutions......Page 139
3.3.2 Inversions......Page 140
3.3.3 Ascents......Page 141
3.3.4 Ascents and descents......Page 142
3.3.5 The Andre problem......Page 144
3.4.1 Gaussian coefficients and Galois numbers......Page 147
3.4.2 Gaussian polynomials......Page 150
3.4.3 The Rota method......Page 152
3.4.4 Partitions of numbers with constraints......Page 153
3.5.1 The Möbius inversion formula......Page 155
3.5.2 The problem on cyclic sequences......Page 158
3.6 Asymptotic behavior of Stirling numbers......Page 160
3.6.1 The basic definitions and results......Page 161
3.6.2 The Jordan formula......Page 162
3.6.3 The first Moser and Wyman formula......Page 164
3.6.4 The second Moser and Wyman formula......Page 171
3.7.1 The saddle point method......Page 172
3.7.2 Asymptotic expansions......Page 174
4.1.1 Basic definitions......Page 179
4.1.2 Graphs with labeled vertices......Page 181
4.1.3 Graphs with labeled edges; graphs with labeled vertices and edges......Page 184
4.1.4 Colored graphs......Page 185
4.2.1 Rooted trees......Page 186
4.2.2 Forests with k disjoined vertices......Page 188
4.2.3 Forests of unrooted trees......Page 190
4.2.5 Unlabeled end vertices......Page 192
4.2.6 A problem on car parking......Page 194
4.2.7 Generation of the symmetric group by transpositions......Page 195
4.2.8 The Hurwitz problem......Page 197
4.2.10 Bichromatic trees......Page 199
4.3.1 Cycles in substitutions......Page 201
4.3.2 Minimal and maximal cycle classes......Page 202
4.4 Generating functions of cycles of substitutions......Page 204
4.4.2 The numbers of substitutions with cycles of even and odd lengths......Page 206
4.4.3 The number of solutions of the equation sᵈ = e......Page 208
4.4.4 Even and odd substitutions......Page 209
4.5.1 Basic definitions......Page 211
4.5.2 Exact formulae......Page 212
4.5.3 Generating functions for mappings with constraints on cycles......Page 214
4.5.4 Generating functions for mappings of bounded height......Page 217
5 The general combinatorial scheme......Page 223
5.1.1 Equivalence of configurations......Page 225
5.1.2 The number of equivalence classes......Page 231
5.1.3 The general combinatorial scheme and its particular cases......Page 236
5.1.4 Non-commutative asymmetric n-basis......Page 237
5.1.5 Commutative asymmetric n-basis......Page 238
5.1.6 Non-commutative symmetric n-basis......Page 239
5.1.7 Commutative symmetric n-basis......Page 241
5.2 Commutative asymmetric n-basis......Page 242
5.2.2 The number of m-samples with restrictions from below......Page 244
5.2.3 The number of m-samples with homogeneous restrictions......Page 245
5.2.4 The number of m-samples with non-homogeneous restrictions......Page 246
5.2.5 Runs......Page 247
5.2.6 Inversions in permutations......Page 248
5.3.1 The main results......Page 249
5.3.2 Proof of the main theorem......Page 250
5.4 Non-commutative asymmetric n-basis......Page 254
5.5 Commutative symmetric n-basis......Page 260
5.6 The Hardy-Ramanujan formula......Page 266
5.7 Non-commutative symmetric n-basis......Page 271
5.8 Asymptotics of the Bell numbers......Page 276
5.9.1 Coverings......Page 278
5.9.2 Minimal coverings......Page 280
5.9.3 Coverings with repetition......Page 281
5.9.4 Minimal coverings with repetition......Page 283
5.9.5 Diagnostics and minimal coverings......Page 284
5.9.6 Algorithms......Page 285
6 Pólya's theorem and its applications......Page 286
6.1.1 Cycle index......Page 287
6.1.2 Burnside's lemma......Page 288
6.1.3 Equivalence classes of families of sets and coverings......Page 291
6.2.1 The main theorem......Page 292
6.2.2 The necklace problem......Page 295
6.2.3 m-samples......Page 296
6.3.1 Cayley's relation......Page 297
6.3.2 Chemical trees......Page 298
6.4.1 Operations on groups of substitutions......Page 300
6.4.3 Weights of classes of functions......Page 303
6.4.4 Equivalence classes of pairs of functions......Page 306
6.4.5 Isomorphism of abstract automata......Page 307
Bibliography......Page 309
Index......Page 317
