6.5 Generalized Permutations & Combinations

Now repetition is allowed, and some objects can be identical. Only subsections 6.5.1–6.5.4 are on the exam. Skip 6.5.5 (distributing objects into boxes).

The master table

The four counting formulas. Memorize this table.

Selecting $r$ items from $n$ types/objects:

	No repetition	Repetition allowed
Order matters	$P (n, r) = \frac{n !}{( n - r )!}$	$n^{r}$
Order doesn't matter	$(r n)$	$(r n + r - 1)$

Plus: arranging $n$ objects where $n_{1}$ are identical of type 1, …, $n_{k}$ identical of type $k$ :
$\frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}$

Permutations with repetition

Theorem 1

The number of $r$ -permutations of a set of $n$ objects with repetition allowed is $n^{r}$ .

Each of the $r$ positions independently gets any of the $n$ objects (product rule). Example from class: strings of length $k$ over the 26 uppercase letters: $2 6^{k}$ .

Combinations with repetition (stars and bars)

Theorem 2

The number of $r$ -combinations from a set with $n$ elements with repetition allowed is
$C (n + r - 1, r) = C (n + r - 1, n - 1) .$

Stars and bars. Know why it works.

Represent a selection of $r$ items from $n$ types as $r$ stars and $n - 1$ bars (dividers between the $n$ types). For example, with 4 types and 6 items:
$⋆ ⋆ ∣ ⋆ ∣ ∣ ⋆ ⋆ ⋆ = 2 of type 1, 1 of type 2, 0 of type 3, 3 of type 4.$
Every arrangement of $r$ stars and $n - 1$ bars is one selection, so the count is the number of ways to choose star positions among $n + r - 1$ spots: $(r n + r - 1)$ .

Memory aid: $(items items + types - 1)$ or, equivalently, $(types - 1 items + types - 1)$ .

From class

6-combinations of ${1, 2, 3, 4}$ with repetition: $(6 4 + 6 - 1) = (6 9) = 84$ .
5 pieces of fruit from apples, oranges, pears: $(5 3 + 5 - 1) = (5 7) = 21$ .
8 bills from 7 denominations (1, 2, 5, 10, 20, 50, 100): $(8 7 + 8 - 1) = (8 14) = 3003$ .

Integer solutions of equations

Equations are stars and bars

The number of solutions of $x_{1} + x_{2} + \dots + x_{n} = r$ with every $x_{i} \geq 0$ an integer is
$(r n + r - 1) = (n - 1 n + r - 1) .$
( $x_{i}$ = how many items of type $i$ ; $n$ variables = $n$ types.)

From class:

x_{1} + x_{2} + x_{3} + x_{4} = 13

x_{i} \in N

$(13 4 + 13 - 1) = (13 16) = (3 16) = 560$ .

Handling constraints

Lower bound $x_{i} \geq a$ : give $a$ to $x_{i}$ up front. Subtract $a$ from the total, then count normally.
Upper bound $x_{i} \leq b$ : complement. (All solutions) − (solutions with $x_{i} \geq b + 1$ ).
Two upper bounds: inclusion–exclusion. All − (first violated) − (second violated) + (both violated).
Inequality $x_{1} + \dots + x_{n} \leq r$ : add a slack variable $x_{n + 1} \geq 0$ to make it $x_{1} + \dots + x_{n + 1} = r$ .

x_{1} + x_{2} + x_{3} = 11

with

x_{1} \geq 1

x_{2} \geq 2

x_{3} \geq 3

(textbook)

Give out $1 + 2 + 3 = 6$ first, leaving $5$ to distribute freely among 3 variables: $(5 3 + 5 - 1) = (5 7) = 21$ .

x_{1} + x_{2} + x_{3} + x_{4} = 20

with

x_{1} \leq 4

All solutions: $(3 23) = 1771$ . Bad ones ( $x_{1} \geq 5$ ): give 5 to $x_{1}$ , leaving 15: $(3 18) = 816$ . Answer: $1771 - 816 = 955$ .

Permutations with indistinguishable objects

Theorem 3

The number of different permutations of $n$ objects, where there are $n_{1}$ indistinguishable objects of type 1, $n_{2}$ of type 2, …, $n_{k}$ of type $k$ , is
$\frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !} .$

Why: place the type-1 objects in $(n _{1} n)$ ways, then type 2 in $(n _{2} n - n _{1})$ ways, and so on. The product telescopes to the formula. Equivalently: $n!$ arrangements, but each is counted $n_{1}! \dots n_{k}!$ times because swapping identical letters changes nothing.

From class

SUCCESS (S×3, C×2, U, E): $\frac{7 !}{3 ! 2 !} = 420$ .
MISSISSIPPI (M×1, I×4, S×4, P×2): $\frac{11 !}{4 ! 4 ! 2 !} = 34, 650$ .
ABBCCCDDDDEEEEE: $\frac{15 !}{1 ! 2 ! 3 ! 4 ! 5 !}$ .

"Using some or all of the letters"

Split by length and by which letters are used (sum rule), applying $n! / (n_{1}! \dots)$ to each case. Organize by how many copies of the repeated letter you use.

Bit strings are a special case

Bit strings with six 1s and eight 0s: $\frac{14 !}{6 ! 8 !} = (6 14)$ . Two types of identical objects is just a binomial coefficient.

The multinomial theorem

Multinomial theorem

(x_{1} + x_{2} + \dots + x_{m})^{n} = n_{1} + \dots + n_{m} = n \sum \frac{n !}{n _{1} ! n _{2} ! \dots n _{m} !} x_{1}^{n_{1}} x_{2}^{n_{2}} \dots x_{m}^{n_{m}}

Multinomial facts

Coefficient of $x^{a} y^{b} z^{c}$ in $(x + y + z)^{n}$ (with $a + b + c = n$ ): $\frac{n !}{a ! b ! c !}$ .
Number of distinct terms in $(x_{1} + \dots + x_{m})^{n}$ : $(n n + m - 1)$ . That's stars and bars, distributing the exponent $n$ among $m$ variables.

Which formula? A decision guide

Ask these in order

Are some of the objects identical and you're arranging all of them (letters of a word)? Use $\frac{n !}{n _{1} ! \dots n _{k} !}$ .
Does order matter?
- Yes, with repetition: $n^{r}$ . Without: $P (n, r)$ .
- No, with repetition ("choose 12 donuts from 21 kinds", "solutions of $x_{1} + \dots = r$ "): $(r n + r - 1)$ . Without: $(r n)$ .
Constraints? Lower bounds: give them out first. Upper bounds: complement / inclusion–exclusion.

Common mistakes

Using $(r n)$ when repetition is allowed. "Choose 3 donuts from 5 kinds" is $(3 7) = 35$ , not $(3 5) = 10$ .
Mixing up $n$ and $r$ in $(r n + r - 1)$ : $n$ = number of types, $r$ = number of items chosen.
Forgetting that "at least one of each" means subtract one per type first.

Exam checklist

Pick the right formula from the master table.
Stars and bars, including lower/upper bounds and $\leq$ (slack variable).
Rearrangements of words with repeated letters; "some or all of the letters" by cases.
Multinomial coefficients and number of terms.