Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools

Combinatorics Methods: Permutations, Combinations and Counting

Every counting method on one page, from the multiplication principle and factorials to permutations, combinations, binomial expansions, inclusion-exclusion and word problems. Each method links to the rules it uses and to the combinatorics lesson where they are explained.

Level
I

Counting rules

Atomic · one rule, applied once
m·n

How to count choices made in stages

Multiplication principle
Atomic
Recognize
One outcome is built from several steps, and the number of options at each step does not depend on the earlier choices: an outfit of a shirt and pants and shoes, a code digit by digit, a meal of 3×2×43 \times 2 \times 4 dishes.
steps
1. Split one outcome into steps joined by the word and.
2. Count the options at each step.
3. Multiply the counts.
Statement
∣A1×A2×⋯×Ak∣=m1⋅m2⋯mk|A_1 \times A_2 \times \cdots \times A_k| = m_1 \cdot m_2 \cdots m_k
worked example
33 shirts, 44 pants, 22 pairs of shoes: 3⋅4⋅2=243 \cdot 4 \cdot 2 = 24 outfits
m+n

How to count choices from separate cases

Addition principle
Atomic
Recognize
One outcome comes from one of several groups that share no outcomes, joined by the word or: one book from 55 novels or 77 biographies, one trip by bus or by train.
steps
1. Split the outcomes into cases that cannot happen together.
2. Count each case and add the counts. If two cases share outcomes, use inclusion-exclusion instead.
Statement
∣A1∪A2∪⋯∪Ak∣=∣A1∣+∣A2∣+⋯+∣Ak∣,Ai∩Aj=∅|A_1 \cup A_2 \cup \cdots \cup A_k| = |A_1| + |A_2| + \cdots + |A_k|, \quad A_i \cap A_j = \emptyset
worked example
55 novels or 77 biographies, pick one book: 5+7=125 + 7 = 12 choices
n!

How to compute a factorial

Factorial
Atomic
Recognize
A product of all whole numbers from nn down to 11 appears, or a ratio of factorials must be simplified: 6!6!, 8!6!\frac{8!}{6!}, 0!0!.
steps
1. Multiply the whole numbers from nn down to 11; use 0!=10! = 1.
2. In a ratio, cancel the smaller factorial first: n!m!=n(n−1)⋯(m+1)\frac{n!}{m!} = n(n-1)\cdots(m+1).
Statement
n!=n⋅(n−1)⋯2⋅1,0!=1n! = n \cdot (n-1) \cdots 2 \cdot 1, \qquad 0! = 1
worked example
6!=720,8!6!=8⋅7=566! = 720, \qquad \dfrac{8!}{6!} = 8 \cdot 7 = 56
II

Arrangements, selections, expansions and overlaps

Composite · each opens its own page
How to count permutationsCount ordered arrangements of rr items chosen from nn distinct items: multiply rr falling factors, P(n,r)=n!(n−r)!P(n, r) = \frac{n!}{(n-r)!}.uses: multiplication principle · factorial · P(n, r)Composite4 steps · 3 examplesHow to count arrangements with repetitionFill rr positions when every position can take any of nn options again: multiply nn by itself rr times, nrn^r.uses: multiplication principle · powersComposite4 steps · 3 examplesHow to count arrangements with identical itemsArrange nn items where some are identical: divide n!n! by the factorial of each group size, n!n1! n2!⋯nk!\frac{n!}{n_1!\,n_2!\cdots n_k!}.uses: factorial · multinomial coefficientComposite4 steps · 3 examplesHow to count circular arrangementsSeat nn distinct items around a circle where turning the circle changes nothing: fix one item and arrange the rest, (n−1)!(n-1)!.uses: factorial · fix one itemComposite4 steps · 3 examplesHow to count combinationsChoose rr of nn distinct items when order does not matter: count the ordered picks and divide by r!r!, which gives (nr)\binom{n}{r}.uses: binomial coefficient · factorial · multiplication principleComposite5 steps · 3 examplesHow to count combinations with repetitionChoose rr items from nn kinds when a kind may be chosen again and order does not matter: stars and bars, (n+r−1r)\binom{n+r-1}{r}.uses: stars and bars · binomial coefficientComposite4 steps · 3 examplesHow to compute binomial coefficientsEvaluate (nk)\binom{n}{k} by hand: switch to the smaller kk by symmetry, write kk falling factors over k!k!, and cancel before you multiply.uses: factorial · symmetry · Pascal's ruleComposite4 steps · 3 examplesHow to expand a binomial powerExpand (a+b)n(a + b)^n with the binomial theorem: coefficients from row nn of Pascal's triangle, powers of aa falling and powers of bb rising.uses: binomial theorem · Pascal's triangle · binomial coefficientsComposite4 steps · 3 examplesHow to find a specific term in a binomial expansionFind one term or coefficient of (a+b)n(a + b)^n without expanding: write the general term (nk)an−kbk\binom{n}{k}a^{n-k}b^k and solve for kk.uses: general term · binomial coefficient · laws of exponentsComposite4 steps · 3 examplesHow to use inclusion-exclusion for two setsCount the items in A or B: add the two sizes and subtract the overlap once, ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B|.uses: addition principle · intersectionComposite4 steps · 3 examplesHow to use inclusion-exclusion for three setsCount the items in at least one of three sets: add the three sizes, subtract the three pairwise overlaps, add back the triple overlap.uses: inclusion-exclusion · intersections · complementComposite4 steps · 3 examplesHow to use complementary countingCount the outcomes you do not want and subtract them from the total; the standard route for "at least one" questions.uses: complement · multiplication principle · subtractionComposite4 steps · 3 examplesHow to count derangementsCount the orders in which no item stays in its own place: the alternating sum !n=n!∑k=0n(−1)kk!!n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!} or the recurrence.uses: inclusion-exclusion · factorial · recurrenceComposite4 steps · 3 examples
III

Choosing a formula

Strategy
IV

Word problems

committees, codes, seating, at least one