# Principles and Techniques in Combinatorics

## Product Details

ISBN-13:
9789810211394
Publisher:
World Scientific Publishing Co Pte Ltd
Publication date:
07/28/1992
Edition description:
New Edition
Pages:
312
Sales rank:
446,024
Product dimensions:
6.00(w) x 9.00(h) x 0.65(d)

## Related Subjects

 Preface Notation and Abbreviation Contents 1 Permutations and Combinations 1 1.1 Two Basic Counting Principles 1 1.2 Permutations 6 1.3 Circular Permutations 12 1.4 Combinations 17 1.5 The Injection and Bijection Principles 27 1.6 Arrangements and Selections with Repetitions 32 1.7 Distribution Problems 40 2 Binomial Coefficients and Multinomial Coefficients 69 2.2 The Binomial Theorem 70 2.3 Combinatorial Identities 71 2.4 The Pascal's Triangle 76 2.5 Chu Shih-Chieh's Identity 78 2.6 Shortest Routes in a Rectangular Grid 85 2.7 Some Properties of Binomial Coefficients 93 2.8 Multinomial Coefficients and the Multinomial Theorem 96 3 The Pigeonhole Principle and Ramsey Numbers 119 3.2 The Pigeonhole Principle 119 3.3 More Examples 122 3.4 Ramsey Type Problems and Ramsey Numbers 129 3.5 Bounds for Ramsey Numbers 132 4 The Principle of Inclusion and Exclusion 145 4.2 The Principle 146 4.3 A Generalization 148 4.4 Integer Solutions and Shortest Routes 153 4.5 Surjective Mappings and Stirling Numbers of the Second Kind 158 4.6 Derangements and A Generalization 160 4.7 The Sieve of Eratosthenes and Euler [phi]-function 163 4.8 The 'Probleme des Menages' 169 5 Generating Functions 185 5.1 Ordinary Generating Functions 185 5.2 Some Modelling Problems 192 5.3 Partitions of Integers 196 5.4 Exponential Generating Functions 204 6 Recurrence Relations 225 6.2 Two Examples 228 6.3 Linear Homogeneous Recurrence Relations 234 6.4 General Linear Recurrence Relations 241 6.5 Two Applications 244 6.6 A System of Linear Recurrence Relations 251 6.7 The Method of Generating Functions 256 6.8 A Nonlinear Recurrence Relation and Catalan Numbers 259 6.9 Oscillating Permutations and an Exponential Generating Function 262 Bibliography 287 Answers 289 Index 297