The Basics of Counting

Textbook

Rosen 8e, Section 6.1

Study day

Saturday, Nov 7

Homework

Written HW 7: 1–17 odd, 21–37 odd, 41, 45–59 odd, 63–73 odd

Progress

Notes not read 0 / 35 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.1 #1 Core Product vs sum

There are 18 mathematics majors and 325 computer science majors at a college.

a) In how many ways can two representatives be picked so that one is a mathematics major and the other is a computer science major?
b) In how many ways can one representative be picked who is either a mathematics major or a computer science major?

Show solution

Answer

a) 5850 b) 343

a) Two tasks in sequence (pick the math rep, then the CS rep), so use the product rule: $18 \cdot 325 = 5850$ .

b) One choice from one of two disjoint groups, so use the sum rule: $18 + 325 = 343$ .

6.1 #3 Core Product rule

A multiple-choice test contains 10 questions. There are four possible answers for each question.

a) In how many ways can a student answer the questions on the test if the student answers every question?
b) In how many ways can a student answer the questions on the test if the student can leave answers blank?

Show solution

Answer

a) $4^{10} = 1, 048, 576$ b) $5^{10} = 9, 765, 625$

a) 10 questions, 4 choices each: $4^{10}$ .

b) "Blank" is a fifth option for each question: $5^{10}$ .

6.1 #5 Core Product rule

Six different airlines fly from New York to Denver and seven fly from Denver to San Francisco. How many different pairs of airlines can you choose on which to book a trip from New York to San Francisco via Denver, when you pick an airline for the flight to Denver and an airline for the continuation flight to San Francisco?

Show solution

Answer

Two legs in sequence: $6 \cdot 7 = 42$ .

6.1 #7 Core Product rule

How many different three-letter initials can people have?

Show solution

Answer

2 6^{3} = 17, 576

Three positions, 26 letters each, repetition allowed: $2 6^{3} = 17, 576$ .

6.1 #9 Core Product rule

How many different three-letter initials are there that begin with an A?

Show solution

Answer

2 6^{2} = 676

The first letter is fixed (1 way); the other two are free: $1 \cdot 26 \cdot 26 = 676$ .

6.1 #11 Core Bit strings

How many bit strings of length ten both begin and end with a 1?

Show solution

Answer

2^{8} = 256

Positions 1 and 10 are fixed as 1; the 8 middle bits are free: $2^{8} = 256$ .

6.1 #13 Core Sum rule

How many bit strings with length not exceeding $n$ , where $n$ is a positive integer, consist entirely of 1s, not counting the empty string?

Show solution

Answer

n

For each length $ℓ = 1, 2, \dots, n$ there is exactly one all-1s string ( $11 \dots 1$ ). By the sum rule the total is $1 + 1 + \dots + 1 = n$ . (The book's answer $n + 1$ includes the empty string, which this question excludes.)

6.1 #15 Core Sum rule

How many strings are there of lowercase letters of length four or less, not counting the empty string?

Show solution

Answer

26 + 2 6^{2} + 2 6^{3} + 2 6^{4} = 475, 254

Split by length (sum rule), using the product rule within each length:
$26 + 2 6^{2} + 2 6^{3} + 2 6^{4} = 26 + 676 + 17, 576 + 456, 976 = 475, 254.$
(The book lists 475,255, which counts the empty string too.)

6.1 #17 Core Complement

How many strings of five ASCII characters contain the character @ ("at" sign) at least once? (There are 128 different ASCII characters.)

Show solution

Answer

12 8^{5} - 12 7^{5} = 1, 321, 368, 961

"At least once," so count the complement:
$all strings 12 8^{5} - no @ 12 7^{5} = 1, 321, 368, 961.$

6.1 #21 Core Multiples

How many positive integers between 50 and 100

a) are divisible by 7? Which integers are these?
b) are divisible by 11? Which integers are these?
c) are divisible by both 7 and 11? Which integers are these?

Show solution

Answer

