Factorials and the fundamental counting principle

Key idea

The fundamental counting principle (rule of product) says: if a process has \(a\) choices for step 1, \(b\) choices for step 2, and \(c\) choices for step 3, then the total number of outcomes is \(a\cdot b\cdot c\).

A factorial counts arrangements of distinct items: \[ n!=n(n-1)(n-2)\cdots 2\cdot 1. \] There are \(n!\) ways to arrange \(n\) distinct objects in a line.

Worked example

Try it

Summary

• Use the rule of product to multiply choices across steps.
• Use factorials to count arrangements of distinct items: \(n!\).

Permutations: when order matters

Key idea

A permutation is an ordered arrangement. If you fill \(r\) positions using \(n\) distinct items with no repetition, the count is: \[ P(n,r)=n(n-1)(n-2)\cdots(n-r+1)=\frac{n!}{(n-r)!}. \] A fast mental check: “first position has \(n\) choices, second has \(n-1\), …”.

Worked example

Try it

Summary

• Use permutations when order matters.
• \(P(n,r)=\dfrac{n!}{(n-r)!}\) counts ordered selections with no repetition.

Combinations: when order does not matter

Key idea

A combination is an unordered selection. If you choose \(r\) items from \(n\) distinct items, the count is: \[ \binom{n}{r}=\frac{n!}{r!(n-r)!}. \] This is also called a binomial coefficient. A powerful connection: \[ P(n,r)=\binom{n}{r}\,r! \] (because each chosen group of \(r\) items has \(r!\) possible orders).

Worked example

Try it

Summary

• Use combinations when order does not matter.
• \(\binom{n}{r}=\dfrac{n!}{r!(n-r)!}\) counts unordered selections.
• Relationship: \(P(n,r)=\binom{n}{r}\,r!\).

Circular permutations and repeated elements

Key idea

Circular permutations: When \(n\) distinct people sit around a round table and rotations are considered the same, the number of seatings is: \[ (n-1)!. \] We “fix” one person to remove rotational duplicates.

Repeated elements: If you arrange \(n\) items where some repeat (for example, a word with repeated letters), then divide by factorials of repeated counts: \[ \frac{n!}{n_1!\,n_2!\cdots}. \]

Worked example

Try it

Summary

• Circular permutations (rotations same): \((n-1)!\).
• Repeated elements: divide by factorials of repeat counts: \(\dfrac{n!}{n_1!\,n_2!\cdots}\).

Bit strings, combinations, and even/odd patterns

Key idea

A bit string of length \(n\) is a sequence of \(0\)s and \(1\)s. To count strings with exactly \(k\) ones, choose which \(k\) positions are ones: \[ \binom{n}{k}. \] To count strings with an even number of ones, you can sum \(\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots\). A key fact (for \(n\ge 1\)) is that exactly half of all \(2^n\) bit strings have an even number of ones, so the count is \(2^{n-1}\).

Worked example

Try it

Summary

• Exactly \(k\) ones in length \(n\): \(\binom{n}{k}\).
• Even number of ones (for \(n\ge 1\)): \(2^{n-1}\).

Counting diagonals and computing larger binomial coefficients

Key idea

A diagonal connects two non-adjacent vertices of a polygon. To count diagonals in a convex \(n\)-gon:

• Choose 2 vertices to form a segment: \(\binom{n}{2}\).
• Subtract the \(n\) sides (edges).

So: \[ \text{diagonals}=\binom{n}{2}-n=\frac{n(n-1)}{2}-n=\frac{n(n-3)}{2}. \]

Worked example

Try it

Summary

• Diagonals in a convex \(n\)-gon: \(\dfrac{n(n-3)}{2}\).
• Compute \(\binom{n}{r}\) efficiently by simplifying factors early.

Why permutations and combinations matter

Where permutations & combinations show up

• Probability: counting outcomes, binomial probabilities, card problems, and sampling without replacement.
• Computer science: passwords and codes, bit strings, search spaces, and algorithm counting.
• Scheduling & assignments: arranging tasks, selecting teams, choosing committees, assigning roles.
• Geometry & graphs: diagonals, edges, and counting pairs.

Worked example: committee + leader

Try it

Final recap

• Rule of product: multiply choices across steps.
• Factorial: \(n!\) counts linear arrangements of \(n\) distinct items; remember \(0!=1\).
• Permutations (order matters): \(P(n,r)=\dfrac{n!}{(n-r)!}\).
• Combinations (order does not matter): \(\binom{n}{r}=\dfrac{n!}{r!(n-r)!}\).
• Connection: \(P(n,r)=\binom{n}{r}\,r!\).
• Circular permutations: \((n-1)!\). Repeated elements: \(\dfrac{n!}{n_1!\,n_2!\cdots}\).
• Bit strings: exactly \(k\) ones \(\Rightarrow \binom{n}{k}\); even number of ones \(\Rightarrow 2^{n-1}\) for \(n\ge 1\).
• Diagonals: \(\dfrac{n(n-3)}{2}\) in a convex \(n\)-gon.