Counting Strings: Consider the set of all strings of a’s,

Problem 1E a. How many bit strings consist of from one through four digits? (Strings of different lengths are considered distinct. Thus 10 and 0010 are distinct strings.) b. How many bit strings consist of from five through eight digits?

Problem 2E a. How many strings of hexadecimal digits consist of from one through three digits? (Recall that hexadecimal numbers are constructed using the 16 digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.) b. How many strings of hexadecimal digits consist of from two through five digits?

Problem 5E a. How many five-digit integers (integers from 10,000 through 99,999) are divisible by 5? ________________ b. What is the probability that a five-digit integer chosen at random is divisible by 5?

Problem 49E A circular disk is cut into n distinct sectors, each shaped like a piece of pie and all meeting at the center point of the disk. Each sector is to be painted red, green, yellow, or blue in such a way that no two adjacent sectors are painted the same color. Let Sn be the number of ways to paint the disk. H a. Find a recurrence relation for Sk in terms of Sk?1 and Sk?2 for each integer k ? 4. b. Find an explicit formula for Sn for n ? 2.

Problem 3E a. How many integers from 1 through 999 do not have any repeated digits? b. How many integers from 1 through 999 have at least one repeated digit? c. What is the probability that an integer chosen at random from 1 through 999 has at least one repeated digit?

Problem 6E In a certain state, license plates consist of from zero to three letters followed by from zero to four digits, with the provision, however, that a blank plate is not allowed. a. How many different license plates can the state produce? ________________ b. Suppose 85 letter combinations are not allowed because of their potential for giving offense. How many different license plates can the state produce?

Problem 4E How many arrangements in a row of no more than three letters can be formed using the letters of the word NETWORK (with no repetitions allowed)?

Problem 7E In another state, all license plates consist of from four to six symbols chosen from the 26 letters of the alphabet together with the ten digits 0–9. a. How many license plates are possible if repetition of symbols is allowed? ________________ b. How many license plates do not contain any repeated symbol? ________________ c. How many license plates have at least one repeated symbol? ________________ d. What is the probability that a license plate chosen at random has a repeated symbol?

Problem 9E a. Consider the following algorithm segment: How many times will the inner loop be iterated when the algorithm is implemented and run? b. Let n be a positive integer, and consider the following algorithm segment: How many times will the inner loop be iterated when the algorithm is implemented and run?

Problem 11E a. How many ways can the letters of the word QUICK be arranged in a row? b. How many ways can the letters of the word QUICK be arranged in a row if the Q and the U must remain next to each other in the order QU? c. How many ways can the letters of the word QUICK be arranged in a row if the letters QU must remain together but may be in either the order QU or the order UQ?

Problem 10E A calculator has an eight-digit display and a decimal point that is located at the extreme right of the number displayed, at the extreme left, or between any pair of digits. The calculator can also display a minus sign at the extreme left of the number. How many distinct numbers can the calculator display? (Note that certain numbers are equal, such as 1.9, 1.90, and 01.900, and should, therefore, not be counted twice.)

Problem 8E At a certain company, passwords must be from 3–5 symbols long and composed of the 26 letters of the alphabet, the ten digits 0–9, and the 14 symbols !,@,#,$,%,^,&, *,(,),–,+,{, and }. a. How many passwords are possible if repetition of symbols is allowed? ________________ b. How many passwords contain no repeated symbols? ________________ c. How many passwords have at least one repeated symbol? ________________ d. What is the probability that a password chosen at random has at least one repeated symbol?

Problem 14E An early compiler recognized variable names according to the following rules: Numeric variable names had to begin with a letter, and then the letter could be followed by another letter or a digit or by nothing at all. String variable names had to begin with the symbol $ followed by a letter, which could then be followed by another letter or a digit or by nothing at all. How many distinct variable names were recognized by this compiler?

