THEORY AND PROBLEMS OF

COMBINATORICS

including concepts of GRAPH THEORY

V.K.Balakrishnan

Chapter 1            BASIC TOOLS

1.1   The Sum Rule and the Product Rule
1.2   Permutations and Combinations
1.3   The Pigeonhole Principle

Solved Problems
      The Sum and Product Rules
      Permutations and Combinations
      The Pigeonhole Principle
      Ramsey Numbers
      Catalan Numbers
      Stirling Numbers

Chapter 2            FURTHER BASIC TOOLS

2.1   Generalized Permutations and Combinations
2.2   Sequences and Selections
2.3   The Inclusion-Exclusion Principle
2.4   Systems of Distinct Representatives (SDR)

Solved Problems
      Generalized Permutations and Combinations
      Sequences and Selections
      The inclusion - exclusion Principle
      Derangements and Other Constrained Arrangements
      Combinatorial Number Theory
      Generalized Inclusion-Exclusion Principle
      The Permanent of a Matrix
      Rook Polynomials and Hit Polynomials
      Systems of Distinct Representatives (SDR) and Coverings
      Sperner’s Theorem and Symmetric Chain Decomposition
      Partially Ordered Sets and Dilworth's Theorem

Chapter 3            GENERATING FUNCTIONS AND RECURRENCE RELATIONS

3.1   Ordinary and Exponential Generating Functions
3.2   Partitions of a Positive Integer
3.3   Recurrence Relations
3.4   Algebraic Solution of Linear Recurrence Relations
      with Constant Coefficients
3.5   Solution of Recurrence Relations Using Generating 
      Functions

Solved Problems
      Ordinary Generating Functions
      Partitions of Integers and Their Generating Functions
      Exponential Generating Functions
      Recurrence Relations and Associated Generating Functions
      H-Tableaux and Young Tableaux

Chapter 4          GROUP THEORY IN COMBINATORICS

4.1   The Burnside-Frobenius Theorem
4.2   Permutation Groups and Their Cycle Indices
4.3   Polya's Enumeration Theorems

Solved Problems
      The Burnside-Frobenius Theorem
      Permutation Groups and Their Cycle Indices
      Polya's Enumeration Theorems

Appendix           GRAPH THEORY

GLOSSARY

LIST OF SYMBOLS

FURTHER READING

INDEX
|Up|
THEORY AND PROBLEMS OF

COMBINATORICS

including concepts of GRAPH THEORY

V.K.Balakrishnan

Contents
