应用组合数学（英文版·第2版）

.2.10.4 case 3: distinguishable balls and indistinguishable ceils
2.10.5 case 4: indistinguishable balls and indistinguishable cells
2.10.6 examples
2.11 multinomial coefficients
2.11.1 occupancy problems with a specified distribution
2.11.2 permutations with classes of indistinguishable objects
2.12 complete digest by enzymes
2.13 permutations with classes of indistinguishable objects revisited
2.14 the binomial expansion
2.15 power in simple games
2.15.1 examples of simple games
2.15.2 the shapley-shubik power index
2.15.3 the u.n. security council
2.15.4 bicameral legislatures
2.15.5 cost allocation
2.15.6 charac+eristic functions
2.16 generating permutations and combinations
2.16.1 an algorithm for generating permutations
2.16.2 an algorithm for generating subsets of sets
2.16.3 an algorithm for generating combinations
2.17 inversion distance between permutations
2.18 good algorithms
2.18.1 asymptotic analysis
2.18.2 np-complete problems
2.19 pigeonhole principle and its generalizations
2.19.1 the simplest version of the pigeonhole principle
2.19.2 generalizations and applications of the pigeonhole principle
2.19.3 ramsey numbers additional exercises for chapter 2
references for chapter 2
3 introduction to graph theory
3.1 fundamental concepts
3.1.1 some examples
3.1.2 definition of digraph and graph
3.1.3 labeled digraphs and the isomorphism problem
3.2 connectedness
3.2.1 reaching in digraphs
3.2.2 joining in graphs
3.2.3 strongly connected digraphs and connected graphs
3.2.4 subgraphs
3.2.5 connected components
3.3 graph coloring and its applications
3.3.1 some applications
3.3.2 planar graphs
3.3.3 calculating the chromatic number
3.3.4 2-colorable graphs
3.3.5 graph-coloring variants
3.4 chromatic polynomials
3.4.1 definitions and examples
3.4.2 reduction theorems
3.4.3 properties of chromatic polynomials
3.5 trees
3.5.1 definition of a tree and examples
3.5.2 properties of trees
3.5.3 proof of theorem 3.15
3.5.4 spanning trees
3.5.5 proof of theorem 3.16 and a related result
3.5.6 chemical bonds and the number of trees
3.5.7 phylogenetic tree reconstruction
3.6 applications of rooted trees
3.6.1 definitions
3.6.2 search trees
3.6.3 proof of theorem 3.24
3.6.4 sorting
3.6.5 the periect phylogeny problem
3.7 representing a graph in the computer
3.8 ramsey numbers revisited references for chapter 3
4 relations
4.1 relations
4.1.1 binary relations
4.1.2 properties of relations/patterns in digraphs
4.2 order relations and their variants
4.2.1 defining the concept of order relation
4.2.2 the diagram of an order relation
4.2.3 linear orders
4.2.4 weak orders
4.2.5 stable marriages
4.3 linear extensions of partial orders
4.3.1 linear extensions and dimension
4.3.2 chains and antichains
4.3.3 interval orders
4.4 lattices and boolean algebras
4.4,1 lattices
4.4.2 boolean algebras references for chapter 4
part ii the counting problem
5 generating functions and their applications
5.1 examples of generating functions
5.1.1 power series
5.1.2 generating functions
5.2 operating on generating functions
5.3 applications to counting
5.3.1 sampling problems
5.3.2 a comment on occupancy problems
5.4 the binomial theorem
5.5 exponential generating functions and generating functions for per-mutations
5.5.1 definition of exponential generating function
5.5.2 applications to counting permutations
5.5.3 distributions of distinguishable balls into indistinguishable cells
5.6 probability generating functions
5.7 the coleman and banzhaf power indices references for chapter 5
6 recurrence relations
6.1 some examples
6.1.1 some simple recurrences
6.1.2 fibonacci numbers and their applications
6.1.3 derangements
6.1.4 recurrences involving more than one sequence
6.2 the method of characteristic roots
6.2.1 the case of distinct roots
6.2.2 computation of the kth fibonacci number
6.2.3 the case of multiple roots
6.3 solving recurrences using generating functions
6.3.1 the method
6.3.2 derangements
6.3.3 simultaneous equations for generating functions
6.4 some recurrences involving convolutions
6.4.1 the number of simple, ordered, rooted trees
6.4.2 the ways to multiply a sequence of numbers in a computer
6.4.3 secondary structure in rna
6.4.4 organic compounds built up from benzene rings references for chapter 6
7 the principle of inclusion and exclusion
7.1 the principle and some of its applications
7.1.1 some simple examples
7.1.2 proof of theorem 6.1
7.1.3 prime numbers, cryptography, and sieves
7.1.4 the probabilistic case
7.1.5 the occupancy problem with distinguishable balls and cells
7.1.6 chromatic polynomials
7.1.7 derangements
7.1.8 counting combinations
7.1.9 rook polynomials
7.2 the number of objects having exactly m properties
7.2.1 the main result and its applications
7.2.2 proofs of theorems 7.4 and 7.5 references for chapter 7
the polya theory of counting
8.1 equivalence relations
8.1.1 distinct configurations and databases
8.1.2 definition of equivalence relations
8.1.3 equivalence classes
8.2 permutation groups
8.2.1 definition of a permutation group
8.2.2 the equivalence relation induced by a permutation group
8.2.3 automorphisms of graphs
8.3 burnside's lemma
8.3.1 statement of burnside's lemma
8.3.2 proof of burnside's lemma
8.4 distinct colorings
8.4.1 definition of a coloring
8.4.2 equivalent colorings
8.4.3 graph colorings equivalent under automorphisms
8.4.4 the case of switching functions
8.5 the cycle index
8.5.1 permutations as products of cycles
8.5.2 a special case of p61ya's theorem
8.5.3 graph colorings equivalent under automorphisms revisited
8.5.4 the case of switching functions
8.5.5 the cycle index of a permutation group
8.5.6 proof of theorem 8.6
8.6 polya's theorem
8.6.1 the inventory of colorings
8.6.2 computing the pattern inventory
8.6.3 the case of switching functions
8.6.4 proof of p61ya's theorem references for chapter 8
part iii the existence problem combinatorial designs
9.1 block designs
9.2 latin squares
9.2.1 some examples
9.2.2 orthogonal latin squares
9.2.3 existence results for orthogonal families
9.2.4 proof of theorem 9.3
9.2.5 orthogonal arrays with applications to cryptography
9.3 finite fields and families of latin squares
9.3.1 modular arithmetic
9.3.2 modular arithmetic and the rsa cryptosystem
9.3.3 the finite fields gf(pk)
9.3.4 construction of a complete orthogonal family of n x n latin squares if n is a power of a prime
9.3.5 justification of the construction of a complete orthogonal family if n= pk
9.4 balanced incomplete block designs
9.4.1 (b, v, r, k, λ)-designs
9.4.2 necessary conditions for the existence of (b, v, r, k, λ)-designs
9.4.3 proof of fisher's inequality
9.4.4 resolvable designs
9.4.5 steiner triple systems
9.4.6 symmetric balanced incomplete block designs
9.4.7 building new (b, v, r, k, a)-designs from existing ones
9.4.8 group testing and its applications
9.4.9 steiner systems and the national lottery
9.5 finite projective planes
9.5.1 basic properties
9.5.2 projective planes, latin squares, and (v, k, a)-designs references for chapter 9
10 coding theory
10.1 information transmission
10.2 encoding and decoding
10.3 error-correcting codes
10.3.1 error correction and hamming distance
10.3.2 the hamming bound
10.3.3 the probability of error
10.3.4 consensus decoding and its connection to finding patterns in molecular sequences
10.4 linear codes
10.4.1 generator matrices
10.4.2 error correction using linear codes
10.4.3 hamming codes
10.5 the use of block designs to find error-correcting codes
10.5.1 hadamard codes
10.5.2 constructing hadamard designs
10.5.3 the richest (n, d)-codes
10.5.4 some applications references for chapter 10
11 existence problems in graph theory
11.1 depth-first search: a test for connectedness
11.1.1 depth-first search
11.1.2 the computational complexity of depth-first search
11.1.3 a formal statement of the algorithm
11.1.4 testing for connectedness of truly massive graphs
11.2 the one-way street problem
11.2.1 robbins' theorem
11.2.2 a depth:first search algorithm
11.2.3 efficient one-way street assignments
11.2.4 efficient one-way street assignments for grids
11.2.5 annular cities and communications in interconnection net-works
11.3 eulerian chains and paths
11.3.1 the k6nigsberg bridge problem
11.3.2 an algorithm for finding an eulerian closed chain
11.3.3 further results about eulerian chains and paths
11.4 applications of eulerian chains and paths
11.4.1 the "chinese postman" problem
11.4.2 computer graph plotting
11.4.3 street sweeping
11.4.4 finding unknown rna/dna chains
11.4.5 a coding application
11.4.6 de bruijn sequences and telecommunications
11.5 hamiltonian chains and paths
11.5.1 definitions
11.5.2 sufficient conditions for the existence of a hamiltonian cir-cuit in a graph
11.5.3 sufficient conditions for the existence of a hamiltonian cycle in a digraph
11.6 applications of hamiltonian chains and paths
11.6.1 tournaments
11.6.2 topological sorting
11.6.3 scheduling problems in operations research
11.6.4 facilities design
11.6.5 sequencing by hybridization references for chapter 11
part iv combinatorial optimization
12 matching and covering
12.1 some matching problems
12.2 some existence results: bipartite matching and sdrs
12.2.1 bipartite matching
12.2.2 systems of distinct representatives
12.3 the existence of perfect matchings for arbitrary graphs
12.4 maximum matchings and minimum coverings
12.4.1 vertex coverings
12.4.2 edge coverings
12.5 finding a maximum matching
12.5.1 m-augmenting chains
12.5.2 proof of theorem 12.7
12.5.3 an algorithm for finding a maximum matching
12.6 matching as many elements of x as possible
12.7 maximum-weight matching
12.7.1 the "chinese postman" problem revisited
12.7.2 an algorithm for the optimal assignment problem (maximum-weight matching)
12.8 stable matchings
12.8.1 gale-shapley algorithm
12.8.2 numbers of stable matchings
12.8.3 structure of stable matchings
12.8.4 stable marriage extensions references for chapter 12
13 optimization problems for graphs and networks
13.1 minimum spanning trees
13.1.1 kruskal's algorithm
13.1.2 proof of theorem 13.1
13.1.3 prim's algorithm
13.2 the shortest route problem
13.2.1 the problem
13.2.2 dijkstra's algorithm
13.2.3 applications to scheduling problems
13.3 network flows
13.3.1 the maximum-flow problem
13.3.2 cuts
13.3.3 a faulty max-flow algorithm
13.3.4 augmenting chains
13.3.5 the max-flow algorithm
13.3.6 a labeling procedure for finding augmenting chains
13.3.7 complexity of the max-flow algorithm
13.3.8 matching revisited
13.3.9 menger's theorems
13.4 minimum-cost flow problems
13.4.1 some examples
references for chapter 13
author index
subject index