Problem 13E A group of eight people are attending the movies together. a. Two of the eight insist on sitting side-by-side. In how many ways can the eight be seated together in a row? ________________ b. Two of the people do not like each other and do not want to sit side-by-side. Now how many ways can the eight be seated together in a row?

Problem 15E Identifiers in a certain database language must begin with a letter, and then the letter may be followed by other characters, which can be letters, digits, or underscores (_). However, 82 keywords (all consisting of 15 or fewer characters) are reserved and cannot be used as identifiers. How many identifiers with 30 or fewer characters are possible? (Write the answer using summation notation and evaluate it using a formula) Summation Notation If m and n are integers and m ? n, the symbol , read the summation from k equals mto n of a-sub-k, is the sum of all the terms am, am+1, am+2, … , an. We say that am + am+1 + am+2 + … + an is the expanded form of the sum, and we write We call k the index of the summation, m the lower limit of the summation, and n the upper limit of the summation.

Problem 16E a. If any seven digits could be used to form a telephone number, how many seven-digit telephone numbers would not have any repeated digits? b. How many seven-digit telephone numbers would have at least one repeated digit? c. What is the probability that a randomly chosen seven-digit telephone number would have at least one repeated digit?

Problem 17E a. How many strings of four hexadecimal digits do not have any repeated digits? b. How many strings of four hexadecimal digits have at least one repeated digit? c. What is the probability that a randomly chosen string of four hexadecimal digits has at least one repeated digit?

Problem 19E A combination lock requires three selections of numbers, each from 1 through 39. Suppose the lock is constructed in such a way that no number can be used twice in a row but the same number may occur both first and third. For example, 20 13 20 would be acceptable, but 20 20 13 would not. How many different combinations are possible?

Problem 20E a. How many integers from 1 through 100,000 contain the digit 6 exactly once? b. How many integers from 1 through 100,000 contain the digit 6 at least once? c. If an integer is chosen at random from 1 through 100,000, what is the probability that it contains two or more occurrences of the digit 6?

Problem 18E Just as the difference rule gives rise to a formula for the probability of the complement of an event, so the addition and inclusion/exclusion rules give rise to formulas for the probability of the union of mutually disjoint events and for a general union of (not necessarily mutually exclusive) events. a. Prove that for mutually disjoint events A and B, P(A ? B) = P(A) + P(B). ________________ b. Prove that for any events A and B. P(A ? B) = P(A) + P(B) – P(A ? B).

Problem 21E Six new employees, two of whom are married to each other, are to be assigned six desks that are lined up in a row. If the assignment of employees to desks is made randomly, what is the probability that the married couple will have nonadjacent desks? (Hint: First find the probability that the couple will have adjacent desks, and then subtract this number from 1.)

Problem 24E a. How many integers from 1 through 1,000 are multiples of 2 or multiples of 9? b. Suppose an integer from 1 through 1,000 is chosen at random. Use the result of part (a) to find the probability that the integer is a multiple of 2 or a multiple of 9. c. How many integers from 1 through 1,000 are neither multiples of 2 nor multiples of 9?

Problem 22E Consider strings of length n over the set {a, b, c, d}. a. How many such strings contain at least one pair of adjacent characters that are the same? ________________ b. If a string of length ten over {a, b, c, d} is chosen at random, what is the probability that it contains at least one pair of adjacent characters that are the same?

Problem 23E a. How many integers from 1 through 1,000 are multiples of 4 or multiples of 7? b. Suppose an integer from 1 through 1,000 is chosen at random. Use the result of part (a) to find the probability that the integer is a multiple of 4 or a multiple of 7. c. How many integers from 1 through 1,000 are neither multiples of 4 nor multiples of 7?

Problem 25E Counting Strings: a. Make a list of all bit strings of lengths zero, one, two, three, and four that do not contain the bit pattern 111. ________________ b. For each integer n ? 0, let dn = the number of bit strings of length n that do not contain the bit pattern 111. Find d0, d1, d2, d3, and d4. ________________ c. Find a recurrence relation for d0, d1, d2, … ________________ d. Use the results of parts (b) and (c) to find the number of bit strings of length five that do not contain the pattern 111.