a) 7: 56, 63, 70, 77, 84, 91, 98 b) 5: 55, 66, 77, 88, 99 c) 1: 77

a) $⌊ 100/7 ⌋ - ⌊ 49/7 ⌋ = 14 - 7 = 7$ : 56, 63, 70, 77, 84, 91, 98.

b) $⌊ 100/11 ⌋ - ⌊ 49/11 ⌋ = 9 - 4 = 5$ : 55, 66, 77, 88, 99.

c) Divisible by both means divisible by $lcm (7, 11) = 77$ : only 77.

6.1 #23 Core Multiples + inclusion–exclusion

How many positive integers between 100 and 999 inclusive

a) are divisible by 7?
b) are odd?
c) have the same three decimal digits?
d) are not divisible by 4?
e) are divisible by 3 or 4?
f) are not divisible by either 3 or 4?
g) are divisible by 3 but not by 4?
h) are divisible by 3 and 4?

Show solution

Answer

a) 128 b) 450 c) 9 d) 675 e) 450 f) 450 g) 225 h) 75

There are $999 - 100 + 1 = 900$ integers. Use multiples of $d$ in $[100, 999]$ $= ⌊ 999/ d ⌋ - ⌊ 99/ d ⌋$ .

Divisible by 3: $333 - 33 = 300$
Divisible by 4: $249 - 24 = 225$
Divisible by 12: $83 - 8 = 75$

a) $⌊ 999/7 ⌋ - ⌊ 99/7 ⌋ = 142 - 14 = 128$ .

b) Half of 900: $450$ . (Or: first digit 9 ways, middle 10, last 5 odd: $9 \cdot 10 \cdot 5 = 450$ .)

c) 111, 222, …, 999: $9$ .

d) $900 - 225 = 675$ .

e) Inclusion–exclusion: $300 + 225 - 75 = 450$ .

f) Complement of (e): $900 - 450 = 450$ .

g) Divisible by 3 minus divisible by both: $300 - 75 = 225$ .

h) Divisible by both 3 and 4 means divisible by 12: $75$ .

6.1 #25 Core Product rule

How many strings of three decimal digits

a) do not contain the same digit three times?
b) begin with an odd digit?
c) have exactly two digits that are 4s?

Show solution

Answer

a) 990 b) 500 c) 27

Strings allow leading zeros, so there are $1 0^{3} = 1000$ total.

a) Subtract the 10 strings $000, 111, \dots, 999$ : $1000 - 10 = 990$ .

b) First digit odd (5 ways), others free: $5 \cdot 10 \cdot 10 = 500$ .

c) Choose which position is not a 4 (3 ways), and that digit is any of the 9 non-4 digits: $3 \cdot 9 = 27$ .

6.1 #27 Core Product rule

A committee is formed consisting of one representative from each of the 50 states in the United States, where the representative from a state is either the governor or one of the two senators from that state. How many ways are there to form this committee?

Show solution

Answer

3^{50}

Each state independently picks 1 of 3 people (governor or one of two senators). Product rule over 50 states: $3^{50}$ .

6.1 #29 Core Sum + product

How many license plates can be made using either two uppercase English letters followed by four digits or two digits followed by four uppercase English letters?

Show solution

Answer

2 6^{2} 1 0^{4} + 1 0^{2} 2 6^{4} = 52, 457, 600

