MATH2030 Combinatorics: Textbook Solution Manual Chap 2.1-2.5

Week 1

List sections and question numbers that are solved in this solution manual.

1. Chap 2.1

2. Chap 2.2

3. Chap 2.3

4. Chap 2.5

Chap 2.1: by ???

1.  (Question 1, Logan Furedi)

We have 20,000 residents, and each has three letters in their initials. Since there are 26 letters in the English alphabet, we have a total of 26 × 26 × 26 = 263  possible initials for any given resident.  Notice that 263  = 17,576 < 20,000. This means it is impossible for all 20,000 residents to have unique initials, and so it is in fact true that there must be at least two residents with the same initials in Carlisle, Pennsylvania.

2.  (Mia Battad) Start by finding the number of unique codewords.

The first three characters have 26 options (for each letter of the alphabet), and the last three characters have 10 options (for each digit 0-9):

26 × 26 × 26 × 10 × 10 × 10 = 263  × 103  = 17576000

This is greater than the number of books (1700000), so it is possible to assign unique codewords to each book. 3.  (Question 3, Logan Furedi)

(a) We want to calculate the total number of trinary codes of length at most three consisting only of the symbols 0, 1, and −1. Note that the strings 0, 00, and 000 are all distinct strings. Therefore, we will have to approach this problem by cases of string length.

Case 1: For single digit strings, we have only 3 possible codes: 0, 1, and −1.

Case 2: For two digit strings, we have 32  = 9 possible codes, as each digit may be one of three options. Case 3: Similarly, for strings of length three, we have 33  = 27 possible codes.

By the rule of sum, we may add up each of these results to yield our final total.  We have, 3 + 9 + 27 = 39 possible encodings of trinary strings of length at most three.

(b)  Similar to (a), we are asked to compute the total number of distinct trinary codes of length at most four. We proceed by cases.

Cases 1-3: In (a), we showed the number of strings of length one, two, and three were 3, 9, and 27 respectively. Case 4: For strings of length four, there are 34  = 81 possible codes.

By the rule of sum, we may add up each of these results to yield our final total. We have, 3+9+27+81 = 120 possible encodings for trinary strings of length at most four.

(c) We are asked to compute the number of distinct trinary codes of length exactly four such that the first digit is either a 0 or a 1.  Immediately, we see that the first digit may only be one of two options.  In contrast, the second, third, and fourth digits may each be one of: 0, 1, or −1.

Therefore, we have 2 × 33  = 54 possible four digit trinary strings where the first digit is either a 0 or a 1.

4.  (Mark Jimenez) If none of the the first three digits can be 0 or 1, then there are only 8 possible choices of numbers (2-8) for the first 3 digits.  The remaining 5 digits each have 10 choices of numbers (0-9).  Thus the total local phone numbers are:

83  × 105  = 51200000

To count the total phone numbers including the area code, recall that the restriction for the area code in example 2.3 in the book is that it could not begin with a 0 or 1, and it had to have 0 or 1 in the middle. The total possible

8 × 2 × 10

And the total phone numbers including the area code, by the product rule is:

8 × 2 × 10 × 83  × 105  = 81920000002

Chap 2.2: by ???

1.  (Huu Nguyen Phu Le) How many bit strings have length 3,4, or 5?

(a) UNDERSTAND QUESTION

i.  Bit strings include 0, 1

ii.  The question wants us to get the total sum of the number of strings with length 3, 4, or 5.

(b) SOLUTION

Since each 0 and 1 can be picked multiple times, and the order matters, each digit has 2 choices (0 or 1). We have 3 cases:

i.  Case of length 3 (3 digits):

23

ii.  Case of length 4 (4 digits):

24

iii.  Case of length 5 (5 digits):

25

Now the number of bit strings with length 3, 4, or 5 is:

23 + 24 + 25  = 4096

Chap 2.3: by ???

1.  (Jonas Weselak) List all permutations of (a) {1,2,3}, and (b) {1,2,3,4}.

(a) We start by listing all the ways we can arrange the 3 numbers with 1 in the first position:

{1,2,3}

{1,3,2}

We now create two more unique permutations by swapping the first and second, and first and third entries in the original list {1, 2, 3}, giving us {2, 1, 3} and {3, 2, 1} respectively. For each of these, we list all ways these numbers can be arranged without moving the first number as:

{2,1,3}    {3,2,1}

{2,3,1}    {3,1,2}

{1,2,3,4}    {2,1,3,4}    {3,2,1,4}    {4,2,3,1}

{1,2,4,3}    {2,1,4,3}    {3,2,4,1}    {4,2,1,3}

{1,3,2,4}    {2,3,1,4}    {3,1,2,4}    {4,3,2,1}

{1,3,4,2}    {2,3,4,1}    {3,1,4,2}    {4,3,1,2}

{1,4,2,3}    {2,4,1,3}    {3,4,1,2}    {4,1,3,2}

{1,4,3,2}    {2,4,3,1}    {3,4,2,1}    {4,1,2,3}

These are all the permutations of the numbers (1,2,3,4) and now add 5 to the beginning of each of these permuta- tions,thus giving us the result that we desired.

{5,1,2,3,4}    {5,2,1,3,4}    {5,3,2,1,4}    {5,4,2,3,1}

{5,1,2,4,3}    {5,2,1,4,3}    {5,3,2,4,1}    {5,4,2,1,3}

{5,1,3,2,4}    {5,2,3,1,4}    {5,3,1,2,4}    {5,4,3,2,1}

{5,1,3,4,2}    {5,2,3,4,1}    {5,3,1,4,2}    {5,4,3,1,2}

{5,1,4,2,3}    {5,2,4,1,3}    {5,3,4,1,2}    {5,4,1,3,2}

{5,1,4,3,2}    {5,2,4,3,1}    {5,3,4,2,1}    {5,4,1,2,3}

4.

5.

6.

7.

8.  (Nolan Coughlan) How many DNA chains of length 3 have no C’s at all or have no T’s in the first position? Solution

There are two ways of doing this question. We show both methods.

First Method: We first count the number of chains that have no C’s, then add the chains that have no T’s in the first position. This double-counts the chains that are both, so we subtract these off.

Chains with no C’s: We have 3 remaining options for each of the three letters, so 3 根 3 根 3 = 27 such chains.

Chains that don’t start with T: This means there are 3 options for the first letter and 4 for the second and third letters, so 3 根 4 根 4 = 48 such chains.

Chains with both:  This means there are only 2 options for the first letter, and 3 for the second and third, so 2 根 3 根 3 = 18 such chains.

So, there are 27 + 48 - 18 = 57 chains that either have no C’s or don’t start with a T.

Second Method: We count the total number of possible DNA chains of length 3 and take away the ones that both start with a T and have a C.

Total DNA chains: There are 4 options for each of the three letters, so 4 根 4 根 4 = 64 total chains.

Chains that start with T and have a C: The first letter would be a T, then we have 2 choices for where the C goes, and 4 choices for the other letter, giving 2 根 4 = 8 strings, but this double counts the string TCC, so there are actually only 7.

So, there are 64 - 7 = 57 chains that either have no C’s or don’t start with a T.

Chap 2.5: by ???

1.

2.

3.

4.

5.  (Noah  Curoe) If a campus telephone extension has four digits, how many different extensions are there with no repeated digits:

a. If the first digit cannot be 0?

Solution: We have four digits to fill with no repetition, and the first digit cannot be 0.

First digit 一 Any digit except 0  =今  9 options

Second digit 一 Any digit except the one digit chosen for digit 1  =今  9 options