Generalized Permutations & Combinations

Textbook

Rosen 8e, Section 6.5

Study day

Tuesday, Nov 10

Homework

Written HW 9: 1–13 odd, 14–17, 20, 32–38, 64–68

Progress

Notes not read 0 / 25 problems graded

Work each problem on paper before opening its solution, then mark it Got it or Review. Do the Core problems first if you're short on time.

6.5 #1 Core Permutations w/ repetition

In how many different ways can five elements be selected in order from a set with three elements when repetition is allowed?

Show solution

Answer

3^{5} = 243

Ordered with repetition: $n^{r} = 3^{5} = 243$ .

6.5 #3 Core Permutations w/ repetition

How many strings of six letters are there?

Show solution

Answer

2 6^{6} = 308, 915, 776

Six positions, 26 choices each: $2 6^{6}$ .

6.5 #5 Core Permutations w/ repetition

How many ways are there to assign three jobs to five employees if each employee can be given more than one job?

Show solution

Answer

5^{3} = 125

Each job independently chooses an employee (5 ways), and repeats are allowed: $5^{3} = 125$ .

Watch the direction: it's $(choices per job)^{jobs}$ , not $3^{5}$ . Equivalently, count functions from jobs to employees: $∣ B ∣^{∣ A ∣} = 5^{3}$ .

6.5 #7 Core Combinations w/ repetition

How many ways are there to select three unordered elements from a set with five elements when repetition is allowed?

Show solution

Answer

(3 7) = 35

$n = 5$ types, $r = 3$ items: $(3 5 + 3 - 1) = (3 7) = 35$ .

6.5 #9 Core Stars and bars

A bagel shop has 8 kinds of bagels: onion, poppy seed, egg, salty, pumpernickel, sesame seed, raisin, and plain. How many ways are there to choose

a) six bagels?
b) a dozen bagels?
c) two dozen bagels?
d) a dozen bagels with at least one of each kind?
e) a dozen bagels with at least three egg bagels and no more than two salty bagels?

Show solution

Answer

a) 1716 b) 50,388 c) 2,629,575 d) 330 e) 9724

$n = 8$ types; formula $(r 8 + r - 1) = (7 r + 7)$ .

a) $(6 13) = 1716$

b) $(12 19) = (7 19) = 50, 388$

c) $(24 31) = (7 31) = 2, 629, 575$

d) Give one of each first (8 bagels), leaving 4 free: $(4 4 + 7) = (4 11) = 330$ .

e) Give 3 egg bagels first, leaving 9 to choose with salty $\leq 2$ .

All ways to choose 9: $(9 9 + 7) = (7 16) = 11, 440$
Bad (salty $\geq 3$ ): give 3 salty, leaving 6: $(6 6 + 7) = (6 13) = 1716$

Answer: $11, 440 - 1716 = 9724$ .

6.5 #11 Core Combinations w/ repetition

How many ways are there to choose eight coins from a piggy bank containing 100 identical pennies and 80 identical nickels?

Show solution

Answer

Two types, 8 items (supply is plentiful): $(8 2 + 8 - 1) = (8 9) = 9$ .

Directly: the number of pennies can be $0, 1, \dots, 8$ , which determines the selection. That's 9 ways.

6.5 #13 Core Stars and bars

A book publisher has 3000 copies of a discrete mathematics book. How many ways are there to store these books in their three warehouses if the copies of the book are indistinguishable?

Show solution

Answer

(2 3002) = 4, 504, 501

Solutions of $x_{1} + x_{2} + x_{3} = 3000$ with $x_{i} \geq 0$ : $(3 - 1 3000 + 3 - 1) = (2 3002) = \frac{3002 \cdot 3001}{2} = 4, 504, 501$ .

6.5 #14 Core Equations

How many solutions are there to the equation $x_{1} + x_{2} + x_{3} + x_{4} = 17$ , where $x_{1}, x_{2}, x_{3}, x_{4}$ are nonnegative integers?

Show solution

Answer

(3 20) = 1140

$n = 4$ variables, $r = 17$ : $(17 4 + 17 - 1) = (3 20) = \frac{20 \cdot 19 \cdot 18}{6} = 1140$ .

6.5 #15 Core Equations with bounds

How many solutions are there to $x_{1} + x_{2} + x_{3} + x_{4} + x_{5} = 21$ , where each $x_{i}$ is a nonnegative integer such that

a) $x_{1} \geq 1$ ?
b) $x_{i} \geq 2$ for $i = 1, \dots, 5$ ?
c) $0 \leq x_{1} \leq 10$ ?
d) $0 \leq x_{1} \leq 3$ , $1 \leq x_{2} < 4$ , and $x_{3} \geq 15$ ?

Show solution

Answer