Two disjoint formats (a plate can't be both), so add:
$2 6^{2} \cdot 1 0^{4} + 1 0^{2} \cdot 2 6^{4} = 6, 760, 000 + 45, 697, 600 = 52, 457, 600.$

6.1 #31 Core Sum + product

How many license plates can be made using either two or three uppercase English letters followed by either two or three digits?

Show solution

Answer

(2 6^{2} + 2 6^{3}) (1 0^{2} + 1 0^{3}) = 20, 077, 200

Choose the letter part (2 or 3 letters) then the digit part (2 or 3 digits). Each part is a sum; the two parts multiply:
$(2 6^{2} + 2 6^{3}) (1 0^{2} + 1 0^{3}) = 18, 252 \cdot 1, 100 = 20, 077, 200.$
(Or add the four cases LL-DD, LL-DDD, LLL-DD, LLL-DDD. Same result.)

6.1 #33 Core Product rule + complement

How many strings of eight English letters are there (5 vowels, 21 consonants)

a) that contain no vowels, if letters can be repeated?
b) that contain no vowels, if letters cannot be repeated?
c) that start with a vowel, if letters can be repeated?
d) that start with a vowel, if letters cannot be repeated?
e) that contain at least one vowel, if letters can be repeated?
f) that contain exactly one vowel, if letters can be repeated?
g) that start with X and contain at least one vowel, if letters can be repeated?
h) that start and end with X and contain at least one vowel, if letters can be repeated?

Show solution

Answer

a) $2 1^{8}$ b) $21 \cdot 20 \dots 14$ c) $5 \cdot 2 6^{7}$ d) $5 \cdot 25 \cdot 24 \dots 19$ e) $2 6^{8} - 2 1^{8}$ f) $8 \cdot 5 \cdot 2 1^{7}$ g) $2 6^{7} - 2 1^{7}$ h) $2 6^{6} - 2 1^{6}$

a) $2 1^{8} = 37, 822, 859, 361$

b) $P (21, 8) = 21 \cdot 20 \cdot 19 \cdot 18 \cdot 17 \cdot 16 \cdot 15 \cdot 14 = 8, 204, 716, 800$

c) $5 \cdot 2 6^{7} = 40, 159, 050, 880$

d) $5 \cdot P (25, 7) = 5 \cdot 25 \cdot 24 \cdot 23 \cdot 22 \cdot 21 \cdot 20 \cdot 19 = 12, 113, 640, 000$

e) Complement: $2 6^{8} - 2 1^{8} = 171, 004, 205, 215$

f) Choose the vowel's position (8), the vowel (5), and 7 consonants: $8 \cdot 5 \cdot 2 1^{7} = 72, 043, 541, 640$

g) X is fixed (and X is a consonant), so the vowel must be among the other 7: $2 6^{7} - 2 1^{7} = 6, 230, 721, 635$

h) Six free middle letters, at least one vowel: $2 6^{6} - 2 1^{6} = 223, 149, 655$

On an exam with no calculator, leaving answers in the forms above is fine.

6.1 #35 Core One-to-one functions

How many one-to-one functions are there from a set with five elements to sets with the following number of elements? a) 4 b) 5 c) 6 d) 7

Show solution

Answer

a) 0 b) 120 c) 720 d) 2520

One-to-one from an $n$ -set to an $m$ -set: $m (m - 1) \dots (m - n + 1)$ , or $0$ if $n > m$ .

a) $5 > 4$ , so no one-to-one function exists: $0$ (pigeonhole!).
b) $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$
c) $6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 = 720$
d) $7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 = 2520$

6.1 #37 Core Counting functions

How many functions are there from the set ${1, 2, \dots, n}$ , where $n$ is a positive integer, to the set ${0, 1}$

a) that are one-to-one?
b) that assign 0 to both 1 and $n$ ?
c) that assign 1 to exactly one of the positive integers less than $n$ ?

Show solution

Answer

a) 2 if $n \leq 2$ , 0 if $n \geq 3$ b) $2^{n - 2}$ for $n \geq 2$ (1 if $n = 1$ ) c) $2 (n - 1)$

a) One-to-one needs $n \leq 2$ . For $n = 1$ : $f (1) = 0$ or $1$ , so 2. For $n = 2$ : $2 \cdot 1 =$ 2. For $n \geq 3$ : 0.

b) $f (1) = f (n) = 0$ is forced; the other $n - 2$ inputs are free: $2^{n - 2}$ (for $n \geq 2$ ). If $n = 1$ there is just $1$ function.

c) Among $1, \dots, n - 1$ , choose which one gets 1: $n - 1$ ways (the rest get 0). Then $f (n)$ is free: 2 ways. Total $2 (n - 1)$ .

