Repeats, chips and dividers

Idea: Label the copies, then forget the labels

Make repeated letters distinct, count, then divide by the orders of the copies.

• $\text{PEPPER}$: $6!=720$ labelled orders
• Each word comes from $3!\times 2!=12$ of them
• Words: $\frac{720}{12}=60$

Formula: Words with repeats

$\frac{n!}{a!\times b!\times c!\times \dots }$

n letters with repeat counts a, b, c. A letter used once adds 1! = 1.

Example: The letters of $\text{LEVEL}$

How many different strings use all the letters of $\text{LEVEL}$?

1. $5$ letters: $L$ and $E$ appear twice each
2. Strings: $\frac{5!}{2!\times 2!}=30$

Formula: Chips and dividers

$\left(\genfrac{}{}{0ex}{}{n+b-1}{b-1}\right)$

n identical items in b different boxes, empty boxes allowed: choose where the b − 1 dividers go.

Example: 8 chips, 3 boxes

Put $8$ identical chips into $3$ different boxes; a box may stay empty. How many ways?

1. Picture: $8$ stars and $2$ dividers, $10$ symbols
2. Choose the dividers: $\left(\genfrac{}{}{0ex}{}{10}{2}\right)=45$

Idea: Minimums go first

If every box needs at least $1$ chip, hand those out first.

• $8-3=5$ chips left, no restriction
• Count: $\left(\genfrac{}{}{0ex}{}{7}{2}\right)=21$
• A maximum needs inclusion and exclusion instead

Common mistake: The wrong kind of items

Dividers need identical items and different boxes.

Instead Distinct chips give $3^8=6561$. And $3$ boxes need $2$ dividers, not $3$.

Quick check: 6 chips, 4 boxes

In how many ways can $6$ identical chips go into $4$ different boxes, empty boxes allowed?

Idea: Before you touch a formula

Say what is identical, what is distinct, and whether boxes may be empty.

• Those words pick the method
• For a word, say what you divide out