Combinatorics and computing

EXERCISES

In a class of 35 students, there are 12 students who speak German, and 5 students who speak Japanese. If 2 of the students speak both of these languages, how many of the students speak neither language? With the aid of a Venn diagram, obtain a version of the Principle of inclusion and exclusion for the cardinality of the union of three sets. Suppose you are offered a choice of tea or coffee, with full milk, reduced milk or no milk, and either with or without sugar. Express all the possible drinks you could have as a Cartesian product of sets, and depict them on a tree diagram. How many different car number plates consisting of 3 letters followed by 3 digits are there altogether? The telephone numbers in a certain area consist of 8 digits. The first digit of telephone number is not permitted to be 0 or 1 (a) How many such telephone numbers are there altogether? (b) How many of the telephone numbers do not contain any zeros? (c) How many of the telephone numbers contain at least one zero? Australian postcodes consist of 4 digits, but only the digits 0, 2, 3, 4, 5, 6 and 7 are used for the first digit, and if the first digit is 0 then the second digit is always 8. How many different postcodes are possible with these restrictions? The DX code on photographic film canisters (which is used by some cameras to set the film speed and number of exposures automatically) consists of 12 regions, numbered from 1 to 12. Each region is either conducting or non-conducting. (a) If all possible combinations of ‘conducting’ and ‘non-conducting’ can occur, how many different codes are possible? (b) In fact, regions 1 and 7 are always conducting. In addition, at least one of areas 5 and 6 is always conducting. How many codes are possible with these restrictions? On a certain computer system, a valid password consists of exactly 8 characters. The first character must be a letter, and the remaining characters must be letters or digits. (Assume that no distinction is made between upper-case and lower-case letters.) In order to be valid, a password must contain at least one digit. How many valid passwords are there? A combination lock for a bicycle has four dials, each with the numbers from 1 to 6. If you have forgotten the combination that opens the lock, how long will it take you to try all the combinations, at a rate of one every 5 seconds? A program to generate all the permutations of a set is run on a computer that writes the output to a file at a rate of 1000 permutations per second. How long will it take the computer to generate all the permutations of a set with: (a) 10 elements? (b) 15 elements? In how many ways can a club with 45 members select a president, a vice president, a secretary and a treasurer, if no member is permitted to hold more than one office? Evaluate: ^10P6 c) ^12P8 ^13C5 d) ^15C11 The test marks for a class of 12 students are as follows: 15, 13, 18, 15, 7, 12, 10, 13, 9, 5, 15, 17 These marks may be entered into a statistical analysis program in any order. How many different orders are there? The Information Systems department at a university has 16 members of staff. The department has been asked to choose five of its members to serve on a faculty committee. (a) In how many ways can the members who are to serve on the committee be chosen? (b) If seven of the 16 members of the department are female, how many five-member committees can be formed in which exactly two of the members are female? A test bank of questions is to be set up so that tests consisting of ten questions can be generated by selecting questions from the test bank. What is the minimum number of questions needed in the test bank in order to ensure that at least 1000 different tests can be generated? (Assume that the order in which the questions appear on a test is not important.) The position of a robotic arm above a printed circuit board is described by a pair of coordinates, giving the distances of the point from the left-hand edge and the lower edge of the board, in that order. The arm is initially at the bottom left-hand corner of the board, which has coordinates (0, 0). Two other points on the board are A, with coordinates (6, 3), and B, with coordinates (3, 5). The arm can only move in unit steps parallel to the sides of the board. In how many different ways can the arm move: (a) from the initial position to A; (b) from the initial position to A, and then to B; (c) from the initial position to A, then to B, and back to the initial position; (d) from the initial position to A and B in either order, returning to the initial position? (Assume that the arm always takes one of the shortest paths from one point to another, with no doubling back.) Prove the identity Prove that: Write down the rows of Pascal’s triangle corresponding to n = 6 and n = 7. By interpreting ^nCr as the number of r-element subsets of an n- element set, find the value of Without referring to ^nCr, explain why a set with n elements has: (a) n 1-element subsets; (b) n (n – 1)-element subsets; (c) the same number of (n – r)-element subsets as r-element subsets.