Miscellaneous Problems
20.1 One commercially available ten-button lock may be opened by depressing — in any order — the correct five buttons. The sample shown below has {1,2,3,6,9} as its combination. Suppose that these locks are redesigned so that sets of as many as nine buttons or as few as one button could serve as combinations. How many additional combinations would this allow?
20.2 Calculate in how many ways each of the following choices can be made.
(i) 4 movies are to be downloaded from a list of 10 movies to be enjoyed during a holiday.
(ii) 200 essays have been shortlisted for a competition, and three are to be chosen so as to receive the 1st, 2nd and 3rd prizes.
(iii) Eight children are to be chosen from a group of 20 children; the chosen children are then to pair up and line up a pair behind the other, but order within each pair does not matter.
20.3 A society is planning a ballot for the office of president. There are 5 candidates for the office. In order to eliminate the order of the candidates on the ballot as a possible influence on the election, there is a rule that on the ballot slips, each candidate must appear in each position the same number of times as any other candidate. What is the smallest number of different ballot slips necessary?
20.4 In the waiting area of a specialist clinic, patients sit on chairs arranged 10 to a row with an aisle on either side. Ten patients are sitting in the second row. How many ways are there for all the patients in the second row to see the doctor if at least one patient has to pass over one or more other patients in order to reach an aisle?
20.5 In how many ways can 4 a’s, 4 b’s, 4 c’s and 4 d’s be arranged in a 4 × 4 array so that exactly one letter occurs in each row and in each column? (Such an arrangement is called a Latin square.)
20.6 A card is drawn from a full pack of 52 playing cards. If the card is a King, Queen or Jack, two dice are thrown and the total T is taken to be the sum of the scores on the dice. If any other card is drawn, only one die is thrown and T is taken to be the sum of the scores on the card (an Ace is considered as 1) and the die. Find the number of ways for each of the following:
(i) T ≤ 2;
(ii) T ≥ 13;
(iii) T is odd.
20.7 In each of the following 5-digit numbers
every digit appears more than once. Find the number of such 5-digit numbers.
20.8 The following list contains some permutations of 
9 in which each of the digits 2, 3, 4 appears in between 1 and 9:
Find the number of such permutations of 9.
20.9 The following list contains some permutations of 9 in which each of the digits 1, 2, 3 appears to the right of 9:
Find the number of such permutations of 9.
20.10 Find the number of ‘0’s at the end of 1 × 2 × 3 ×…× 2012.
20.11 Find the number of 15-digit ternary sequences (formed by 0, 1 and 2) in each of the following cases:
(i) there is no restriction;
(ii) there are exactly three ‘0’s;
(iii) there are exactly four ‘0’s and five ‘1’s;
(iv) there are at most two ‘0’s;
(v) there is at least one pair of consecutive digits that are the same;
(vi) there are exactly one ‘00’, three ‘11’, three ‘22’, three ‘02’, two ‘21’ and two ‘10’ (for instance, 002211102221102).
20.12 Find the number of (i) positive divisors, (ii) even positive divisors of 2160.
20.13 It can be checked that ‘12’ and ‘18’ are the only two positive integers that are divisible by 6 and have exactly 6 different positive divisors.
(i) Find all natural numbers which are divisible by 30 and have exactly 30 different divisors.
(ii) How many positive integers are there which are divisible by 105 and have exactly 105 different positive divisors?
20.14 Consider the following grid:
Find in the grid
(i) the number of shortest P-R routes;
(ii) the number of shortest P-Q routes.
20.15 In a shooting match, eight clay targets are arranged in two hanging columns of three each and one column of two, as pictured.
A marksman is to break all eight targets according to the
following rules:
(1) The marksman first chooses a column for which a target is to be broken.
(2) The marksman must break the lowest remaining unbroken target in the chosen column.
If these rules are followed, in how many different orders can
the eight targets be broken?
20.16 Six scientists are working on a secret project. They wish to lock up the documents in a cabinet such that the cabinet can be opened when and only when 3 or more of the scientists are present. What is the smallest number of locks needed? What is the smallest number of keys each scientist must carry?
20.17 A team for a boxing competition consists of a heavyweight, a middleweight and a lightweight. There are 5 teams in the competition.
(i) If each person fights with each person of a similar weight class, how many fights take place?
(ii) At the end of the competition, everyone shakes hands exactly once with every other person, except his teammates (they have to tend to each other’s wounds later). How many handshakes take place?
20.18 Find the number of paths in the array which spell out the word COUNTING.
20.19 Let A = {1,2,..., 500}. Find
(i) the number of 2-element subsets of A;
(ii) the number of 2-element subsets {a, b} of A such that a · b is a multiple of 3;
(iii) the number of 2-element subsets {a, b} of A such that a+b is a multiple of 3.
20.20 Two integers p and q, with p ≥ 2 and q ≥ 2, are said to be coprime if p and q have no common prime factor. Thus 8 and 9 are coprime while 4 and 6 are not.
(i) Find the number of ways to express 360 as a product of two coprime numbers (the order of these two numbers is unimportant).
(ii) In general, given an integer n ≥ 2, how do you find the number of ways to express n as a product of two coprime numbers where the order is immaterial?
20.21 The lattice points of the following m x n(n ≤ m) grid are named as shown:
For k ∈ {1, 2,..., n}, let p be the number of shortest (k,k – 1)–
(m, n) routes and q be the number of shortest (k – 1, k)–
(m, n) routes. Show that p(n + 1 – k) = q(m + 1 – k).
20.22 The face cards (Kings, Queens and Jacks) are removed from a pack of playing cards. Six cards are drawn one at a time from this pack of cards such that they are in increasing order of magnitude. How many ways are there to do this?
20.23 There are 12 coins on a table. I pick up a number (non-zero) of coins each time. Find the number of ways of picking up all the 12 coins in the following cases:
(i) I pick up all the 12 coins in an even number of picks.
(ii) I pick up an even number of coins each time.
20.24 Find the number of 4-tuples of integers
(i) (a, b, c, d) satisfying 1 ≤ a ≤ b ≤ c ≤ d ≤ 30;
(ii) (p, q, r, s) satisfying 1 ≤ p ≤ q ≤ r ≤ s ≤ 30.
20.25 Consider the following two 15-digit ternary sequences (formed by 0, 1 and 2):
Observe that each of the sequences contains exactly three ‘00’,three ‘11’, three ‘22’, two ‘01’, two ‘12’ and one ‘20’. Find the number of such ternary sequences.
20.26 There are n upright cups in a row. At each step, I turn over n-1 of them. Show that I can end up with all the cups upside down if and only if n is even. Find the number of ways this can be done in a minimum number of steps.
20.27 The following diagram shows 15 distinct points: w1, w2, w3, x1, . . . , x4, y1, . . . , y6, z1, z2 chosen from the sides of rectangle ABCD.
(i) How many line segments are there joining any two points each on different sides?
(ii) How many triangles can be formed from these points?
(iii)How many quadrilaterals can be formed from these points?
(iv) If no three line segments are concurrent in the interior of the rectangle, find the number of points of intersection of these line segments in the interior of rectangle ABCD.
20.28 A ternary sequence is a sequence formed by 0, 1 and 2. Let n be a positive integer. Find the number of n-digit ternary sequences
(i) which contain at least one ‘0’;
(ii) which contain one ‘0’ and one ‘1’;
(iii) which contain three ‘2’s.
20.29 Each of the following six configurations consists of 4 vertices w, x, y, z with some pairs of vertices joined by lines. We are now given five colours 1, 2, 3, 4, 5 to colour the 4 vertices such that
(1) each vertex is coloured by one colour and
(2) any two vertices which are joined by a line must be coloured by different colours.
How many different ways are there to colour each configuration?
20.30 If repetitions are not allowed, find the number of different 5-digit numbers which can be formed from 0,1, 2,..., 9 and are
(i) divisible by 25;
(ii) odd and divisible by 25;
(iii) even and divisible by 25;
(iv) greater than 75000;
(v) less than 75000;
(vi) in the interval [30000, 75000] and divisible by 5.
20.31 There are 12 boys and 8 girls, including a particular boy B and two particular girls G1 and G2, in a class. A class debating team of 4 speakers and a reserve is to be formed for the interclass games. Find the number of ways this can be done if the team is to contain
(i) exactly one girl;
(ii) exactly two girls;
(iii) at least one girl;
(iv) at most two girls;
(v) Gi;
(vi) no B;
(vii) B and G1;
(viii) neither B nor G1;
(ix) exactly one from G1 and G2;
(x) an odd number of girls.
20.32 A group of 6 people is to be chosen from 7 couples. Find the number of ways this can be done if the group is to contain
(i) three couples;
(ii) no couples;
(iii) exactly one couple;
(iv) exactly two couples;
(v) at least one couple.
20.33 Find the number of ways in which 6 people can be divided into
(i) 3 groups consisting of 3, 2, and 1 persons;
(ii) 3 groups with 2 persons in each group;
(iii) 4 groups consisting of 2, 2, 1 and 1 persons;
(iv) 3 groups with 2 persons in each group, and the groups are put in 3 distinct rooms.
20.34 Show that the number of r-combinations of Nn which contain no consecutive integers is given by 
, where 0 ≤ r ≤ n — r + 1.
20.35 Suppose the n integers in Nn are arranged consecutively round a table so that ‘1’ is also adjacent to ‘n’. For 0 ≤ r ≤ 
let T(r) denote the number of r-combinations of Nn in which no two integers are adjacent around the table. Show that
20.36 Three girls and five boys are to line up in a row. Find the number of ways if each boy is adjacent to at most one girl.
20.37 There are n + 2 vertices, denoted by u,v,x1,x2,... ,xn, in a graph (see Chapter 15 for the concept of a ‘graph’) as shown below:
You are allowed to draw exactly n + 1 edges to link the vertices in such a way that
(1) each edge joins u or v to some xi,
(2) no two edges join the same pair of vertices, and
(3) the following configuration can never occur
Thus, for instance, when n = 2, there are 4 different such graphs as shown below:
(i) Show all different such graphs for n = 3.
(ii) For all n ≥ 4, evaluate the number of different such graphs.
20.38 Find the coefficient of x9 in the expansion of (1+ x + x3 + x5)5.
20.39 Find the number of 4-element subsets {w, x, y, z} of 25 in each of the following cases:
(i) there is no restriction;
(ii) the product w · x · y · z is odd;
(iii) the product w · x · y · z is even;
(iv) the sum w + x + y + z is odd;
(v) the sum w ? x + y ? z is odd.
20.40 Find the number of positive divisors of 67500 in each of the following cases:
(i) there is no restriction;
(ii) the divisors are even;
(iii) the divisors are odd;
(iv) the divisors are multiples of 5;
(v) the divisors are multiples of 6.
20.41 Six distinct numbers a, b, c, d, e and f are chosen from the 8-element set {2,3,...,9} and are arranged in a row in the order a, b, c, d,e, f. Find the number of ways this can be done if
(i) there is no restriction;
(ii) the product a · d is even;
(iii) the product a · b · c is odd;
(iv) the product a · b · c is odd and the product d · e · f is a multiple of 10;
(v) a, b and c are divisible by d, e and f respectively.
20.42 Every day, an inter-city train arrives at a station early (E), on time (T) or late (L), or the trip is cancelled (C). Let Sn denote the number of possible sequences of arrival for the train in a series of n days. Given that the train is never cancelled on two successive days, find a recurrence relation for Sn. Prove also that S2n and S2n+1 are both divisible by 3n.
20.43 A special deck of 52 playing cards consists of cards without the usual numbers or pictures but just bearing the suit (i.e. there are 13 cards of each of the four suits, Heart, Diamond, Spade and Club, and the cards in each suit are indistinguishable from each other).
(i) Eight cards are selected from the deck. Find the number of different selections if there is at least one card of each suit.
(ii) Eight cards are arranged in a row. Find the number of distinct sequences if there must be at least one card of each suit.
(iii) Two cards of each suit are selected. Find the number of ways they can be arranged in a row if no two cards of the same suit are together.
20.44 Let n and k be positive integers with n ≥ k. A partition of n into exactly k parts is a way of expressing n as a sum of k positive integers in which the ordering is immaterial; that is,
and we may assume that n1 ≥ n2 ≥··· ≥ nk.
For instance, three partitions of ‘8’ into exactly 4 parts are shown below:
Note that a partition of n into exactly k parts can also be considered as a way of distributing n identical objects into k identical boxes so that no box is empty.
Let p(n, k) denote the number of partitions of n into exactly k parts.
(i) Given that n ≥ k + 2 and k ≥ 2, prove that p(n,k) ≥ 2. Hence determine all values of n and k such that p(n, k) = 1.
(ii) Prove that, for 
(iii) Find the values of 
and 
and verify that 
(iv) Prove that, for 1 ≤ m ≤ n,
(v) Find the value of p(9,3) and verify that p(10,4) = p(9, 3) + p(6, 4).
(vi) Show that, for 2 ≤ k ≤ n,
(vii) Prove that for m ≥ 1, p(6m, 3) = 3m2.
20.45(i) Ice-cream sticks are tied in bundles of 1, 2, 3 or 4. Let an be the number of ways of bundling and arranging n icecream sticks in a line. Thus, a1 = 1, a2 = 2 and a3 = 4. For example, the arrangements (1,1,1), (1,2), (2,1), and (3) show that a3 = 4. Find a4 and a recurrence relation for an.
(ii) Ice-cream sticks and satay sticks are tied in bundles of 1, 2 or 3. Let bn be the number of ways of bundling and arranging n sticks in a line. For example, if we label the two types of sticks as c and s, the arrangements ({c}, {c}), ({c}, {s}), ({s}, {c}), ({s}, {s}), ({c,c}), ({c,s}), and ({s,s}) show that b2 = 7. Find a recurrence relation for bn.
20.46 (i) There are 20 seats in a row labelled from left to right with the numbers 1, 2,..., 20. Find the number of ways of choosing 5 disjoint pairs of adjacent seats (for instance, {{3, 4}, {9,10}, {11,12}, {15,16}, {19, 20}} is a way) from them.
(ii) There are n seats in a row. Let r be a positive integer such that 2r ≤ n. Find the number of ways of choosing r disjoint pairs of adjacent seats from them.
20.47 In the game of Mastermind, a code is constructed by arranging 4 out of 6 distinct coloured counters in a row. This code is hidden from a player who attempts to break the code by making a series of guesses. Each guess consists of placing counters (not necessarily distinct), which can be chosen from the 6 available colours, into 4 slots in a row. Any of the 4 slots may also be left ‘empty’ instead of placing a counter in it. After each guess, the codemaker will check the guess against the code. For each colour correctly placed, he will allocate a black token, and for each colour present in the code but incorrectly placed, he will allocate a white token. For example, suppose the code is (Blue, Green, Red, Yellow). A guess of (Red, Red, Empty, Empty) will be allocated 1 white token (for the incorrectly placed Red counter). A guess of (Blue, Red, Red, Green) will be allocated 2 black tokens (for the correctly placed Blue and Red counters) and 1 white token (for the incorrectly placed Green counter).
(i) How many possible guesses are there altogether?
(ii) How many guesses will result in no tokens?
(iii) How many guesses will result in 3 white and no black tokens?
(iv) How many guesses will result in 1 white and 3 black tokens?
20.48 Show that if a and b are integers, then the decimal representation of 
either terminates or eventually has a block of digits that repeats itself to infinity. (For example, 
and 
In what follows, let S be an n-element universal set, and let P1, P2,... ,Pq be q properties for the elements of S, where q >1. For integer m with 0 ≤ m ≤ q, let E(m) denote the number of elements of S that possess exactly m of the q properties and for 1 ≤ m ≤ q, let 
denote the number of elements of S that possess the properties Pi1, Pi2,..., Pim, and let
where the summation is taken over all m-combinations {i1, i2,..., im} of {1,2,..., q}. We also define w(0) to be |S|, i. e. w(0) = |S| = n.
In the following problems, we shall establish the following generalised principle of inclusion and exclusion (GPIE) and show two applications of it.
20.49 Prove the following identities.
20.50 Prove (GPIE).
Hint: Let x ∈ S and assume that x possesses exactly t properties. Consider the different possible values of t and count the contribution of x to each side of the inequality.
20.51 Find the number of integers from the set {1, 2,... , 1000} which are divisible by exactly two of 2, 5 and 7.
20.52 Using (GPIE) on a particular value of m, prove that the number of onto mappings from Nm to Nn, where m ≥ n ≥ 1, is given by 
(see Problem 14.5).
20.53 Use a direct combinatorial argument to show that \s(m,k)\ = s*(m, k).
20.54 For integers m,n ≥ 0, prove the following identities:
20.55 For integers m, n > 0, prove the following identities.
(i) 
(ii)
20.56 Let n, k and d be positive integers with n ≥ k ≥ d. Denote by Sd(n, k) the number of ways of partitioning the n-element set n into k nonempty subsets such that for any two elements i and j in each same subset, |i – j| ≥ d. For instance, {{4}, {1,3}, {2,5}} is a partition counted in S2(5,3) and {{1}, {4}, {2, 5}, {3, 6}} is one counted in S2(6, 4) as well as S3(6,4). Clearly, S1 (n,k) = S(n,k).
(i) Verify that S2(5, 3) = 7 by listing all possible partitions.
(ii) Verify that S3(6, 4) = 7 by listing all possible partitions.
(iii) Show that Sd(n,k) = Sd(n – 1,k – 1) + (k – d + 1)Sd (n – 1,k), where n ≥ k ≥ d ≥ 2.
(iv) Show that Sd(n,k) = S(n – d + 1,k – d + 1) where n ≥ k ≥ d ≥ 2.
(Mohr, A. and Porter, T. D., Applications of Chromatic Polynomials Involving Stirling Numbers, Journal of Combinatorial Mathematics and Combinatorial Computing 70 (2009), 5764.)
20.57 For any positive integer n, the nth Bell number (named after E.T. Bell (1883–1960)), denoted by Bn, is defined as the number of ways of dividing n distinct objects into (nonempty) groups i.e. the number of ways of partitioning an n-element set into nonempty subsets. For instance, B3 = 5 and the 5 ways of partitioning {1, 2, 3} into nonempty subsets are shown below: {{1, 2, 3}}, {{1, 2}, {3}}, {{1,3}, {2}},{{2,3},{1}}, {{1},{2},{3}}.
The first 10 Bell numbers are shown below:
B1 = 1, B2 = 2, B3 = 5,B4 = 15, B5 = 52, Be = 203,
B7 = 877, Bg = 4140, B9 = 21147, B10 = 115975.
(i) Explain why Bn = S(n, 1) + S(n, 2) + … + S(n, n).
(ii) Show that
20.58 A “depth” sequence of non-negative integers d1,d2,...,dn, satisfies
(i) d1 = 0
(ii) for i ≥ 1, di+1 ≤ di + 1.
Show that the number of “depth” sequences of length n is C (n).
20.59 A standard Young tableau consists of two rows of boxes with n boxes in each row in which the integers 1,2<...,2n are placed such that the numbers increase from left to right and each number in the bottom row is larger than the number in the box above it.
Show that the number of standard Young tableau with 2n boxes is C (n).
20.60 For r = 1,2,...,2012, let Ar be a set such that |Ar| = 44. Assume that 
for all i, j ∈ {1,2,..., 2012} with i ≠ j. Evaluate 