Problem 27E For each integer n ? 0, let ak be the number of bit strings of length n that do not contain the pattern 101. a. Show that ak = ak-1 + ak-3 + ak-4 + + a0 + 2, for all integers k ? 3. ________________ b. Use the result of part (a) to show that if k ? 3, then ak = 2ak–1 – ak–2 + ak–3.

Problem 26E Counting Strings: Consider the set of all strings of a’s, b’s, and c’s. a. Make a list of all of these strings of lengths zero, one, two, and three that do not contain the pattern aa. b. For each integer n ? 0, let sn = the number of strings of a’s, b’s, and c’s of length n that do not contain the pattern aa. Find . c. Find a recurrence relation for d. Use the results of parts (b) and (c) to find the number of strings of a’s, b’s, and c’s of length four that do not contain the pattern aa e. Use the technique described in Section 5.8 to find an explicit formula for

Problem 28E For each integer n ? 2 let an be the number of permutations of {1, 2, 3, ..., n} in which no number is more than one place removed from its “natural” position. Thus a1 = 1 since the one permutation of {1}, namely 1, does not move 1 from its natural position. Also a2 = 2 since neither of the two permutations of {1,2}, namely 12 and 21, moves either number more than one place from its natural position. a. Find a3. ________________ b. Find a recurrence relation for a1, a2, a3, …

Problem 30E A row in a classroom has n seats. Let sn be the number of ways nonempty sets of students can sit in the row so that no student is seated directly adjacent to any other student. (For instance, a row of three seats could contain a single student in any of the seats or a pair of students in the two outer seats. Thus s3 = 4.) Find a recurrence relation for s1, s2, s3,

Problem 31E Assume that birthdays are equally likely to occur in any one of the 12 months of the year. a. Given a group of four people, A, B, C, and D, what is the total number of ways in which birth months could be associated with A, B, C, and D? (For instance, A and B might have been born in May, C in September, and D in February. As another example, A might have been born in January, B in June, C in March, and D in October.) ________________ b. How many ways could birth months be associated with A, B, C, and D so that no two people would share the same birth month? ________________ c. How many ways could birth months be associated with A, B, C, and D so that at least two people would share the same birth month? ________________ d. What is the probability that at least two people out of A, B, C, and D share the same birth month? ________________ e. How large must n be so that in any group of n people, the probability that two or more share the same birth month is at least 50%?

Problem 29E Refer to Example 9.3.5. a. Write the following IP address in dotted decimal form: 11001010 00111000 01101011 11101110 b. How many Class A networks can there be? c. What is the dotted decimal form of the IP address for a computer in a Class A network? d. How many host IDs can there be for a Class A network? e. How many Class C networks can there be? f. What is the dotted decimal form of the IP address for a computer in a Class C network? g. How many host IDs can there be for a Class C network? h. How can you tell, by looking at the first of the four numbers in the dotted decimal form of an IP address, what kind of network the address is from? Explain. i. An IP address is 140.192.32.136. What class of network does it come from? j. An IP address is 202.56.107.238. What class of network does it come from?

Problem 32E Assuming that all years have 365 days and all birthdays occur with equal probability, how large must n be so that in any randomly chosen group of n people, the probability that two or more have the same birthday is at least 1/2? (This is called the birthday problem. Many people find the answer surprising.)

Problem 33E A college conducted a survey to explore the academic interests and achievements of its students. It asked students to place checks beside the numbers of all the statements that were true of them. Statement #1 was “I was on the honor roll last term,” statement #2 was “I belong to an academic club, such as the math club or the Spanish club,” and statement #3 was “I am majoring in at least two subjects.” Out of a sample of 100 students, 28 checked #1, 26 checked #2, and 14 checked #3, 8 checked both #1 and #2, 4 checked both #1 and #3, 3 checked both #2 and #3, and 2 checked all three statements. a. How many students checked at least one of the statements? ________________ b. How many students checked none of the statements? ________________ c. Let H be the set of students who checked #1, C the set of students who checked #2, and D the set of students who checked #3. Fill in the numbers for all eight regions of the diagram below. ________________ d. How many students checked #1 and #2 but not #3? ________________ e. How many students checked #2 and #3 but not #1? ________________ f. How many students checked #2 but neither of the other two?

