Permutations & Combinations

Textbook

Rosen 8e, Section 6.3

Study day

Sunday, Nov 8

Homework

Written HW 8: 1–41 odd

Progress

Notes not read 0 / 23 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.3 #1 Core Permutations

List all the permutations of ${a, b, c}$ .

Show solution

Answer

abc, acb, bac, bca, cab, cba

Fix the first letter, then arrange the remaining two: abc, acb, bac, bca, cab, cba. That's $3! = 6$ .

6.3 #3 Core Permutations

How many permutations of ${a, b, c, d, e, f, g}$ end with $a$ ?

Show solution

Answer

6! = 720

Fix $a$ in the last position; arrange the other 6 letters: $6! = 720$ .

6.3 #5 Core P(n,r)

Find the value of each of these quantities: a) $P (6, 3)$ b) $P (6, 5)$ c) $P (8, 1)$ d) $P (8, 5)$ e) $P (8, 8)$ f) $P (10, 9)$

Show solution

Answer

a) 120 b) 720 c) 8 d) 6720 e) 40320 f) 3628800

$P (n, r) = n (n - 1) \dots (n - r + 1)$ , a product of $r$ factors.

a) $6 \cdot 5 \cdot 4 = 120$
b) $6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 = 720$
c) $8$
d) $8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 = 6720$
e) $8! = 40, 320$
f) $10 \cdot 9 \dots 2 = 10! /1! = 3, 628, 800$

6.3 #7 Core P(n,r)

Find the number of 5-permutations of a set with nine elements.

Show solution

Answer

15,120

$P (9, 5) = 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 = 15, 120$ .

6.3 #9 Core P(n,r)

How many possibilities are there for the win, place, and show (first, second, and third) positions in a horse race with 12 horses if all orders of finish are possible?

Show solution

Answer

1320

Order matters (1st ≠ 2nd): $P (12, 3) = 12 \cdot 11 \cdot 10 = 1320$ .

6.3 #11 Core Bit strings

How many bit strings of length 10 contain

a) exactly four 1s?
b) at most four 1s?
c) at least four 1s?
d) an equal number of 0s and 1s?

Show solution

Answer

a) 210 b) 386 c) 848 d) 252

Row 10 of Pascal's triangle: 1, 10, 45, 120, 210, 252, …

a) Choose positions of the four 1s: $(4 10) = 210$ .

b) $(0 10) + (1 10) + (2 10) + (3 10) + (4 10) = 1 + 10 + 45 + 120 + 210 = 386$ .

c) Complement of "at most three": $2^{10} - (1 + 10 + 45 + 120) = 1024 - 176 = 848$ .

d) Five 1s: $(5 10) = 252$ .

6.3 #13 Core Arrangements

A group contains $n$ men and $n$ women. How many ways are there to arrange these people in a row if the men and women alternate?

Show solution

Answer

2 (n!)^{2}

The pattern is either MWMW… or WMWM…: 2 choices. Then arrange the men in their $n$ spots ( $n!$ ) and the women in theirs ( $n!$ ):
$2 \cdot n! \cdot n! = 2 (n!)^{2} .$

6.3 #15 Core Combinations

In how many ways can a set of five letters be selected from the English alphabet?

Show solution

Answer

(5 26) = 65, 780

A set, so order doesn't matter: $(5 26) = \frac{26 \cdot 25 \cdot 24 \cdot 23 \cdot 22}{120} = 65, 780$ .

6.3 #17 Core Complement

How many subsets with more than two elements does a set with 100 elements have?

Show solution

Answer

2^{100} - 5051

All subsets minus those of size 0, 1, 2:
$2^{100} - (0 100) - (1 100) - (2 100) = 2^{100} - 1 - 100 - 4950 = 2^{100} - 5051.$

6.3 #19 Core Coin flips

A coin is flipped 10 times where each flip comes up either heads or tails. How many possible outcomes

