Basic Counting

What you need to know

• Multiplication principle. If a job has stages, and each stage has the same number of choices no matter what you chose before, multiply. Cases that do not overlap add. Example: $2$ letters then $3$ digits make $26\cdot26\cdot10\cdot10\cdot10 = 676{,}000$ license plates.
• Permutations (order matters). $n$ different objects can be put in order in $n!$ ways. Picking $k$ of them in order: $P(n,k) = \frac{n!}{(n-k)!}$ ways. Example: a president, vice president, and secretary from $10$ people: $10\cdot9\cdot8 = 720$.
• Combinations (order does not matter). Choosing $k$ of $n$ different objects: $\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$. Also $\binom{n}{k} = \binom{n}{n-k}$ (choosing who is in is choosing who is out), and $\binom n0+\binom n1+\dots+\binom nn = 2^n$ (each object is in or out). Example: a $3$-person committee from $10$ people: $\frac{720}{3!} = 120$, since each committee has $3!$ orders.
• Repeated objects: $\frac{n!}{a!\,b!\cdots}$, where $a$, $b$, … count each group of identical objects. Example: ALABAMA has four A's, so $\frac{7!}{4!} = 210$ arrangements.
• Complementary counting. Count what you do not want and subtract from the total. Example: $5^4 = 625$ four-digit numbers use only odd digits, so $9000-625 = 8375$ have an even digit.

How AMC 10 tests it

• Problems 3–10: "How many three-digit numbers / license plates / subsets have property X?", by multiplying or by one $\binom{n}{k}$.
• Problems 10–18: choose-then-arrange questions (committees, handshakes, seating) where the trap is whether order matters.
• Digit problems that come down to short casework on the first digit.
• Counting the right thing: pairs of people, diagonals ($\binom{n}{2}-n$: pairs of corners minus the sides), crossing points of chords ($\binom{n}{4}$ for $n$ points on a circle, if no three chords meet at one point).
• The count is often the hidden step inside a probability problem.

Standard approaches

1. Decide whether order matters. Then build the object stage by stage and multiply.
2. If the total is quick to find, count the opposite and subtract.
3. Split into cases that do not overlap, based on the most limited spot (first digit, largest number, a special object), and add.
4. Look for a one-to-one correspondence with something you can count directly: strings of $0$s and $1$s, subsets, grid paths. Example: subsets of $\{1,2,3,4,5\}$ match the $0$-$1$ strings of length $5$ ($1$ means "in"), so there are $2^5 = 32$.
5. Check with a tiny case you can list by hand.

Worked example

How many four-digit positive integers have digits that are strictly increasing from left to right or strictly decreasing from left to right?

(A) $126$ (B) $210$ (C) $330$ (D) $336$ (E) $420$

Solution. Any four different digits can be written in increasing order in exactly one way, and in decreasing order in one way. So we count sets of four digits.

Step 1: increasing. A $0$ would be the smallest digit, so it would come first, which is not allowed. Choose $4$ digits from $1$ to $9$: $\binom94 = 126$.

Step 2: decreasing. Now a $0$ would come last, which is fine. Choose $4$ digits from $0$ to $9$: $\binom{10}{4} = 210$. (For example, $\{0,3,5,9\}$ gives $9530$.)

Step 3: add. No number is both: $126+210 = 336$.

The answer is $\boxed{\textbf{(D)}\ 336}$.

Pitfalls

• Multiplying when one stage's choices depend on an earlier choice. Use casework. Example: in a two-digit number whose second digit is bigger than the first, the second digit has $8$ choices after a $1$ but $1$ choice after an $8$.
• Mixing up $\binom{n}{k}$ and $P(n,k)$. A committee has no order; a line-up does.
• Forgetting that the first digit cannot be $0$, while $0$ is fine elsewhere. There are $900$ three-digit numbers, not $1000$.
• Counting things twice in "at least one" problems. Example: $3$-person committees from $5$ boys and $5$ girls with at least one girl: "pick a girl, then any $2$ others" gives $5\cdot\binom92 = 180$, but the answer is $\binom{10}{3}-\binom53 = 110$. Complementary counting avoids this.

Traps that recur

• Summing binom(9,k) 2^k instead of binom(9,k) 2^(k-1), which gives 3^9 - 1 = 19682, choice (E); the factor 2^(k-1) is right because the largest digit's position is forced. (2025 AMC 10A #24)
• Multiplying the 81 multiples of 11 by the number of permutations, which double counts triples like {2, 0, 9} that give two different multiples (209 and 902). (2017 AMC 10A #25)
• Answering 70 by assuming no three diagonals are concurrent; the regular octagon has concurrency at the center and at eight other points. (2013 AMC 10A #25)
• Forgetting that the two-friends case includes two separate triangles as well as one six-person loop, or overcounting loops by ignoring rotations and reflections. (2012 AMC 10A #23)