Combinatorics, An Introduction

Introduction

The fundamental theorem of combinatorics, and of probability and statistics, is also the most obvious. If there are six possible outcomes from the throw of a die, and two outcomes from the toss of a coin, Then the two events taken together have twelve possible outcomes. This is really a statement about the cardinality of the cross product of two finite sets, and its proof is best left in set theory, where it belongs.

There is a catch. The individual events must be independent. If someone decides to drop the coin flat on the table, heads up, whenever the die comes up 6, there are only 11 possible outcomes, not 12. This disclaimer is obvious, but in the real world, seemingly unrelated events are often connected in subtle ways.

The branch of mathematics known as combinatorics combines independent events and counts, or at least estimates, the number of outcomes. Probability brings in the concept of randomness, so that one of these outcomes can be chosen at random. Then we can compute the odds of a royal flush, 4 chances in 2598960. That will come later. For now, let's start counting events.