Problem 37E For each of exercises below, the number of elements in a certain set can be found by computing the number in some larger universe that are not in the set and subtracting this from the total. In each case, as indicated by exercise, De Morgan’s laws and the inclusion/exclusion rule can be used to compute the number that are not in the set. Exercise Fill in the reasons for each step below. If A and B are sets in a finite universe U, then Exercise How many positive integers less than 1,000 have no common factors with 1,000?

Problem 36E Fill in the reasons for each step below. If A and B are sets in a finite universe U, then

Problem 39E For each of exercises below, the number of elements in a certain set can be found by computing the number in some larger universe that are not in the set and subtracting this from the total. In each case, as indicated by exercise, De Morgan’s laws and the inclusion/exclusion rule can be used to compute the number that are not in the set. Exercise Fill in the reasons for each step below. If A and B are sets in a finite universe U, then Exercise For each of exercises below, the number of elements in a certain set can be found by computing the number in some larger universe that are not in the set and subtracting this from the total. In each case, as indicated by exercise, De Morgan’s laws and the inclusion/exclusion rule can be used to compute the number that are not in the set. How many integers from 1 through 999,999 contain each of the digits 1, 2, and 3 at least once? (Hint: For each i = 1, 2, and 3, let Ai be the set of all integers from 1 through 999,999 that do not contain the digit i.)

Problem 35E An interesting use of the inclusion/exclusion rule is to check survey numbers for consistency. For example, suppose a public opinion polltaker reports that out of a national sample of 1,200 adults, 675 are married, 682 are from 20 to 30 years old, 684 are female, 195 are married and are from 20 to 30 years old, 467 are married females, 318 are females from 20 to 30 years old, and 165 are married females from 20 to 30 years old. Are the polltaker’s figures consistent? Could they have occurred as a result of an actual sample survey?

Problem 34E A study was done to determine the efficacy of three different drugs—A, B, and C—in relieving headache pain. Over the period covered by the study, 50 subjects were given the chance to use all three drugs. The following results were obtained: 21 reported relief from drug A. 21 reported relief from drug B. 31 reported relief from drug C. 9 reported relief from both drugs A and B. 14 reported relief from both drugs A and C. 15 reported relief from both drugs B and C. 41 reported relief from at least one of the drugs. Note that some of the 21 subjects who reported relief from drug A may also have reported relief from drugs B or C .A similar occurrence may be true for the other data. a. How many people got relief from none of the drugs? ________________ b. How many people got relief from all three drugs? ________________ c. Let A be the set of all subjects who got relief from drug A, B the set of all subjects who got relief from drug B, and C the set of all subjects who got relief from drug C. Fill in the numbers for all eight regions of the diagram below. d. How many subjects got relief from A only?

Problem 38E For each of exercises below, the number of elements in a certain set can be found by computing the number in some larger universe that are not in the set and subtracting this from the total. In each case, as indicated by exercise, De Morgan’s laws and the inclusion/exclusion rule can be used to compute the number that are not in the set. Exercise Fill in the reasons for each step below. If A and B are sets in a finite universe U, then Exercise For each of exercises below, the number of elements in a certain set can be found by computing the number in some larger universe that are not in the set and subtracting this from the total. In each case, as indicated by exercise, De Morgan’s laws and the inclusion/exclusion rule can be used to compute the number that are not in the set. How many permutations of abcde are there in which the first character is a, b,or c and the last character is c, d, or e?