a) are there in total?
b) contain exactly two heads?
c) contain at most three tails?
d) contain the same number of heads and tails?

Show solution

Answer

a) 1024 b) 45 c) 176 d) 252

An outcome is a length-10 H/T string, like a bit string.

a) $2^{10} = 1024$
b) $(2 10) = 45$
c) $(0 10) + (1 10) + (2 10) + (3 10) = 1 + 10 + 45 + 120 = 176$
d) $(5 10) = 252$

6.3 #21 Core Substrings

How many permutations of the letters ABCDEFG contain

a) the string BCD?
b) the string CFGA?
c) the strings BA and GF?
d) the strings ABC and DE?
e) the strings ABC and CDE?
f) the strings CBA and BED?

Show solution

Answer

a) 120 b) 24 c) 120 d) 24 e) 6 f) 0

Glue each required string into a block and count units.

a) [BCD], A, E, F, G: 5 units, $5! = 120$ .

b) [CFGA], B, D, E: 4 units, $4! = 24$ .

c) [BA], [GF], C, D, E: 5 units, $5! = 120$ .

d) [ABC], [DE], F, G: 4 units, $4! = 24$ .

e) ABC and CDE share the C, so they must overlap as [ABCDE]. With F, G that's 3 units: $3! = 6$ .

f) CBA needs B followed by A; BED needs B followed by E. B can't be followed by two different letters: 0.

6.3 #23 Core Gap method

How many ways are there for eight men and five women to stand in a line so that no two women stand next to each other?

Show solution

Answer

8! \cdot P (9, 5) = 609, 638, 400

Gap method. First line up the 8 men: $8!$ ways. This creates 9 gaps (before, between, and after the men):
$_M_M_M_M_M_M_M_M_$
Put the 5 women in 5 different gaps, in order: $P (9, 5) = 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 = 15, 120$ .

Total: $8! \cdot 15, 120 = 40, 320 \cdot 15, 120 = 609, 638, 400$ .

6.3 #25 Core Blocks

How many ways are there for four men and five women to stand in a line so that

a) all men stand together?
b) all women stand together?

Show solution

Answer

a) 17,280 b) 14,400

a) Treat the 4 men as one block: block + 5 women = 6 units, $6!$ ways. Arrange the men inside the block: $4!$ .
$6! \cdot 4! = 720 \cdot 24 = 17, 280.$

b) Women block + 4 men = 5 units, $5!$ ways; women inside the block, $5!$ :
$5! \cdot 5! = 120 \cdot 120 = 14, 400.$

6.3 #27 Core Permutations with conditions

One hundred tickets, numbered 1–100, are sold to 100 different people. Four different prizes are awarded, including a grand prize. How many ways are there to award the prizes if

a) there are no restrictions?
b) the person holding ticket 47 wins the grand prize?
c) the person holding ticket 47 wins one of the prizes?
d) the person holding ticket 47 does not win a prize?
e) the people holding tickets 19 and 47 both win prizes?
f) the people holding tickets 19, 47, and 73 all win prizes?
g) the people holding tickets 19, 47, 73, and 97 all win prizes?
h) none of the people holding tickets 19, 47, 73, and 97 wins a prize?
i) the grand prize winner is a person holding ticket 19, 47, 73, or 97?
j) the people holding tickets 19 and 47 win prizes, but the people holding tickets 73 and 97 do not win prizes?

Show solution

Answer

a) 94,109,400 b) 941,094 c) 3,764,376 d) 90,345,024 e) 114,072 f) 2,328 g) 24 h) 79,727,040 i) 3,764,376 j) 109,440

Prizes are different, so order matters: assign prize 1, prize 2, prize 3, prize 4 to distinct tickets.

a) $P (100, 4) = 100 \cdot 99 \cdot 98 \cdot 97 = 94, 109, 400$

b) Grand prize fixed to 47; the other 3 prizes go to the remaining 99: $P (99, 3) = 99 \cdot 98 \cdot 97 = 941, 094$