a) 10,626 b) 1,365 c) 11,649 d) 106

5 variables, so the count for total $r$ is $(4 r + 4)$ .

a) Give 1 to $x_{1}$ : total 20. $(4 24) = 10, 626$ .

b) Give 2 to each (10 total): remaining 11. $(4 15) = 1365$ .

c) All: $(4 25) = 12, 650$ . Bad ( $x_{1} \geq 11$ ): remaining 10, $(4 14) = 1001$ . Answer $12, 650 - 1001 = 11, 649$ .

d) Lower bounds first: give $x_{2}$ 1 and $x_{3}$ 15, leaving $21 - 16 = 5$ . Let $x_{2}^{'} = x_{2} - 1$ , so now $x_{1} \leq 3$ and $x_{2}^{'} \leq 2$ , and the sum of the five variables is 5.

All: $(4 5 + 4) = (4 9) = 126$
$x_{1} \geq 4$ : remaining 1: $(4 5) = 5$
$x_{2}^{'} \geq 3$ : remaining 2: $(4 6) = 15$
Both: would need $4 + 3 = 7 > 5$ : 0

Inclusion–exclusion: $126 - 5 - 15 + 0 = 106$ .

6.5 #16 Core Equations with bounds

How many solutions are there to $x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} = 29$ , where each $x_{i}$ is a nonnegative integer such that

a) $x_{i} > 1$ for $i = 1, \dots, 6$ ?
b) $x_{1} \geq 1$ , $x_{2} \geq 2$ , $x_{3} \geq 3$ , $x_{4} \geq 4$ , $x_{5} > 5$ , and $x_{6} \geq 6$ ?
c) $x_{1} \leq 5$ ?
d) $x_{1} < 8$ and $x_{2} > 8$ ?

Show solution

Answer

a) 26,334 b) 792 c) 179,976 d) 46,942

6 variables, so the count for total $r$ is $(5 r + 5)$ .

a) $x_{i} > 1$ means $x_{i} \geq 2$ ; give out 12, leaving 17: $(5 22) = 26, 334$ .

b) $x_{5} > 5$ means $x_{5} \geq 6$ . Minimums sum to $1 + 2 + 3 + 4 + 6 + 6 = 22$ , leaving 7: $(5 12) = 792$ .

c) All: $(5 34) = 278, 256$ . Bad ( $x_{1} \geq 6$ ): leaving 23, $(5 28) = 98, 280$ . Answer: $179, 976$ .

d) $x_{2} > 8$ means $x_{2} \geq 9$ : give 9, leaving 20. Now $x_{1} \leq 7$ :

All: $(5 25) = 53, 130$
$x_{1} \geq 8$ : leaving 12, $(5 17) = 6188$

Answer $53, 130 - 6188 = 46, 942$ .

6.5 #17 Core Indistinguishable objects

How many strings of 10 ternary digits (0, 1, or 2) are there that contain exactly two 0s, three 1s, and five 2s?

Show solution

Answer

\frac{10 !}{2 ! 3 ! 5 !} = 2520

Arrange 10 symbols with repeats: $\frac{10 !}{2 ! 3 ! 5 !} = \frac{3 , 628 , 800}{2 \cdot 6 \cdot 120} = 2520$ .

(Or: $(2 10) (3 8) (5 5) = 45 \cdot 56 \cdot 1 = 2520$ .)

6.5 #20 Core Slack variable

How many solutions are there to the inequality $x_{1} + x_{2} + x_{3} \leq 11$ , where $x_{1}, x_{2}, x_{3}$ are nonnegative integers?

Show solution

Answer

(3 14) = 364

Add a slack variable $x_{4} = 11 - (x_{1} + x_{2} + x_{3}) \geq 0$ . Solutions of the inequality correspond one-to-one with solutions of
$x_{1} + x_{2} + x_{3} + x_{4} = 11, x_{i} \geq 0.$
Count: $(3 4 + 11 - 1) = (3 14) = 364$ .

6.5 #32 Core Indistinguishable objects

How many different strings can be made from the letters in MISSISSIPPI, using all the letters?

Show solution

Answer

\frac{11 !}{4 ! 4 ! 2 !} = 34, 650

M×1, I×4, S×4, P×2 (total 11):
$\frac{11 !}{1 ! 4 ! 4 ! 2 !} = 34, 650.$

6.5 #33 Core Indistinguishable objects

How many different strings can be made from the letters in ABRACADABRA, using all the letters?

Show solution

Answer

\frac{11 !}{5 ! 2 ! 2 !} = 83, 160

A×5, B×2, R×2, C×1, D×1 (total 11):
$\frac{11 !}{5 ! 2 ! 2 ! 1 ! 1 !} = \frac{39 , 916 , 800}{120 \cdot 4} = 83, 160.$

