Q1. As discussed in the first assignment, it can be helpful to study the probability oferrors and therefore it is useful to know the cardinalities of sets of words and validcodewords — this is where combinatorics comes in.(a) In Question 3 of Assignment 1, it was stated that the set of all bit strings oflength four has 16 elements and the set of all bit strings of length 12 has4096. Justify these cardinalities.2 marks(b) Suppose that a code is made up six digits from the range 0–9 (inclusive)and satisfies the rules:• The first three digits must be odd (and non-zero).• No number is repeated in the first five digits.• The sixth digit is the remainder of the sum of the first five digits dividedby 10.i. How many valid codewords are there?4 marksii. What is the probability that a random selected six digit number is a validcodeword?2 marks(c) One common mistake humans make when reading out numbers is transpo-sitions. Transposition is the special case of swapping letters of a word givenby swapping adjacent letters. (In Assignment 1 we mentioned that ISBN-10could detect such errors.)How many distinguishable rearrangements (not just transpositions) of theISBN-10 code0-205-08005-7are there?2 marksTotal: 10 marksPage 3 of 8

(a) The cardinalities of the sets of all bit strings of length four and twelve can be justified by the fact that each bit in a string can have two possible values: 0 or 1. Therefore, for a bit string of length four, there are 2^4 = 16 possible combinations. Similarly, for a bit string of length twelve, there are 2^12 = 4096 possible combinations.

(b) i. For the first three digits, there are 5 choices (1, 3, 5, 7, 9) for each digit and they must be different, so there are 543 = 60 choices. For the fourth and fifth digits, they can be any of the remaining 7 digits (0, 2, 4, 6, 8 and the two not used in the first three), so there are 76 = 42 choices. The sixth digit is determined by the sum of the first five digits, so there is only 1 choice. Therefore, there are 6042*1 = 2520 valid codewords.

ii. The total number of six-digit numbers is 10^6 = 1,000,000. Therefore, the probability that a randomly selected six-digit number is a valid codeword is 2520/1,000,000 = 0.00252.

(c) The ISBN-10 code 0-205-08005-7 has 10 digits and 3 hyphens. If we ignore the hyphens, there are 10! = 3,628,800 distinguishable rearrangements. If we consider the hyphens, we need to choose 3 positions out of 13 (10 digits + 3 hyphens) to place them, which gives us C(13,3) = 286 ways. Therefore, there are 3,628,800 * 286 = 1,038,036,800 distinguishable rearrangements.

(a) The cardinalities of the sets of all bit strings of length four and twelve can be justified by the rule of product in combinatorics. A bit string of length n can have 2^n different combinations because each bit can be either 0 or 1. Therefore, a bit string of length four has 2^4 = 16 combinations and a bit string of length twelve has 2^12 = 4096 combinations.

(b) i. The first three digits must be odd and non-zero, so there are 5 choices (1, 3, 5, 7, 9) for each of the first three digits. However, no number can be repeated in the first five digits. So, there are 5 choices for the first digit, 4 for the second, and 3 for the third. For the fourth and fifth digits, they can be any of the remaining 7 and 6 digits respectively. The sixth digit is determined by the sum of the first five digits, so there is only 1 choice. Therefore, the total number of valid codewords is 54376*1 = 2520.

ii. The total number of six-digit numbers is 10^6 = 1,000,000. Therefore, the probability that a randomly selected six-digit number is a valid codeword is 2520 / 1,000,000 = 0.00252.

(c) The ISBN-10 code 0-205-08005-7 has 10 digits and 3 hyphens. We treat each hyphen as a separate entity. Therefore, there are 13 entities to arrange. However, the digit 0 and the hyphen appear 3 times each. Therefore, the number of distinguishable rearrangements is 13! / (3!*3!) = 1,778,214,400.