Introduction to Combinatorics and Probability

Combinatorics and probability are fundamental areas of mathematics that deal with counting, arrangement, and the likelihood of events.

Probability

To formalize the concept of probability, we need to define the concepts of random process, sample space, and events.

A random process is a process that produces a singular outcome out of a set of outcomes that cannot be predicted with certainty.

For example, flipping a fair coin is a random process because we cannot predict whether it will land on heads or tails.

The sample space is the set of all possible outcomes of a random process. For the coin flip example, the sample space is $\{ Heads, Tails \}$.

An event is a subset of the sample space. For example, the event of getting heads when flipping a coin is $\{ Heads \}$.

The probability of an event is a measure of how likely that event is to occur. It is defined as the ratio of the event to the total number of possible outcomes in the sample space.

If all outcomes in the sample space are equally likely, the probability of an event $E$ is given by:

where $|E|$ is the number of outcomes in event $E$ and $|S|$ is the total number of outcomes in the sample space $S$.

For example, when flipping a fair coin, the probability of getting heads is:

since there is 1 outcome for the event (heads) and 2 possible outcomes (heads and tails).

Combinatorics

Combinatorics is the branch of mathematics that deals with counting, arrangement, and combination of objects.

Counting Elements in a List

How many numbers are there from 1 to 100?

Yes, the answer is 100.

But what about from 50 to 100?

You might be tempted to say 50, but we need to include both endpoints. So the correct answer is actually 51.

For any two integers $a$ and $b$ where $a \leq b$, the number of integers from $a$ to $b$ inclusive is given by:

Problems