6.5 #34 Core Indistinguishable + block

How many different strings can be made from the letters in AARDVARK, using all the letters, if all three As must be consecutive?

Show solution

Answer

\frac{6 !}{2 !} = 360

Letters: A×3, R×2, D, V, K. Glue AAA into one block. Now arrange 6 objects: [AAA], R, R, D, V, K, where the two Rs are identical:
$\frac{6 !}{2 !} = 360.$

6.5 #35 Core Some or all letters

How many different strings can be made from the letters in ORONO, using some or all of the letters?

Show solution

Answer

Letters: O×3, R×1, N×1. Split by length.

Length	Cases	Count
1	O, R, N	3
2	OO (1); two different letters from {O,R,N}: $P (3, 2) = 6$	7
3	OOO (1); OO + R or N: $2 \cdot \frac{3 !}{2 !} = 6$ ; O,R,N: $3! = 6$	13
4	OOO + R or N: $2 \cdot \frac{4 !}{3 !} = 8$ ; OO,R,N: $\frac{4 !}{2 !} = 12$	20
5	OOO,R,N: $\frac{5 !}{3 !} = 20$	20

Total: $3 + 7 + 13 + 20 + 20 = 63$ .

6.5 #36 Core Some letters

How many strings with five or more characters can be formed from the letters in SEERESS?

Show solution

Answer

370

Letters: S×3, E×3, R×1 (7 total).

Length 7 (all): $\frac{7 !}{3 ! 3 !} = 140$ .

Length 6 (drop one letter):

drop S: S2 E3 R1 → $\frac{6 !}{2 ! 3 !} = 60$
drop E: S3 E2 R1 → $60$
drop R: S3 E3 → $\frac{6 !}{3 ! 3 !} = 20$

Total $140$ .

Length 5 (drop two letters):

drop SS: S1 E3 R1 → $\frac{5 !}{3 !} = 20$
drop EE: S3 E1 R1 → $20$
drop SE: S2 E2 R1 → $\frac{5 !}{2 ! 2 !} = 30$
drop SR: S2 E3 → $\frac{5 !}{2 ! 3 !} = 10$
drop ER: S3 E2 → $10$

Total $90$ .

Answer: $140 + 140 + 90 = 370$ .

6.5 #37 Extra Some letters

How many strings with seven or more characters can be formed from the letters in EVERGREEN?

Show solution

Answer

19,635

Letters: E×4, R×2, V, G, N (9 total).

Length 9: $\frac{9 !}{4 ! 2 !} = 7560$ .

Length 8 (drop one):

E → E3 R2 V G N: $\frac{8 !}{3 ! 2 !} = 3360$
R → E4 R1 V G N: $\frac{8 !}{4 !} = 1680$
V, G, or N → E4 R2 + two singles: $\frac{8 !}{4 ! 2 !} = 840$ each, so $2520$

Total $7560$ .

Length 7 (drop two):

EE → E2 R2 V G N: $\frac{7 !}{2 ! 2 !} = 1260$
E + R → E3 R1 V G N: $\frac{7 !}{3 !} = 840$
E + (V, G, or N) → E3 R2 + two singles: $\frac{7 !}{3 ! 2 !} = 420$ each, so $1260$
RR → E4 V G N: $\frac{7 !}{4 !} = 210$
R + (V, G, or N) → E4 R1 + two singles: $\frac{7 !}{4 !} = 210$ each, so $630$
two of {V, G, N} (3 ways) → E4 R2 + one single: $\frac{7 !}{4 ! 2 !} = 105$ each, so $315$

Total $1260 + 840 + 1260 + 210 + 630 + 315 = 4515$ .

Answer: $7560 + 7560 + 4515 = 19, 635$ .

6.5 #38 Core Indistinguishable objects

How many different bit strings can be formed using six 1s and eight 0s?

Show solution

Answer

(6 14) = 3003

$\frac{14 !}{6 ! 8 !} = (6 14) = 3003$ : choose the positions of the six 1s.

6.5 #64 Core Multinomial

How many different terms are there in the expansion of $(x_{1} + x_{2} + \dots + x_{m})^{n}$ after all terms with identical sets of exponents are added?

Show solution

Answer

(n n + m - 1)

Each term is $x_{1}^{n_{1}} \dots x_{m}^{n_{m}}$ with $n_{1} + \dots + n_{m} = n$ and $n_{i} \geq 0$ . Count the solutions (stars and bars, $m$ variables, total $n$ ):
$(n n + m - 1) = (m - 1 n + m - 1) .$

6.5 #65 Challenge Multinomial

