Combinatorics and Probability - Theory & Concepts

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 (or Multiplication Rule) provides a method for finding the total number of ways a sequence of events can occur without listing them all.

Multiplication Rule

If one event can occur in $m$ ways and a second 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 (e.g., $m \times n \times p \dots$ ).

Factorials

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

n

. It is denoted by

n!

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	-

Zero Factorial

By definition,

0! = 1

. This convention is necessary for the formulas of permutations and combinations to work when 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 different 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 (also written as {}^nP_r)	-
$n$	Total number of items in the set	-
$r$	Number of items to arrange	-

Special Cases

Arranging all objects: The number of ways to arrange all $n$ distinct objects is $n!$ . (e.g., arranging 5 books on a shelf is $5! = 120$ ways).
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 accounts for the lack of a distinct starting point.

Combinatorics Explorer

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

Item Pool (4):

Permutations (Order Matters)

Example: Passwords, Rankings (1st, 2nd, 3rd)

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

12 distinct arrangements

Combinations (Order Does NOT Matter)

Example: Committees, Hands of cards

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

6 distinct groups

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$ ).

Combinations

A combination is a selection of objects from a set where the order does not matter. (e.g., selecting a committee of 3 people from a group of 10).

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 (also written as {}^nC_r or \\binom{n}{r})	-
$n$	Total number of items in the set	-
$r$	Number of items to select	-

Key Properties

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 just a combination followed by an arrangement of those selected items.

Basic Probability

Probability measures the likelihood of an event occurring, ranging from 0 (impossible) to 1 (certain).

Probability of an Event

The theoretical probability of an event happening in an equally likely sample space.

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	-

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 outcome of event A does not affect 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 dependent, $P(A \cap B) = P(A) \times P(B|A)$ .

Key Takeaways

Order Matters: Use permutations ( $P$ ) when arranging items (e.g., passwords, racing placements). Use combinations ( $C$ ) when grouping items (e.g., committees, hands of cards).
Factorials: Remember that $0! = 1$ .
Identical Items: Divide the total permutations by the factorials of the counts of identical objects to remove duplicates (e.g., arranging the letters in MISSISSIPPI).
Probability Scale: All probabilities must fall within the range $0 \le P(E) \le 1$ . If you calculate a probability greater than 1 or less than 0, check your math.
The "Or" vs "And" Rule: In probability and counting, "OR" generally translates to addition ( $+$ ), while "AND" translates to multiplication ( $\times$ ).

PreviousSequences and Series - Examples & Applications

Quiz Me

NextIntroduction to Analytic Geometry - Theory & Concepts