Combinatorics : topics, techniques, algorithms = 组合数学 : 专题、技术与算法 /

1. what is combinatorics? .　1

sample problems--how to use this book--what you need to know--exercises

2. on numbers and counting　7

natural numbers and arithmetic--induction--some useful functions--orders of magnitude--different ways of counting--double counting--appendix on set notation--exercises

3. subsets, partitions, permutations　21

subsets--subsets of fixed size--the binomial theorem and pascal's triangle--project: congruences of binomial coefficients--permutations-- estimates for factorials--selections--equivalence and order--project: finite topologies--project: cayley's theorem on trees--bell numbers-- generating combinatorial objects--exercises

4. recurrence relations and generating functions　49

fibonacci numbers--aside on formal power series--linear recurrence relations with constant coefficients--derangements and involutions-- catalan and bell numbers--computing solutions to recurrence relations--project: finite fields and quicksort--exercises

5. the principle of inclusion and exclusion　75

pie--a generalisation--stirling numbers--project: stirling numbers and exponentias--even and odd permutations--exercises

6. latin squares and s drs　87

latin squares--systems of distinct representatives--how many latin squares ?--quasigroups--project: quasigroups and groups--orthogonal latin squares--exercises

7. extremal set theory　99

intersecting families--sperner families--the de bruijn-erdos theorem--project: regular families--exercises

8. steiner triple systems　107

steiner systems--a direct construction--a recursive construction--packing and covering--project: some special steiner triple systems-- project: tournaments and kirkman's schoolgirls--exercises

9. finite geometry　123

linear algebra over finite fields--gaussian coefficients--projective geometry axioms for projective geometry--projective planes--other kinds of geometry--project: coordinates and configurations--project: proof of the bruck-ryser theorem--appendix: finite fields--exercises

10. ramsey's theorem　147

the pigeonhole principle--some special cases--ramsey's theorem--bounds for ramsey numbers--applications--the infinite version--exercises

.11. graphs　159

definitions--trees and forests--minimal spanning trees--eulerian graphs--hamiltonian graphs--project: gray codes--the travelling salesman--digraphs--networks--menger, kjnig and hall--diameter and girth--project: moore graphs exercises

12. posets, lattices and matroids ..　187

posers and lattices--linear extensions of a poser--distributive lattices--aside on propositional logic--chains and antichains--products and dimension--the mjbius function of a poset--matroids--project: arrow's theorem--exercises

13. more on partitions and permutations　209

partitions, diagrams and conjugacy classes--euler's pentagonal numbers theorem--project: jacobi's identity--tableaux--symmetric polynomials--exercises

14. automorphism groups and permutation groups　225

three definitions of a group--examples of groups--orbits and transitivity--the schreier-sims algorithm--primitivity and multiple transitivity--examples--project: cayley digraphs and frucht's theorem--exercises

15. enumeration under group action　245

the orbit-counting lemma--an application--cycle index--examples--direct and wreath products--stirling numbers revisited--project: cycle index and symmetric functions--exercises

16. designs　257

definitions and examples--to repeat or not to repeat--fisher's inequality--designs from finite geometry--small designs--project: hadamard matrices--exercises

17. error-correcting codes　271

finding out a liar--definitions--probabilistic considerations--some bounds--linear codes; hamming codes--perfect codes--linear codes and projective spaces--exercises

18. graph colourings　291

more on bipartite graphs--vertex colourings--project: brooks' theorem--perfect graphs--edge colourings--topological graph theory--project: the five-colour theorem--exercises

19. the infinite　307

counting infinite sets konig's infinity lemma--posers and zorn's lemma--ramsey theory--systems of distinct representatives--free constructions--the random graph--exercises

20. where to from here?　325

computational complexity--some graph-theoretic topics--computer software--unsolved problems--further reading

answers to selected exercises　339

bibliography　343

index ...　347