c) Choose which prize 47 wins (4), then the other 3 prizes: $4 \cdot P (99, 3) = 3, 764, 376$

d) All four prizes from the other 99: $P (99, 4) = 90, 345, 024$

e) Prizes for 19 and 47: $4 \cdot 3 = 12$ ; remaining 2 prizes from 98 people: $P (98, 2) = 9506$ . Total $12 \cdot 9506 = 114, 072$

f) Prizes for 19, 47, 73: $4 \cdot 3 \cdot 2 = 24$ ; last prize from 97 people: $24 \cdot 97 = 2328$

g) The four people get the four prizes in some order: $4! = 24$

h) From the other 96 people: $P (96, 4) = 96 \cdot 95 \cdot 94 \cdot 93 = 79, 727, 040$

i) Grand prize to one of the 4 (4 ways); the other 3 prizes among the remaining 99: $4 \cdot P (99, 3) = 3, 764, 376$

j) 19 and 47 get prizes: $4 \cdot 3 = 12$ ; the other 2 prizes go to the 96 people excluding 19, 47, 73, 97: $P (96, 2) = 9120$ . Total $12 \cdot 9120 = 109, 440$

6.3 #29 Core P vs C

A club has 25 members.

a) How many ways are there to choose four members of the club to serve on an executive committee?
b) How many ways are there to choose a president, vice president, secretary, and treasurer of the club, where no person can hold more than one office?

Show solution

Answer

a) 12,650 b) 303,600

a) Committee, so unordered: $(4 25) = \frac{25 \cdot 24 \cdot 23 \cdot 22}{24} = 12, 650$ .

b) Titled offices, so ordered: $P (25, 4) = 25 \cdot 24 \cdot 23 \cdot 22 = 303, 600$ .

(Check: $(b) = (a) \cdot 4!$ .)

6.3 #31 Challenge Inclusion–exclusion

How many 4-permutations of the positive integers not exceeding 100 contain three consecutive integers $k, k + 1, k + 2$ , in the correct order

a) where these consecutive integers can perhaps be separated by other integers in the permutation?
b) where they are in consecutive positions in the permutation?

Show solution

Answer

a) 37,927 b) 18,915

$k$ ranges over $1, \dots, 98$ .

b) Choose $k$ (98 ways). The block $k, k + 1, k + 2$ occupies positions 1–3 or 2–4 (2 ways). The remaining slot gets any of the other 97 numbers. That gives $98 \cdot 2 \cdot 97 = 19, 012$ .
Overcount: the permutation $k, k + 1, k + 2, k + 3$ contains two blocks ( $k$ in positions 1–3 and $k + 1$ in 2–4) and is counted twice. There are 97 of these ( $k = 1..97$ ). Answer: $19, 012 - 97 = 18, 915$ .

a) Choose $k$ (98), which 3 of the 4 positions hold $k, k + 1, k + 2$ in order ( $(3 4) = 4$ ), and the fourth number (97): $98 \cdot 4 \cdot 97 = 38, 024$ .
Overcount: a permutation containing two such triples must be $k, k + 1, k + 2, k + 3$ in increasing order (97 of them), each counted twice. Answer: $38, 024 - 97 = 37, 927$ .

6.3 #33 Core Exactly / at least

The English alphabet contains 21 consonants and five vowels. How many strings of six lowercase letters of the English alphabet contain

a) exactly one vowel?
b) exactly two vowels?
c) at least one vowel?
d) at least two vowels?

Show solution

Answer

a) $6 \cdot 5 \cdot 2 1^{5}$ b) $(2 6) 5^{2} 2 1^{4}$ c) $2 6^{6} - 2 1^{6}$ d) $2 6^{6} - 2 1^{6} - 6 \cdot 5 \cdot 2 1^{5}$

