Combinatorics and probability

This chapter covers the following:

• Permutations
• Combinations
• Key differences
• Special cases
• Probability
• Law of total probability
• Law of compound or joint probability
• Bayes’ theorem

In mathematics, permutations and combinations are counting methods. You use them to figure out how many ways you can arrange or select items.

Permutations

Permutations count the number of ways to arrange objects when order matters.

Formula for permutations (without repetition):

Use this when you’re arranging $r$ items chosen from $n$ distinct items, with no repeats:

$$P(n,r)=\frac{n!}{(n-r)!}$$

Where:

• $n!$ (“$n$ factorial”) means $n\times (n-1)\times \cdots \times 1$
• $r$ is the number of items you arrange

Example:

How many ways can you arrange 3 letters from the word “MATH”?

• Number of distinct letters: $n=4$ (M, A, T, H)
• Number of letters to arrange: $r=3$

$$P(4,3)=\frac{4!}{(4-3)!}=\frac{24}{1}=24$$

So, there are 24 ways to arrange 3 letters out of 4.

Combinations

Combinations count the number of ways to select objects when order doesn’t matter.

Formula for combinations:

Use this when you’re choosing $r$ items from $n$ distinct items and the order of the chosen items is irrelevant:

$$C(n,r)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\frac{n!}{r!(n-r)!}$$

Example:

How many ways can you choose 3 students from a group of 5?

• $n=5$
• $r=3$

$$C(5,3)=\frac{5!}{3!(5-3)!}=\frac{120}{6\times 2}=\frac{120}{12}=10$$

So, there are 10 ways to choose 3 students from 5.

Key differences

Aspect	Permutations	Combinations
Order matters?	Yes	No
Formula	$\frac{n!}{(n-r)!}$	$\frac{n!}{r!(n-r)!}$
Example	Arranging medals	Choosing committee members

Special cases

Permutations with repetition

Use this when each of the $r$ positions can be filled by any of the $n$ items (so repeats are allowed):

$$n^r$$

Example: 4-digit PIN code using digits 0-9:

• $n=10$ possible digits
• $r=4$ positions

$$10^4=10,000\text{ possible codes}$$

Permutations with identical items

If some objects are indistinguishable, swapping those identical objects doesn’t create a new arrangement. That reduces the number of distinct permutations.

The number of different permutations of $n$ objects, where:

• $n_1$ are of type 1
• $n_2$ are of type 2
• …
• $n_k$ are of type $k$
• and ${\sum }_{i=1}^k{n}_i=n$

Then the number of distinct permutations is:

$$\frac{n!}{n_1!\cdot n_2!\cdots n_k!}$$

Example:

How many distinct ways can you arrange the letters in the word BALLOON?

Letters: B, A, L, L, O, O, N

• $n=7$
• L appears 2 times
• O appears 2 times

So,

$$\frac{7!}{2!\cdot 2!}=\frac{5040}{4}=1260$$

Combinations with repetition

Use this when selections can repeat and order doesn’t matter.

For $r$ selections from $n$ types:

$$C(n+r-1,r)=\left(\genfrac{}{}{0ex}{}{n+r-1}{r}\right)$$

Example: Ways to choose 3 scoops of ice cream from 5 flavors (allowing repeats):

$$\left(\genfrac{}{}{0ex}{}{5+3-1}{3}\right)=\left(\genfrac{}{}{0ex}{}{7}{3}\right)=35$$

Probability

Definition: Probability measures how likely an event is to occur.

Let $S$ be the sample space (all possible outcomes) and $A$ an event (a set of outcomes). The probability of event $A$, written $P(A)$, is:

$$P(A)=\frac{\text{Number of favorable outcomes}}{\text{Total number of possible outcomes}}$$

Example: If a fair die is rolled, what is the probability of getting a 4?

$$P(4)=\frac{1}{6}$$

Law of total probability

If events $B_1,B_2,...,B_n$ are mutually exclusive and exhaustive (meaning they partition the sample space), then any event $A$ can be found by adding up the ways $A$ can happen through each case $B_i$:

$$P(A)=\sum _{i=1}^{n}P(A\mid B_i)P(B_i)$$

Example:

Suppose a factory has two machines:

• Machine 1 produces 60% of the items and has a defect rate of 1%.
• Machine 2 produces 40% of the items and has a defect rate of 2%.

What is the probability that a randomly selected item is defective?

Let:

• $B_1$: item from Machine 1, $P(B_1)=0.6$
• $B_2$: item from Machine 2, $P(B_2)=0.4$
• $A$: item is defective

Then,

$$\begin{gathered} P(A)=P(A\mid B_1)P(B_1)+P(A\mid B_2)P(B_2) \\ =(0.01)(0.6)+(0.02)(0.4)=0.006+0.008=0.014 \end{gathered}$$

So, the probability of a defective item is 0.014 or 1.4%.

Law of compound or joint probability

The joint probability of two events $A$ and $B$ occurring together is:

$$P(A\cap B)=P(A\mid B)\cdot P(B)=P(B\mid A)\cdot P(A)$$

This formula connects:

• a conditional probability (like $P(A\mid B)$)
• the probability of the condition (like $P(B)$)
• the probability of both events happening (like $P(A\cap B)$)

Example:

Suppose:

• $P(B)=0.5$
• $P(A\mid B)=0.3$

Then:

$$P(A\cap B)=0.3\times 0.5=0.15$$

Bayes’ theorem

Bayes’ theorem lets you reverse a conditional probability. In other words, it helps you find $P(A\mid B)$ when you know $P(B\mid A)$.

Given events $A$ and $B$ with $P(B)>0$:

$$P(A\mid B)=\frac{P(B\mid A)\cdot P(A)}{P(B)}$$

Using the Law of Total Probability in the denominator:

$$P(A_i\mid B)=\frac{P(B\mid A_i)\cdot P(A_i)}{{\sum }_{j=1}^{n}P(B\mid A_j)\cdot P(A_j)}$$

Example (continued from previous):

What is the probability that a defective item came from Machine 2?

We already know:

• $P(A)=0.014$
• $P(B_2)=0.4$
• $P(A\mid B_2)=0.02$

Now apply Bayes’ Theorem:

$$P(B_2\mid A)=\frac{P(A\mid B_2)\cdot P(B_2)}{P(A)}=\frac{0.02\cdot 0.4}{0.014}=\frac{0.008}{0.014}\approx 0.5714$$

So, about 57.14% of defective items come from Machine 2.