6.1 #41 Core Bit strings

A palindrome is a string whose reversal is identical to the string. How many bit strings of length $n$ are palindromes?

Show solution

Answer

2^{⌈ n /2 ⌉}

A palindrome is determined by its first half; the second half is forced to mirror it.

$n$ even: choose the first $n /2$ bits: $2^{n /2}$ .
$n$ odd: choose the first $(n + 1) /2$ bits (including the middle): $2^{(n + 1) /2}$ .

Both cases: $2^{⌈ n /2 ⌉}$ .

6.1 #45 Core Division rule

At a large university, 434 freshmen, 883 sophomores, and 43 juniors are enrolled in an introductory algorithms course. How many sections of this course need to be scheduled to accommodate all these students if each section contains 34 students?

Show solution

Answer

$434 + 883 + 43 = 1360$ students, and $1360/34 = 40$ sections.

6.1 #47 Core Circular arrangements

How many ways are there to seat six people around a circular table where two seatings are considered the same when everyone has the same two neighbors without regard to whether they are right or left neighbors?

Show solution

Answer

$6! = 720$ ordered seatings. Each circular seating is counted 6 times (rotations) and another 2 times (mirror image, since left/right doesn't matter). Division rule:
$\frac{6 !}{6 \cdot 2} = \frac{720}{12} = 60.$

6.1 #49 Core Arrangements

In how many ways can a photographer at a wedding arrange six people in a row, including the bride and groom, if

a) the bride must be next to the groom?
b) the bride is not next to the groom?
c) the bride is positioned somewhere to the left of the groom?

Show solution

Answer

a) 240 b) 480 c) 360

a) Glue bride and groom into one block: 5 units to arrange ( $5!$ ), and the block can be BG or GB ( $2$ ): $5! \cdot 2 = 240$ .

b) Complement: $6! - 240 = 720 - 240 = 480$ .

c) By symmetry, in exactly half of all arrangements the bride is left of the groom: $720/2 = 360$ .

6.1 #51 Core Inclusion–exclusion

How many bit strings of length 10 either begin with three 0s or end with two 0s?

Show solution

Answer

352

Begin with 000: $2^{7} = 128$
End with 00: $2^{8} = 256$
Both: $2^{5} = 32$ (5 fixed bits)

128 + 256 - 32 = 352.

6.1 #53 Challenge Complement + recursion

How many bit strings of length eight contain either three consecutive 0s or four consecutive 1s?

Show solution

Answer

147

Count the complement: strings with no $000$ and no $1111$ . Such a string is made of alternating runs, where 0-runs have length 1–2 and 1-runs have length 1–3.

Let $a_{n}$ = number of valid strings of length $n$ ending in 0, and $b_{n}$ = number ending in 1. The last run of 0s has length 1 or 2 and is preceded by a valid string ending in 1 (or nothing). Similarly for 1s:
$a_{n} = b_{n - 1} + b_{n - 2}, b_{n} = a_{n - 1} + a_{n - 2} + a_{n - 3},$
with $a_{0} = b_{0} = 1$ (the empty string can precede the first run) and negative indices $= 0$ .

$n$	1	2	3	4	5	6	7	8
$a_{n}$	1	2	3	6	10	17	30	52
$b_{n}$	1	2	4	6	11	19	33	57

Valid strings of length 8: $52 + 57 = 109$ . So the answer is $2^{8} - 109 = 256 - 109 = 147$ .

(Check $n = 3$ : $3 + 4 = 7 = 8 - 1$ , since only $000$ is excluded. ✓)

6.1 #55 Core Inclusion–exclusion

How many positive integers not exceeding 100 are divisible either by 4 or by 6?

Show solution

Answer

$⌊ 100/4 ⌋ + ⌊ 100/6 ⌋ - ⌊ 100/12 ⌋ = 25 + 16 - 8 = 33$ .

(Both 4 and 6 means divisible by $lcm (4, 6) = 12$ , not 24.)

6.1 #57 Core Sum rule + complement

