Combinatorics and Probability

Combinatorics and Probability

Combinatorics is the branch of mathematics focused on counting, arranging, and combining sets of elements. It forms the foundation for probability theory, which quantifies the likelihood of events occurring in random experiments. These concepts are essential for solving complex engineering optimization problems and understanding statistical distributions.

The Fundamental Counting Principle

The Fundamental Counting Principle, also known as the Multiplication Rule, provides a method for finding the total number of ways a sequence of events can occur without explicitly listing all possible outcomes.

If one event can occur in $m$ ways and a second independent event can occur in $n$ ways, then the two events can occur in sequence in $m \times n$ ways. This principle extends to any number of sequential events.

Factorials

A factorial is the product of all positive integers less than or equal to a given positive integer $n$ .

Factorial

The product of an integer and all the integers below it, down to 1.

Factorial Definition

The mathematical definition of a factorial.

n! = n \times (n-1) \times (n-2) \times \dots \times 3 \times 2 \times 1

Variables

Symbol	Description	Unit
$n!$	n factorial	-
$n$	A non-negative integer	-

Note

By definition, $0! = 1$ . This convention is mathematically necessary to ensure that the formulas for permutations and combinations remain consistent when selecting or arranging zero items.

Permutations

A permutation is an arrangement of objects in a specific order. When dealing with permutations, the sequence of the items matters (e.g., a lock combination 1-2-3 is distinct from 3-2-1).

Permutation Formula

The number of ways to arrange r objects from a set of n distinct objects.

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

Variables

Symbol	Description	Unit
$P (n, r)$	Number of permutations	-
$n$	Total number of items in the set	-
$r$	Number of items to arrange	-

Special Cases of Permutations

Arranging all objects: The number of ways to arrange all $n$ distinct objects is $n!$ .
Permutations with Identical Objects: The number of distinct permutations of $n$ objects where there are $n_1$ identical items of type 1, $n_2$ identical items of type 2, etc., is given by $\frac{n!}{n_1! n_2! \dots n_k!}$ .
Circular Permutations: The number of ways to arrange $n$ distinct objects in a circle is $(n-1)!$ . This reduction accounts for the lack of a distinct starting point.

Combinations

A combination is a selection of objects from a set where the order does not matter. For example, selecting a committee of 3 engineers from a group of 10 engineers is a combination, because the sequence in which they are selected is irrelevant to the final committee composition.

Combination Formula

The number of ways to select r objects from a set of n distinct objects.

C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}

Variables

Symbol	Description	Unit
$C (n, r)$	Number of combinations	-
$n$	Total number of items in the set	-
$r$	Number of items to select	-

Properties of Combinations

Symmetry: $C(n, r) = C(n, n-r)$ . Choosing $r$ objects to keep is mathematically identical to choosing $n-r$ objects to leave behind.
Relationship to Permutations: $P(n, r) = r! \times C(n, r)$ . A permutation is simply a combination followed by an ordered arrangement of those selected items.

Use the interactive tool below to visualize the relationship between permutations and combinations. Notice how the number of permutations grows much faster than combinations as you increase $r$ .

Permutations vs. Combinations Explorer

Total Items (

n

Pool of distinct items to choose from

Items Selected (

r

Number of items to select
(Note: r cannot exceed n. Assumes distinct items, no duplicates)

Item Pool (4):

Permutations (Order Matters)

Scenario: Creating a password, or picking 1st/2nd/3rd place.
(Choosing 2 items where order matters)

P(4, 2) = \frac{4!}{(4-2)!} = \frac{24}{2} = 12

12 distinct arrangements

1,21,31,42,12,32,43,13,23,44,14,24,3

Combinations (Order Does NOT Matter)

Scenario: Forming a committee, or drawing a hand of cards.
(Choosing 2items where order doesn't matter)

C(4, 2) = \frac{4!}{2!(4-2)!} = \frac{24}{2 \cdot 2} = 6

6 distinct groups

1,21,31,42,32,43,4

Notice that $P(4, 2)$ is always exactly $2!$ times larger than $C(4, 2)$ , because for every combination (group), there are $2!$ ways to arrange those specific items. ( $2! = 2$ ).

Basic Probability

Probability is the measure of the likelihood that an event will occur. The probability of an event ranges from 0 (impossible) to 1 (certain).

Sample Space

The set of all possible outcomes of a random experiment.

Theoretical Probability

The probability of an event happening in a sample space where all outcomes are equally likely.

P(E) = \frac{n(E)}{n(S)}

Variables

Symbol	Description	Unit
$P (E)$	Probability of event E	-
$n (E)$	Number of favorable outcomes	-
$n (S)$	Total number of possible outcomes in the sample space	-

Caution

All calculated probabilities must fall within the range $0 \le P(E) \le 1$ . If you calculate a probability greater than 1 or less than 0, there is an error in your formulation or arithmetic.

Probability Rules

Complementary Events: The probability that an event $E$ does not occur is $P(E') = 1 - P(E)$ .
Addition Rule (Mutually Exclusive Events): If events $A$ and $B$ cannot occur simultaneously, then $P(A \text{ or } B) = P(A \cup B) = P(A) + P(B)$ .
Addition Rule (Non-Mutually Exclusive Events): $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ .
Multiplication Rule (Independent Events): If the occurrence of event $A$ does not affect the probability of event $B$ , then $P(A \text{ and } B) = P(A \cap B) = P(A) \times P(B)$ .
Conditional Probability: The probability of event $B$ occurring given that event $A$ has already occurred is denoted as $P(B|A)$ . If the events are dependent, $P(A \cap B) = P(A) \times P(B|A)$ .

Use the interactive Venn diagram laboratory below to explore set probabilities. Adjust the sizes of sets $A$ and $B$ , along with their intersection $A \cap B$ , to visually verify the Addition Rule and trace conditional probabilities dynamically.

Set Probability & Venn Diagram Simulator

Set Probability Parameters

Probability of A - P(A)0.60

Probability of B - P(B)0.50

Intersection - P(A \cap B)0.30

Max intersection cap: 0.50 (min of P(A), P(B))

Interactive Set Algebra

Union: P(A \cup B)0.80

A only: P(A \cap B')0.30

B only: P(B \cap A')0.20

Complement: P((A \cup B)')0.20

Formula: P(A \cup B) = P(A) + P(B) - P(A \cap B)

Set A only (0.30)

Set B only (0.20)

Intersection (0.30)

Complement (0.20)

Important

In probability and counting principles, the word "OR" generally translates to addition ( $+$ ), while "AND" translates to multiplication ( $\times$ ).

Trace conditional probabilities and sequential outcomes using the interactive probability tree below. Adjust the path probabilities to see Bayes' Theorem compute final outcomes in real time.

Conditional Probability Tree Builder

Probability P(A)0.60

Probability P(B | A)0.80

Probability P(B | A')0.30

Bayes & Total Probability

Total P(B):

P(B) = P(A \cap B) + P(A' \cap B) = 0.480 + 0.120 = 0.600

Bayes P(A | B):

P(A|B) = \frac{P(A \cap B)}{P(B)} = \frac{0.480}{0.600} = 0.800

Event A/A'Event BEvent B' (Not B)

Key Takeaways

Order matters for permutations ( $P$ ), whereas order does not matter for combinations ( $C$ ).
The number of ways to arrange $n$ items in a circle is $(n-1)!$ .
For identical items, divide the total factorial permutation by the factorials of the counts of identical objects.
Mutually exclusive events utilize the addition rule, while independent events utilize the multiplication rule.

PreviousSequences and Series - Examples & Applications

Quiz Me

NextCombinatorics and Probability - Examples