Letters may repeat (it's a string).

a) Position of the vowel: $(1 6) = 6$ ; which vowel: 5; the other 5 letters are consonants: $2 1^{5}$ .
$6 \cdot 5 \cdot 2 1^{5} = 122, 523, 030$

b) Positions: $(2 6) = 15$ ; vowels: $5^{2}$ ; consonants: $2 1^{4}$ .
$15 \cdot 25 \cdot 2 1^{4} = 72, 930, 375$

c) Complement: $2 6^{6} - 2 1^{6} = 223, 149, 655$ .

d) At least one, minus exactly one: $223, 149, 655 - 122, 523, 030 = 100, 626, 625$ .

6.3 #35 Core Committees

Suppose that a department contains 10 men and 15 women. How many ways are there to form a committee with six members if it must have the same number of men and women?

Show solution

Answer

(3 10) (3 15) = 54, 600

3 men and 3 women: $(3 10) (3 15) = 120 \cdot 455 = 54, 600$ .

6.3 #37 Core Clever encoding

How many bit strings contain exactly eight 0s and 10 1s if every 0 must be immediately followed by a 1?

Show solution

Answer

(2 10) = 45

Each 0 is glued to the 1 after it, making 8 blocks "01". That uses 8 of the 1s, leaving 2 single "1"s. Arrange 8 identical "01" blocks and 2 identical "1"s: 10 objects, choose the positions of the two lone 1s:
$(2 10) = 45.$

6.3 #39 Core Sums of binomials

How many bit strings of length 10 contain at least three 1s and at least three 0s?

Show solution

Answer

912

The number of 1s must be between 3 and 7 (so that there are at least 3 zeros):
$(3 10) + (4 10) + (5 10) + (6 10) + (7 10) = 120 + 210 + 252 + 210 + 120 = 912.$

6.3 #41 Core Product rule

How many license plates consisting of three letters followed by three digits contain no letter or digit twice?

Show solution

Answer

11,232,000

$P (26, 3) \cdot P (10, 3) = (26 \cdot 25 \cdot 24) (10 \cdot 9 \cdot 8) = 15, 600 \cdot 720 = 11, 232, 000$ .

Custom (from lecture) Core P vs C Not from HW

a) How many 5-card poker hands can be drawn from a standard 52-card deck?
b) How many 47-card hands? Why is the answer the same?
c) A college has 10 math and 12 sociology faculty. How many committees have 3 math and 5 sociology faculty?
d) How many bit strings of length $n$ contain exactly $k$ 1s?

Show solution

Answer

a) $(5 52) = 2, 598, 960$ b) same c) $(3 10) (5 12) = 95, 040$ d) $(k n)$

a) A hand is unordered: $(5 52) = \frac{52 \cdot 51 \cdot 50 \cdot 49 \cdot 48}{120} = 2, 598, 960$ .

b) $(47 52) = (5 52)$ . Choosing the 47 cards you keep is the same as choosing the 5 you leave out (symmetry).

c) Product rule: $(3 10) (5 12) = 120 \cdot 792 = 95, 040$ .

d) Choose which $k$ of the $n$ positions are 1s: $(k n)$ .

Custom Core At least one (trap) Not from HW

A committee of 5 is chosen from 7 women and 9 men.

a) How many committees have at least one woman?
b) What is wrong with the answer $(1 7) (4 15)$ ?

Show solution

Answer

a) $(5 16) - (5 9) = 4368 - 126 = 4242$

a) Complement: all committees minus all-men committees:
$(5 16) - (5 9) = 4368 - 126 = 4242.$

b) "Pick one woman, then any 4 others" counts a committee with $w$ women $w$ times, once for each woman you could have picked first. For example, ${W_{1}, W_{2}, M_{1}, M_{2}, M_{3}}$ gets counted via $W_{1}$ and via $W_{2}$ . So $7 \cdot 1365 = 9555$ overcounts.

Next: 6.4 Binomial Coefficients & Identities