Mathwords logoMathwords

Combinatorics

Combinatorics

The mathematics of counting, especially counting how many elements are in very large sets.

 

 

See also

Combination, permutation

Worked Example

Problem: A school committee must be formed by choosing 3 students from a group of 10. How many different committees are possible?
Identify the type of problem: The order in which students are chosen does not matter — picking Alice, Bob, and Carol is the same committee as picking Carol, Alice, and Bob. This is a combination problem.
Apply the combination formula: The number of ways to choose rr items from nn items (without regard to order) is given by the combination formula.
(nr)=n!r! (n−r)!\binom{n}{r} = \frac{n!}{r!\,(n-r)!}
Substitute the values: Here n=10n = 10 and r=3r = 3.
(103)=10!3!⋅7!=10×9×83×2×1\binom{10}{3} = \frac{10!}{3!\cdot 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1}
Compute: Multiply the numerator and denominator, then divide.
7206=120\frac{720}{6} = 120
Answer: There are 120 different possible committees.

Another Example

Problem: How many different 3-digit codes can be formed from the digits 1, 2, 3, 4, and 5 if no digit may be repeated?
Identify the type of problem: Here order matters — the code 1-2-3 is different from 3-2-1. This is a permutation problem.
Apply the counting principle: There are 5 choices for the first digit, 4 remaining choices for the second, and 3 for the third.
5×4×35 \times 4 \times 3
Compute: Multiply these together.
5×4×3=605 \times 4 \times 3 = 60
Answer: There are 60 possible 3-digit codes.

Frequently Asked Questions

What is the difference between combinatorics and probability?
Combinatorics focuses on counting how many ways something can happen. Probability uses those counts to determine how likely an event is. For example, combinatorics tells you there are 120 possible committees; probability tells you the chance a specific person is on a randomly chosen committee.
When do I use permutations vs. combinations?
Use permutations when the order of selection matters (like arranging people in a line or forming a code). Use combinations when order does not matter (like choosing members of a team). If rearranging the same items gives a different outcome, it's a permutation; if it gives the same outcome, it's a combination.

Permutation vs. Combination

Both are core tools in combinatorics. A permutation counts ordered arrangements — how many ways you can line up or sequence items. A combination counts unordered selections — how many groups you can form. For any set of chosen items, there are always at least as many permutations as combinations, because each combination corresponds to multiple permutations (one for every rearrangement of that group).

Why It Matters

Combinatorics is the foundation of probability — you cannot compute the likelihood of an event without first counting the possible outcomes. It appears in computer science (algorithm analysis, cryptography), biology (gene combinations), and everyday decisions like scheduling and tournament brackets. Many standardized math tests include combinatorics problems, making it a practical skill for students to develop.

Common Mistakes

Mistake: Using permutations when order does not matter (or vice versa)
Correction: Always ask: does rearranging the chosen items create a different outcome? If yes, use permutations. If no, use combinations. Mixing these up typically inflates or deflates your count by a factor of r!r!.
Mistake: Forgetting to account for restrictions or overcounting
Correction: If a problem says 'no repeated digits' or 'at least one girl must be chosen,' you need to adjust your count accordingly. Read the constraints carefully before choosing a formula.

Related Terms