Problem 40E For use the definition of the Euler phi function Euler phi function For each integer n ? 1, ?(n) is the number of positive integers less than or equal to n that have no common factors with n except ±1. For example, ?(10) = 4 because there are four positive integers less than or equal to 10 that have no common factors with 10 except ±1; namely, 1, 3, 7, and 9. Use the inclusion/exclusion principle to prove the following: If n = pq, where p and q are distinct prime numbers, then ?(n) = (p – 1)(q – 1).

Problem 41E For use the definition of the Euler phi function Euler phi function For each integer n ? 1, ?(n) is the number of positive integers less than or equal to n that have no common factors with n except ±1. For example, ?(10) = 4 because there are four positive integers less than or equal to 10 that have no common factors with 10 except ±1; namely, 1, 3, 7, and 9. Use the inclusion/exclusion principle to prove the following: If n = pqr, where p, q, and r are distinct prime numbers, then ? (n) = (p – 1)(q – 1)(r – 1).

Problem 42E A gambler decides to play successive games of blackjack until he loses three times in a row. (Thus the gambler could play five games by losing the first, winning the second, and losing the final three or by winning the first two and losing the final three. These possibilities can be symbolized as LWLLL and WWLLL.) Let gn be the number of ways the gambler can play n games. a. Find g3, g4, and g5. ________________ b. Find g6. ________________ c. Find a recurrence relation for g3, g4, g5, …

Problem 43E A derangement of the set {1, 2,…, n} is a permutation that moves every element of the set away from its “natural” position. Thus 21 is a derangement of {1, 2}, and 231 and 312 are derangements of {1, 2, 3}. For each positive integer n, let dn be the number of derangements of the set {1, 2,…, n}. a. Find d1, d2, and d3. ________________ b. Find d4. ________________ c. Find a recurrence relation for d1, d2, d3,…

Problem 45E Use mathematical induction to prove Theorem. Theorem The Addition Rule Suppose a finite set A equals the union of k distinct mutually disjoint subsets A1, A2, …, Ak.…Then N(A) = N(A1) + N(A2)+…+ N(Ak).

Problem 47E Prove the inclusion/exclusion rule for three sets.

Problem 46E Prove the inclusion/exclusion rule for two sets A and B by showing that A ? B can be partitioned into A ? B, A – (A ? B), and B – (A ? B), and then using the addition and difference rules.

Problem 44E Note that a product x1 x2x3 may be parenthesized in two different ways: (x1 x2)x3 and x1(x2x3). Similarly, there are several different ways to parenthesize x1x2x3x4. Two such ways are (x1x2)(x3x4) and x1 ((x2x3)x4). Let Pn be the number of different ways to parenthesize the product x1x2 … x4. Show that if P1 = 1, then (It turns out that the sequence P1, P2, P3, … is the same as the sequence of Catalan numbers: Pn = Cn–1 for all integers n > 1. See Example) Example Showing That a Sequence Given by an Explicit Formula Satisfies a Certain Recurrence Relation The sequence of Catalan numbers, named after the Belgian mathematician Eugène Catalan (1814–1894), arises in a remarkable variety of different contexts in discrete mathematics. It can be defined as follows: For each integer n ? 1, a. Find C1,C2, and C3. ________________ b. Show that this sequence satisfies the recurrence relation for all integers k ? 2 Solution a. ________________ b. To obtain the kth and (k – 1)st terms of the sequence, just substitute k and k – 1 in place of n in the explicit formula for C1, C2, C3,… Then start with the right-hand side of the recurrence relation and transform it into the left-hand side: For each integer k ? 2,

Problem 48E Use mathematical induction to prove the general inclusion/exclusion rule: If A1, A2,…, An are finite sets, then (The notation ) means that quantities of the form N (Ai ? Aj) are to be added together for all integers i and j with 1 ? i n.)

Problem 12E a. How many ways can the letters of the word THEORY be arranged in a row? b. How many ways can the letters of the word THEORY be arranged in a row if T and H must remain next to each other as either TH or HT ?