Check nearby libraries
Buy this book
![Loading indicator](/images/ajax-loader-bar.gif)
This edition doesn't have a description yet. Can you add one?
Check nearby libraries
Buy this book
![Loading indicator](/images/ajax-loader-bar.gif)
Previews available in: English
Showing 5 featured editions. View all 5 editions?
Edition | Availability |
---|---|
1 |
zzzz
Libraries near you:
WorldCat
|
2
Discrete Mathematics (Oxford Science Publications)
September 2, 1993, Oxford University Press, USA
in English
0198534272 9780198534273
|
aaaa
Libraries near you:
WorldCat
|
3
Discrete mathematics
1989, Clarendon Press, Oxford University Press
in English
- Rev. ed.
0198534264 9780198534266
|
zzzz
Libraries near you:
WorldCat
|
4 |
zzzz
Libraries near you:
WorldCat
|
5
Discrete mathematics
1985, Clarendon Press, Oxford University Press
in English
0198532520 9780198532521
|
zzzz
Libraries near you:
WorldCat
|
Book Details
Table of Contents
Part I.
Numbers and Counting
Page 1
1.
Integers
Page 3
1.1.
Arithmetic
Page 3
1.2.
Ordering the integers
Page 5
1.3.
Recursive definitions
Page 8
1.4.
The principle of induction
Page 11
1.5.
Quotient and remainder
Page 14
1.6.
Divisibility
Page 17
1.7.
The greatest common divisor
Page 18
1.8.
Factorization into primes
Page 21
1.9.
Miscellaneous exercises
Page 25
2.
Functions and counting
Page 27
2.1.
Functions
Page 27
2.2.
Surjections, injections, bijections
Page 29
2.3.
Counting
Page 33
2.4.
The pigeonhole principle
Page 36
2.5.
Finite or infinite?
Page 38
2.6.
Miscellaneous exercises
Page 42
3.
Principles of counting
Page 44
3.1.
The addition principle
Page 44
3.2.
Counting sets of pairs
Page 46
3.3.
Euler's function
Page 49
3.4.
Functions, words, and selections
Page 52
3.5.
Injections as ordered selections without repetition
Page 54
3.6.
Permutations
Page 55
3.7.
Miscellaneous exercises
Page 59
4.
Subsets and designs
Page 62
4.1.
Binomial numbers
Page 62
4.2.
Unordered selections with repetition
Page 66
4.3.
The binomial theorem
Page 68
4.4.
The sieve principle
Page 71
4.5.
Some arithmetical applications
Page 74
4.6.
Designs
Page 79
4.7.
t-designs
Page 83
4.8.
Miscellaneous exercises
Page 86
5.
Partition, classification, and distribution
Page 89
5.1.
Partitions of a set
Page 89
5.2.
Classification and equivalence relations
Page 92
5.3.
Distributions and the multinomial numbers
Page 95
5.4.
Partitions of a positive integer
Page 100
5.5.
Classification of permutations
Page 101
5.6.
Odd and even permutations
Page 105
5.7.
Miscellaneous exercises
Page 110
6.
Modular arithmetic
Page 113
6.1.
Congruences
Page 113
6.2.
ℤₘ and its arithmetic
Page 115
6.3.
Invertible elements of ℤ
Page 119
6.4.
Cyclic constructions for designs
Page 122
6.5.
Latin squares
Page 126
6.6.
Miscellaneous exercises
Page 129
Part II.
Graphs and Algorithms
Page 131
7.
Algorithms and their efficiency
Page 133
7.1.
What is an algorithm?
Page 133
7.2.
The language of programs
Page 135
7.3.
Algorithms and programs
Page 139
7.4.
Proving that an algorithm is correct
Page 142
7.5.
Efficiency of algorithms
Page 145
7.6.
Growth rates: the O notation
Page 148
7.7.
Comparison of algorithms
Page 150
7.8.
Introduction to sorting algorithms
Page 153
7.9.
Miscellaneous exercises
Page 156
8.
Graphs
Page 158
8.1.
Graphs and their representation
Page 158
8.2.
Isomorphism of graphs
Page 161
8.3.
Valency
Page 163
8.4.
Paths and cycles
Page 165
8.5.
Trees
Page 169
8.6.
Colouring the vertices of a graph
Page 171
8.7.
The greedy algorithm for vertex-colouring
Page 173
8.8.
Miscellaneous exercises
Page 177
9.
Trees, sorting, and searching
Page 180
9.1.
Counting the leaves on a rooted tree
Page 180
9.2.
Trees and sorting algorithms
Page 184
9.3.
Spanning trees and the MST problem
Page 189
9.4.
Depth-first search
Page 193
9.5.
Breadth-first search
Page 197
9.6.
The shortest-path problem
Page 201
9.7.
Miscellaneous exercises
Page 203
10.
Bipartite graphs and matching problems
Page 206
10.1.
Relations and bipartite graphs
Page 206
10.2.
Edge-colourings of graphs
Page 208
10.3.
Application of edge-colouring latin squares
Page 212
10.4.
Matchings
Page 215
10.5.
Maximum matchings
Page 219
10.6.
Transversals for families of finite sets
Page 222
10.7.
Miscellaneous exercises
Page 225
11.
Digraphs, networks, and flows
Page 228
11.1.
Digraphs
Page 228
11.2.
Networks and critical paths
Page 231
11.3.
Flows and cuts
Page 234
11.4.
The max-flow min-cut theorem
Page 237
11.5.
The labelling algorithm for network flows
Page 241
11.6.
Miscellaneous exercises
Page 245
12.
Recursive techniques
Page 248
12.1.
Generalities about recursion
Page 248
12.2.
Linear recursion
Page 250
12.3.
Recursive bisection
Page 253
12.4.
Recursive optimization
Page 255
12.5.
The framework of dynamic programming
Page 258
12.6.
Examples of the dynamic programming method
Page 261
12.7.
Miscellaneous exercises
Page 265
Part III.
Algebraic Methods
Page 269
13.
Groups
Page 271
13.1.
The axioms for a group
Page 271
13.2.
Examples of groups
Page 272
13.3.
Basic algebra in groups
Page 276
13.4.
The order of a group element
Page 278
13.5.
Isomorphism of groups
Page 280
13.6.
Cyclic groups
Page 282
13.7.
Subgroups
Page 285
13.8.
Cosets and Lagrange's theorem
Page 288
13.9.
Characterization of cyclic groups
Page 293
13.10.
Miscellaneous exercises
Page 296
14.
Groups of Permutations
Page 300
14.1.
Definitions and examples
Page 300
14.2.
Orbits and stabilizers
Page 303
14.3.
The size of an orbit
Page 306
14.4.
The number of orbits
Page 309
14.5.
Representation of groups by permutations
Page 313
14.6.
Applications to group theory
Page 316
14.7.
Miscellaneous exercises
Page 318
15.
Rings, fields, and polynomials
Page 321
15.1.
Rings
Page 321
15.2.
Invertible elements of a ring
Page 323
15.3.
Fields
Page 324
15.4.
Polynomials
Page 327
15.5.
The division algorithm for polynomials
Page 330
15.6.
The Euclidean algorithm for polynomials
Page 333
15.7.
Factorization of polynomials in theory
Page 336
15.8.
Factorization of polynomials in practice
Page 338
15.9.
Miscellaneous exercises
Page 341
16.
Finite fields and some applications
Page 344
16.1.
A field with nine elements
Page 344
16.2.
The order of a finite field
Page 346
16.3.
Construction of finite fields
Page 348
16.4.
The primitive element theorem
Page 350
16.5.
Finite fields and latin squares
Page 354
16.6.
Finite geometry and designs
Page 357
16.7.
Projective planes
Page 361
16.8.
Squares in finite fields
Page 364
16.9.
Existence of finite fields
Page 368
16.10.
Miscellaneous exercises
Page 372
17.
Error-correcting codes
Page 375
17.1.
Words, codes, and errors
Page 375
17.2.
Linear codes
Page 379
17.3.
Construction of linear codes
Page 382
17.4.
Correcting errors in linear codes
Page 384
17.5.
Cyclic codes
Page 389
17.6.
Classification and properties of cyclic codes
Page 392
17.7.
Miscellaneous exercises
Page 397
18.
Generating functions
Page 399
18.1.
Power series and their algebraic properties
Page 399
18.2.
Partial fractions
Page 403
18.3.
The binomial theorem for negative exponents
Page 408
18.4.
Generating functions
Page 411
18.5.
The homogeneous linear recursion
Page 414
18.6.
Nonhomogeneous linear recursions
Page 418
18.7.
Miscellaneous exercises
Page 421
19.
Partitions of a positive integer
Page 423
19.1.
Partitions and diagrams
Page 423
19.2.
Conjugate partitions
Page 425
19.3.
Partitions and generating functions
Page 427
19.4.
Generating functions for restricted partitions
Page 431
19.5.
A mysterious identity
Page 433
19.6.
The calculation of p(n)
Page 437
19.7.
Miscellaneous exercises
Page 439
20.
Symmetry and Counting
Page 441
20.1.
The cycle index of a group of permutations
Page 441
20.2.
Cyclic and dihedral symmetry
Page 444
20.3.
Symmetry in three dimensions
Page 448
20.4.
The number of inequivalent colourings
Page 452
20.5.
Sets of colourings and their generating functions
Page 456
20.6.
Pólya's theorem
Page 458
20.7.
Miscellaneous exercises
Page 462
ID Numbers
Community Reviews (0)
Feedback?August 17, 2024 | Edited by MARC Bot | import existing book |
December 19, 2023 | Edited by ImportBot | import existing book |
December 19, 2023 | Edited by ImportBot | import existing book |
August 28, 2020 | Edited by Drini | Edited without comment. |
December 10, 2009 | Created by WorkBot | add works page |