A password must have at least 8 but no more than 12 characters, where each character is a lowercase letter, an uppercase letter, a digit, or one of the six special characters ∗, >, <, !, +, =.

a) How many different passwords are available?
b) How many of these passwords contain at least one occurrence of at least one of the six special characters?
c) How long does it take a hacker to try every possible password, at one nanosecond per password?

Show solution

Answer

a) $\sum_{i = 8}^{12} 6 8^{i} \approx 9.9 \times 1 0^{21}$ b) $\sum_{i = 8}^{12} (6 8^{i} - 6 2^{i}) \approx 6.6 \times 1 0^{21}$ c) about 314,000 years

Character set: $26 + 26 + 10 + 6 = 68$ .

a) Sum over lengths: $i = 8 \sum 12 6 8^{i} = 9, 920, 671, 339, 261, 325, 541, 376 \approx 9.9 \times 1 0^{21}$ .

b) For each length, all minus those with no special character ( $62$ choices): $i = 8 \sum 12 (6 8^{i} - 6 2^{i}) \approx 6.6 \times 1 0^{21}$ .

c) $9.9 \times 1 0^{21}$ ns $= 9.9 \times 1 0^{12}$ s. A year is about $3.16 \times 1 0^{7}$ s, so this is about $3.1 \times 1 0^{5}$ , roughly 314,000 years.

6.1 #59 Extra Sum rule (geometric series)

The name of a variable in JAVA is a string of between 1 and 65,535 characters, inclusive, where each character can be an uppercase or a lowercase letter, a dollar sign, an underscore, or a digit, except that the first character must not be a digit. Determine the number of different variable names in JAVA.

Show solution

Answer

\frac{54 ( 6 4 ^{65535} - 1 )}{63}

Characters: $52 + 1 + 1 + 10 = 64$ ; the first character has $64 - 10 = 54$ options.

Names of length $i$ : $54 \cdot 6 4^{i - 1}$ . Sum over $i = 1, \dots, 65535$ :
$i = 1 \sum 65535 54 \cdot 6 4^{i - 1} = 54 j = 0 \sum 65534 6 4^{j} = 54 \cdot \frac{6 4 ^{65535} - 1}{64 - 1} .$

(The book's answer key prints the exponent as 65,536, which would include length 65,536. The question allows at most 65,535.)

6.1 #63 Core Sum rule

A wired equivalent privacy (WEP) key for a WiFi network is a string of either 10, 26, or 58 hexadecimal digits. How many different WEP keys are there?

Show solution

Answer

1 6^{10} + 1 6^{26} + 1 6^{58}

16 hex digits; three disjoint lengths, so add: $1 6^{10} + 1 6^{26} + 1 6^{58}$ .

6.1 #65 Core Inclusion–exclusion

Use the principle of inclusion–exclusion to find the number of positive integers less than 1,000,000 that are not divisible by either 4 or by 6.

Show solution

Answer

666,667

Integers $1, \dots, 999, 999$ .

Divisible by 4: $⌊ 999999/4 ⌋ = 249, 999$
Divisible by 6: $⌊ 999999/6 ⌋ = 166, 666$
Divisible by 12: $⌊ 999999/12 ⌋ = 83, 333$

Divisible by 4 or 6: $249, 999 + 166, 666 - 83, 333 = 333, 332$ .
Neither: $999, 999 - 333, 332 = 666, 667$ .

6.1 #67 Core Complement

How many ways are there to arrange the letters a, b, c, and d such that a is not followed immediately by b?

Show solution

Answer

Total $4! = 24$ . Arrangements with "ab" adjacent: glue ab into a block, giving 3 units and $3! = 6$ . Answer: $24 - 6 = 18$ .

6.1 #69 Core Tree diagram

Use a tree diagram to determine the number of subsets of ${3, 7, 9, 11, 24}$ with the property that the sum of the elements in the subset is less than 28.

Show solution

Answer

Branch on including or excluding each element in order, and prune once the sum reaches 28.

Size 0: $\emptyset$ (1)
Size 1: ${3}, {7}, {9}, {11}, {24}$ (5)
Size 2: ${3, 7}, {3, 9}, {3, 11}, {3, 24}, {7, 9}, {7, 11}, {9, 11}$ (7). ${7, 24}$ = 31 is too big, and so is anything else with 24.
Size 3: ${3, 7, 9} = 19$ , ${3, 7, 11} = 21$ , ${3, 9, 11} = 23$ , ${7, 9, 11} = 27$ (4)
Size 4: ${3, 7, 9, 11} = 30$ , too big (0)

Total: $1 + 5 + 7 + 4 = 17$ .

6.1 #71 Core Tree diagram / sum rule

A running shoe comes in women's sizes 6, 7, 8, 9 (colors: white, red, black) and men's sizes 8, 9, 10, 11, 12 (colors: white, black).

a) Use a tree diagram to determine how many different shoes a store must stock to have one pair of each size and color for both men and women.
b) Answer the question in part (a) using counting rules.

