Principles and Techniques in Combinatorics Book

	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