Combinatorics

Abstract

Combinatorics is the bane of many a student of probability theory. Even elementary combinatorial problems can be frustratingly subtle. The cure for this ill is more exposure, not less. Because combinatorics has so many important applications, serious students of the mathematical sciences neglect it at their peril. Here we explore a few topics in combinatorics that have maximum intersection with probability. Our policy is to assume that readers have a nodding familiarity with combinations and permutations. Based on this background, we discuss bijections, inclusion-exclusion (sieve) methods, Catalan numbers, Stirling numbers of the first and second kind, and the pigeonhole principle. Along the way we meet some applications that we hope will whet readers’ appetites for further study. The books [21, 22, 26, 59, 78, 139, 207] are especially recommended.