Prove the Multinomial Theorem: if $n$ is a positive integer, then
$(x_{1} + x_{2} + \dots + x_{m})^{n} = n_{1} + \dots + n_{m} = n \sum C (n; n_{1}, \dots, n_{m}) x_{1}^{n_{1}} \dots x_{m}^{n_{m}}, C (n; n_{1}, \dots, n_{m}) = \frac{n !}{n _{1} ! \dots n _{m} !} .$

Show solution

Expand the product of $n$ factors $(x_{1} + \dots + x_{m}) (x_{1} + \dots + x_{m}) \dots$ . Each term of the expansion picks one $x_{i}$ from each factor, so every term has the form $x_{1}^{n_{1}} \dots x_{m}^{n_{m}}$ with $n_{1} + \dots + n_{m} = n$ .

The term $x_{1}^{n_{1}} \dots x_{m}^{n_{m}}$ appears once for each way of deciding which $n_{1}$ factors contribute $x_{1}$ , which $n_{2}$ contribute $x_{2}$ , and so on. That's the number of ways to arrange $n$ labels consisting of $n_{1}$ "1"s, $n_{2}$ "2"s, …, $n_{m}$ " $m$ "s, which by Theorem 3 is $\frac{n !}{n _{1} ! \dots n _{m} !}$ . Collecting like terms gives the formula. ∎

6.5 #66 Core Multinomial

Find the expansion of $(x + y + z)^{4}$ .

Show solution

Answer

15 terms: coefficients 1 ( $x^{4}$ type), 4 ( $x^{3} y$ type), 6 ( $x^{2} y^{2}$ type), 12 ( $x^{2} y z$ type)

Exponent patterns $(a, b, c)$ with $a + b + c = 4$ , coefficient $\frac{4 !}{a ! b ! c !}$ :

$(4, 0, 0)$ : $1$ → $x^{4}, y^{4}, z^{4}$
$(3, 1, 0)$ : $\frac{24}{6} = 4$ → $x^{3} y, x^{3} z, y^{3} x, y^{3} z, z^{3} x, z^{3} y$
$(2, 2, 0)$ : $\frac{24}{4} = 6$ → $x^{2} y^{2}, x^{2} z^{2}, y^{2} z^{2}$
$(2, 1, 1)$ : $\frac{24}{2} = 12$ → $x^{2} y z, x y^{2} z, x y z^{2}$

$(x + y + z)^{4} = x^{4} + y^{4} + z^{4} + 4 (x^{3} y + x^{3} z + x y^{3} + y^{3} z + x z^{3} + y z^{3}) + 6 (x^{2} y^{2} + x^{2} z^{2} + y^{2} z^{2}) + 12 (x^{2} y z + x y^{2} z + x y z^{2}) .$
Check: 15 terms $= (2 4 + 2)$ , and the coefficients sum to $3 + 24 + 18 + 36 = 81 = 3^{4}$ . ✓

6.5 #67 Core Multinomial

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

Show solution

Answer

\frac{10 !}{3 ! 2 ! 5 !} = 2520

Multinomial coefficient: $\frac{10 !}{3 ! 2 ! 5 !} = 2520$ .

6.5 #68 Core Multinomial

How many terms are there in the expansion of $(x + y + z)^{100}$ ?

Show solution

Answer

(2 102) = 5151

By #64 with $m = 3$ , $n = 100$ : $(100 100 + 3 - 1) = (2 102) = \frac{102 \cdot 101}{2} = 5151$ .

Custom (from lecture) Core Mixed Not from HW

a) How many ways can ABBCCCDDDDEEEEE be permuted?
b) Find the number of 6-combinations of $S = {1, 2, 3, 4}$ with repetition allowed.
c) How many ways are there to select 5 pieces of fruit from apples, oranges, and pears (at least 5 of each available)?
d) How many solutions does $x_{1} + x_{2} + x_{3} + x_{4} = 13$ have with all $x_{i} \in N$ ?
e) How many ways are there to select 8 bills from 1, 2, 5, 10, 20, 50, and 100 dollar bills (at least 8 of each)?

Show solution

Answer

a) $\frac{15 !}{1 ! 2 ! 3 ! 4 ! 5 !}$ b) 84 c) 21 d) 560 e) 3003

a) 15 letters: A×1, B×2, C×3, D×4, E×5: $\frac{15 !}{1 ! 2 ! 3 ! 4 ! 5 !} = 37, 837, 800$ .

b) $n = 4$ , $r = 6$ : $(6 9) = (3 9) = 84$ .

c) $n = 3$ , $r = 5$ : $(5 7) = 21$ .

d) $n = 4$ , $r = 13$ : $(13 16) = (3 16) = 560$ .

e) $n = 7$ , $r = 8$ : $(8 14) = (6 14) = 3003$ .

Next: Practice Exam