Fundamental Counting: Permutations & Combinations

A plate has 2 letters ($A$--$Z$) followed by 3 digits ($0$--$9$). How many plates are possible?

Solution. Five independent stages: $26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 = 676{,}000$. Now suppose the first symbol may be either a letter or a digit (so $26+10=36$ choices) while the rest stay as before: the count becomes $36 \cdot 26 \cdot 10^3$. The “either/or” at one stage is an addition inside a multiplication.

How many 3-digit numbers (100--999) contain at least one digit equal to $7$?

Solution. Complementary counting is cleanest: total 3-digit numbers $=900$. Those with no $7$: first digit has $8$ choices ($1$--$9$ except $7$), the other two have $9$ each, giving $8\cdot 9 \cdot 9 = 648$. So the answer is $900-648 = 252$.

In a race of $8$ runners, how many ways can the gold, silver, and bronze medals be awarded (no ties)?

Solution. Order matters and there is no repetition, so

How many ways can $5$ distinct books be lined up on a shelf if the dictionary must be on one of the two ends?

Solution. Place the dictionary first: $2$ end choices. Arrange the other $4$ books in the remaining slots: $4! = 24$. Total $2 \cdot 24 = 48$. Handle the restricted object first.

From $10$ people, how many ways can we choose a committee of $4$?

Solution. Order is irrelevant: $\binom{10}{4} = \frac{10\cdot 9\cdot 8\cdot 7}{4\cdot 3\cdot 2\cdot 1} = 210.$

A club has $6$ freshmen and $5$ seniors. How many $4$-person committees have exactly $2$ freshmen?

Solution. Choose $2$ of $6$ freshmen and $2$ of $5$ seniors: $\binom{6}{2}\binom{5}{2} = 15\cdot 10 = 150$. (Multiplication principle joins two independent choices.)

How many distinct arrangements of the letters in MISSISSIPPI are there?

Solution. There are $11$ letters: $M{\times}1,\ I{\times}4,\ S{\times}4,\ P{\times}2$. So

How many shortest grid paths go from $(0,0)$ to $(4,3)$ moving only right (R) or up (U)?

Solution. Every path is a sequence of $4$ R's and $3$ U's, so we arrange $7$ steps:

Lattice-path counting is really “permutations with identical objects” in disguise --- a favorite contest trick.

In how many ways can $6$ people sit at a round table if only relative order matters?

Solution. $(6-1)! = 5! = 120$.

$5$ couples sit around a round table so that partners are adjacent. How many seatings (rotations equivalent)?

Solution. Treat each couple as a block: arrange $5$ blocks around the circle in $(5-1)! = 24$ ways, then order the two partners within each block: $2^5 = 32$. Total $24 \cdot 32 = 768$.

From $9$ students:

• 2pt
• How many ways to pick a $3$-person study group?   $\binom{9}{3}=84$ (order doesn't matter).
• How many ways to pick a President, VP, and Treasurer?   $P(9,3)=9\cdot 8\cdot 7 = 504$ (distinct roles $\Rightarrow$ order matters).

Notice $504 = 84 \cdot 3! = 84\cdot 6$.

How many distinct triangles can be drawn using $8$ points on a circle as vertices (no three collinear)?

Solution. A triangle is just an unordered choice of $3$ vertices, so $\binom{8}{3}=56$. If you had counted ordered triples $8\cdot 7\cdot 6 = 336$, you would be overcounting each triangle by its $3! = 6$ vertex orderings: $336/6 = 56$. Recognizing the hidden symmetry factor is the whole game.

In how many ways can $6$ distinct players be split into $3$ unlabeled pairs?

Solution. If the pairs were labeled (Court 1, 2, 3), the count would be $\binom{6}{2}\binom{4}{2}\binom{2}{2} = 15\cdot 6\cdot 1 = 90$. But the $3!$ orderings of the (identical-status) pairs are the same partition, so divide: $90/3! = 15$. Dividing by the arrangements of interchangeable groups is the most common contest overcount.

How many $4$-digit numbers (1000--9999) have at least one repeated digit?

Solution. Total $=9000$. All-distinct: $9\cdot 9\cdot 8\cdot 7 = 4536$ (first digit $1$--$9$, then any unused digit including $0$). At least one repeat $=9000 - 4536 = 4464$. When “at least one” appears, subtract the “none” case.

How many ways can we write $x_1 + x_2 + x_3 + x_4 = 10$ with each $x_i$ a nonnegative integer?

Solution. Encode a solution as a row of $10$ stars split into $4$ groups by $3$ bars, e.g.

Every solution gives exactly one such string of $10$ stars and $3$ bars, and every string decodes to exactly one solution --- a bijection. Counting the strings is a “permutations with identical objects” problem on $13$ symbols:

In general $x_1 + \cdots + x_k = n$ (nonnegatives) has $\binom{n+k-1}{k-1}$ solutions.

How many subsets of $\{1,2,\dots,12\}$ contain no two consecutive integers?

Solution. Suppose we pick $k$ elements $a_1 < a_2 < \cdots < a_k$ with each gap $a_{i+1}-a_i \ge 2$. Define $b_i = a_i - (i-1)$. This subtracts off the forced gaps, and the map $\{a_i\}\mapsto\{b_i\}$ is a bijection onto the $k$-element subsets of $\{1,2,\dots,12-(k-1)\} = \{1,\dots,13-k\}$ with no restriction. Hence the count for each $k$ is $\binom{13-k}{k}$, and summing over all $k$:

(These are Fibonacci numbers --- a bijection can expose hidden structure, not just a number.)

Let $X = \{1,2,3,4\}$ and $Y = \{a,b,c\}$, so $n=4$, $m=3$.

Solution.

• 2pt
• All functions: $3^4 = 81$.
• Injective functions: impossible, since $n=4 > 3 = m$; count $=0$.
• Surjective functions: $\displaystyle\sum_{j=0}^{3}(-1)^j\binom{3}{j}(3-j)^4 = 3^4 - 3\cdot 2^4 + 3\cdot 1^4 - 0 = 81 - 48 + 3 = 36.$

Sanity check: a surjection from a $4$-set onto a $3$-set forces exactly one output to be used twice. Choose the doubled output ($3$ ways), choose which $2$ of the $4$ inputs share it ($\binom{4}{2}=6$), then biject the remaining $2$ inputs to the remaining $2$ outputs ($2!=2$): $3\cdot 6\cdot 2 = 36$. ✓

Find the coefficient of $x^{3}y^{2}z^{2}$ in the expansion of $(x + y + z)^{7}$.

Solution. Here $n=7$ with exponents $(k_1,k_2,k_3) = (3,2,2)$, which sum to $7$:

In how many ways can a standard $52$-card deck be dealt into four labeled hands (North, East, South, West) of $13$ cards each?

Solution. This is a distribution of $52$ distinct objects into $4$ labeled boxes of size $13$:

If instead the four hands were unlabeled (just a partition into four piles of $13$, no seat names), we would divide by the $4!$ orderings of the interchangeable piles: $\dfrac{52!}{(13!)^{4}\,4!}$.

Distribute balls into $3$ boxes; compare the four “any” entries for small cases.

Solution.

• 2pt
• Distinct balls, distinct boxes, $n=4$: functions $\{1,2,3,4\}\to\{$box$_1,$box$_2,$box$_3\}$, so $3^4 = 81$.
• Identical balls, distinct boxes, $n=4$: stars and bars, $\binom{4+3-1}{4} = \binom{6}{4} = 15$.
• Distinct balls, identical boxes, $n=4$ into at most $3$ nonempty groups: $S(4,1)+S(4,2)+S(4,3) = 1 + 7 + 6 = 14$.
• Identical balls, identical boxes, $n=4$ into at most $3$ parts: partitions of $4$ with $\le 3$ parts: $4,\ 3{+}1,\ 2{+}2,\ 2{+}1{+}1$, so $4$.

Same phrase, four genuinely different answers --- the two “distinguishable?” switches are everything.