Show solution

Answer

a) Tree: gender → size → color. Women: 4 size branches, each with 3 color leaves (12). Men: 5 size branches, each with 2 color leaves (10). Total leaves: 22.

b) Sum rule over gender, product rule within: $4 \cdot 3 + 5 \cdot 2 = 12 + 10 = 22$ .

6.1 #73 Core Clever counting

Determine the minimum and the maximum number of matches that can be played in a double-elimination tournament with $n$ players, where after each game between two players, the winner goes on and the loser goes on if and only if this is not a second loss.

Show solution

Answer

Minimum $2 n - 2$ , maximum $2 n - 1$ .

Count losses instead of matches: every match produces exactly one loss.

Every player except the champion is eliminated, i.e. gets exactly 2 losses: $2 (n - 1)$ losses.
The champion has either 0 or 1 losses.

So the number of matches is $2 n - 2$ (champion undefeated) or $2 n - 1$ (champion lost once).

Custom (from lecture) Core Product rule Not from HW

Let $∣ A ∣ = m$ and $∣ B ∣ = n$ .

a) How many relations are there from $A$ to $B$ ? (A relation is any subset of $A \times B$ .)
b) How many functions $f : A \to B$ are there?
c) If $A = {1, 2, 3}$ and $B = {x, y}$ , compute both numbers.

Show solution

Answer

a) $2^{mn}$ b) $n^{m}$ c) 64 relations, 8 functions

a) $∣ A \times B ∣ = mn$ . A relation is a subset of $A \times B$ , and a set of size $mn$ has $2^{mn}$ subsets: each ordered pair is either in or out.

b) Each of the $m$ elements of $A$ chooses an image among $n$ elements: $n^{m}$ .

c) $2^{3 \cdot 2} = 64$ relations and $2^{3} = 8$ functions. Every function is a relation, but most relations aren't functions.

Custom (6.1 #22h style) Core Cases Not from HW

How many positive integers less than 1000 have distinct digits and are even?

Show solution

Answer

373

Split by number of digits (sum rule). Within each, split on whether the last digit is 0, since that changes the restriction on the first digit.

1 digit: 2, 4, 6, 8: 4.

2 digits (first digit 1–9, last digit even, digits distinct):

last = 0: first has 9 choices: 9
last ∈ {2,4,6,8} (4 ways): first is 1–9 but not the last digit: 8 ways: $4 \cdot 8 = 32$

Total 41.

3 digits:

last = 0: first 9 ways, middle 8 ways (not first, not 0): $72$
last ∈ {2,4,6,8} (4 ways): first 8 ways (nonzero, ≠ last), middle 8 ways (≠ first, ≠ last; 0 allowed): $4 \cdot 8 \cdot 8 = 256$

Total 328.

Answer: $4 + 41 + 328 = 373$ .

Why split on the last digit?

If you choose the last digit first, how many options the first digit has depends on whether the last digit was 0. When a step's count depends on an earlier choice, split into cases.

Next: 6.2 The Pigeonhole Principle