COMBINATORICS ASSIGNMENT 1

COMBINATORICS

LEVEL I
Arrangement Based
1. There are 6 roads between A & B and 4 roads between B & C.
(i) In how many ways can one drive from A to C by way of B?
(ii) In how many ways can one drive from A to C and back to A, passing through B on both trips?
(iii) In how many ways can one drive the circular trip described in (ii) without using the same road
more than once.
2. (i) How many car number plates can be made if each plate contains 2 different letters of English
alphabet, followed by 3 different digits.
(ii) Solve the problem, if the first digit cannot be 0.
3. (i) Find the number of four letter word that can be formed from the letters of the word HISTORY.
(each letter to be used at most once)
(ii) How many of them contain only consonants?
(iii) How many of them begin & end in a consonant?
(iv) How many of them begin with a vowel?
(v) How many contain the letters Y?
(vi) How many begin with T & end in a vowel?
(vii) How many being with T & also contain S?
4. In how many ways can 5 letters be mailed if there are 3 different mailboxes available if each letter
can be mailed in any mailbox?
5. Every telephone number consists of 7 digits. How many telephone numbers are there which do not
include any other digits but 2, 3, 5 & 7?
6. How many of the arrangements of the letter of the word “LOGARITHM” begin with a vowel and end
with a consonant?
7. In a telephone system four different letter P, R, S, T and the four digits 3, 5, 7, 8 are used. Find the
maximum number of “telephone numbers” the system can have if each consists of a letter followed
by a four-digit number in which the digit may be repeated.
8. Find the number of 5 lettered palindromes which can be formed using the letters from the English
alphabets.
COMBINATORICS 2

9. Number of ways in which 7 different colours in a rainbow can be arranged if green is always in the
middle.
10. A letter lock consists of three rings each marked with 10 different letters. Find the number of ways in
which it is possible to make unsuccessful attempts to open the lock.
11. It is required to seat 5 men and 4 women in a row so that the women occupy the even places. How
many such arrangements are possible?
12. In how many ways can clean & clouded (overcast) days occur in a week assuming that an entire day
is either clean or clouded.
13. How many 4 lettered words starting with ‘V’ can be formed using letters of VEDANTU if (a)
Repetition not allowed (b) Repetition allowed
14. A new flag is to be designed with six vertical strips using some or all of the colours yellow, green,
blue and red. Then, the number of ways this can be done such that no two adjacent strips have the
same colour is
15. In how many ways Five friends F1, F2, F3, F4 & F5 have to be arranged in a 5 seater car having 2 seats
in front (including driver seat) & 3 seats in the back, such that F1 doesn’t drive. Also, in how many
ways it can be done such that if F1 drives then F2 has to be sit next to him.
16. How many 10 digit numbers can be made with odd digits so that no two consecutive digits are same.
17. Find the number of different signals that can be generated by arranging at least 2 flags in order (one
below the other) on a vertical staff, if five different flags are available.
18. Find all possible three digits even numbers which can be formed with the condition that if 5 is one of
the digit, then 7 is the next digit.
19. How many natural numbers are there from 1 to 1000 which have none of their digits repeated?
20. If repetitions are not permitted
(i) How many 3 digit numbers can be formed from the six digits 2, 3, 5, 6, 7 & 9?
(ii) How many of these are less than 400?
(iii) How many are even?
(iv) How many are odd?
(v) How many are multiples of 5?
21. Find the number of six digit numbers that can be formed from the digits 1, 2, 3, 4, 5, 6 & 7 so that
digits do not repeat and the terminal digits are even.
22. How many numbers between 400 and 1000 (both exclusive) can be made with the digit 2, 3, 4, 5, 6, 0
if
COMBINATORICS 3

(a) Repetition of digits not allowed (b) Repetition of digits is allowed

23. Find the number of 5 digit numbers such that the sum of their digits is even.
24. Find the number of 9 digit numbers that can be formed by using the digits 1, 2, 3, 4 & 5.
25. There are 11 players P1, P2,…..,P11 in a team. How many batting orders are possible if
(a) Either P1 is at first position or P5 is at last position
(b) Neither P1 is at first position nor P5 is at last position.
26. How many of the 900 three digit numbers have at least one even digit?
27. Find the number of natural number from 1000 to 9999 (both inclusive) that do not have all 4 different
digits.

Selection Based
28. A box contains two white balls, three black balls and four red balls. In how many ways can three balls
be drawn from the box if at least one black ball is to be included in the draw?
29. In how many ways can 5 colours be selected out of 8 different colours including red, blue and green
(a) If blue and green are always to be included
(b) If red is a always excluded
(c) If red and blue are always included but green excluded?
30. A student has to answer 10 out of 13 questions in an examination. Find the number of ways in which
he can answer if he must answer atleast 3 of the first five questions.
31. A paper on mathematics consists of twelve questions divided into three parts. A, B and C, each
containing four questions. In how many ways can an examinee answer five questions, selecting at
least one from each part?
32. A woman has 11 close friends. Find the number of ways in which she can invite 5 of them to dinner,
if two particular of them are not on speaking terms and will not attend together.
33. A rack has 5 different pairs of shoes. Find the number of ways in which 4 shoes can be chosen from it
so that there will be no complete pair.
34. Everybody in a room shakes hands with everybody else. The total number of handshakes is 66. Find
the total number of persons in the room.
35. Three ladies have each brought a child for admission to a school. The head of the school wishes to
interview six people one by one, taking care that no child is interviewed before his/her mother. In
how many different ways can the interviews be arranged?
COMBINATORICS 4

36. There are 5 different physics, 3 different chemistry and 4 different math books. In how many ways
books can be selected:
(a) If at least one book is selected.
(b) If at least one book is selected from each subject.
(c) If at least one and at most two books are selected from each subject.
37. The interior angles of a regular polygon measure 150° each. Find the number of diagonals of the
polygon.
38. 18 points are indicated on the perimeter of a triangle ABC (see figure). How many triangles are there
with vertices at these points?

39. Consider 9 points out of which 4 are collinear. Joining these points how many
(a) lines will be made (b) triangles will be made
(c) Quadrilaterals will be made (d) Pentagons will be made
40. Triangles are formed joining the marked points as vertices, when
(i) A is excluded &
(ii) A is included
Find ratio of number of triangles.

41. How many squares & rectangles are there in 8 × 8 chessboard

42. There are n concurrent lines and another line parallel to one of them. The number of different
triangles that will be formed by the (n + 1) lines, is
43. In how many ways we can pick 5 letters out of ARRANGEMENT
44. The total number of selections of fruit which can be made from 3 bananas, 4 apples and 2 oranges is
COMBINATORICS 5

Arrangement and Selection

45. Find the number of ways in which 4 boys and 2 girls (all are of different heights) can be arranged in a
line so that boys as well as girls among themselves are in decreasing order of height (from left to
right).
46. (a) Out of seven consonants and four vowels, the number of words of six letters, formed by taking
four consonants and two vowels is (Assume that each ordered group of letter is a word):
(b) Find the number of permutations of the word “AUROBIND” in which vowels appear in an
alphabetical order.
(c) Find the number of permutations of the word “AUROBIND” in which no two vowels come
together.
47. Find the number of ways in which letters of the word VALEDICTORY be arranged so that the
vowels may never be separated.
48. Four visitors A, B, C & D arrive at a town which has 5 hotels. In how many ways can they disperse
themselves among 5 hotels, if 4 hotels are used to accommodate them.
49. Number of six digit numbers which have 3 digits even and 3 digits odd, if each is to be used atmost
once is ..............
50. If m denotes the number of 5 digit numbers if each successive digits are in their descending order of
magnitude and n is the corresponding figure, when the digits are in their ascending order of
magnitude then (m – n) has the value
51. (a) If the letters of the word “VARUN” are written in all possible ways and then are arranged as in a
dictionary, then the rank of the word VARUN is
(b) The letters of the word RANDOM are written in all possible orders and these words are written
out as in a dictionary then the rank of the word RANDOM is

Arrangement of Alike Objects

52. The total number of arrangements which can be made out of the letters of the word ‘Algebra’, without
altering the relative position of vowels and consonants is
53. The total number of ways of arranging the letters AAAA BBB CC D E F in a row such that letters C
are separated from one another is
54. The number 2006 is made up of exactly two zeros and two other digits whose sum is 8. The number
of 4 digit numbers with these properties (including 2006) is :
COMBINATORICS 6

Divisor, Sum of Divisors & Exponent of p in n!

55. For the number 34  52  73 , find
(a) Number of divisors
(b) Number of even divisors
(c) Number of divisors which are multiple of 21
(d) Sum of all the divisors
56. Find exponent of
(a) 3 in 100!
(b) 10 in 100!
(c) Power of 5 in 30C12

57. (a) In how many ways the number 7056 can be resolved as a product of 2 factors.
(b) Find the number of ways in which the number 300300 can be split into 2 factors which are
relatively prime.
58. The number of odd proper divisors of 3p . 6m . 21n is :

De arrangement
59. In how many ways 6 letters can be placed in 6 envelopes such that
(a) No letter is placed in its corresponding envelope.
(b) At least 4 letters are placed in correct envelopes.
(c) At most 3 letters are placed in wrong envelopes

Distribution of item into Groups

60. Find the total number of ways in which n2 number of identical balls can be put in n numbered boxed
(1, 2, 3, ......... n) such that ith box contains at least i number of balls.
61. Find the number of ways in which n different prizes can be distributed amongst m (< n) persons if
each is entitled to receive at most n – 1 prizes.
62. (a) The number of ways in which 12 balls can be divided between two friends, one receiving 8 and
the other 4, is
(b) The number of ways in which 52 cards can be divided into 4 sets, three of them having 17 cards
each and the fourth one having just one card
COMBINATORICS 7

63. Seven different coins are to be divided amongst three persons. If no two of the persons receive the
same number of coins but each receives at least one coin and none is left over, then the number of
ways in which the division may be made is:
64. Number of different ways in which 8 different books can be distributed among 3 students, if each
student receive at least 2 books is ...............
65. The number of ordered triplets of positive integers which are solutions of the equation
x + y + z = 100 is
66. The total number of ways of selecting six coins out of 20 one rupee coins, 10 fifty paise coins and 7
twenty five paise coins is
67. Find number of integral solutions of:
(a) x + y + z = 10 ; x  0, y  2, z  0
(b) x + y + z + w = 12 ; x  4, y  −2, z  −3
(c) 2 x + y + z = 10 ; x  2, y  0, z  0
(d) x + y + z = 12 ; 1  x  3, y  0, z  0
68. In how many ways 5 fruits can be selected out of unlimited identical bananas, identical apples &
identical oranges.
69. Find number of non-negative integral solutions of: x + y + z  5
70. Find the number of positive integer solutions of x + y + z = 10, where x, y, z are unequal
71. There are three piles of identical red, blue and green balls each pile contains at least 10 balls. The
number of ways of selecting 10 balls if twice as many red balls as green balls are to be selected is
72. The number of ways in which 5 identical balls can be kept in 10 identical boxes, if not more than one
can go into a box, is
73. 5 balls are to be placed in 3 boxes. Each box can hold all the 5 balls. Number of ways in which the
balls can be placed so that no box remains empty, if :
(a) balls are identical but boxes are different
(b) balls are different but boxes are identical
(c) balls as well as boxes are identical
(d) balls as well as boxes are identical but boxes are kept in a row

Circular Arrangement
74. There are 16 men sitting on a round table. Find the number of ways to select 7 men such that no two
are consecutive.
COMBINATORICS 8

75. How many garlands of 6 flowers of different colours be made out of 10 flowers of different colors?
76. In how many ways a team of 11 cricket players may sit on a round table so that captain, vice captain
& wicket keeper are together.
77. Find the number of ways in which seven persons can be arranged at a round table if two particular
persons may not sit together.
COMBINATORICS 9

LEVEL II
1. Find the number of times the digit 5 will be written when listing integers from 1 to 1000.
2. A seven digit number divisible by 9 is to be formed by using 7 out of numbers {1, 2, 3, 4, 5, 6, 7, 8,
9}. Find the number of ways in which this can be done.
3. (a) A 5 digit number divisible by 3 is to be formed using the numerals 0, 1, 2, 3, 4 & 5 without
repetition. Find the total number of ways.
(b) How many five digits numbers divisible by 3 can be formed using the digits 0, 1, 2, 3, 4, 7 and
8
if each digit is to be used at most once?
4. A committee of 5 is to be chosen from a group of 9 people. Find the number of ways in which it
can be formed if two particular persons either serve together or not at all and two other particular
persons refuse to serve with each other.
5. In a certain algebra exercise book there are 4 examples on arithmetical progressions, 5 examples of
permutation – combination and 6 examples on binomial theorem. Find the number of ways a teacher
can select for his pupils atleast one but not more than 2 examples from each of these sets.
6. How many ordered pairs (P, Q) of subsets of {a, b, c, d, e} can be made such that:
(a) P  Q = 

(b) P  Q = a

(c) P  Q Contains exactly 2 elements

7. A seven digit number with distinct digits is in form of abcdefg (g, f, e, etc. are digits at units, tens,
hundred place etc.) where a < b < c < d > e > f > g. Find the number of such numbers.
8. The number of ways of arranging ‘m’ number out of 1, 2, 3, . . . . ., n so that maximum is (n – 2)
and minimum is 2 (repetitions of numbers is allowed) such that maximum and minimum both occur
exactly once, (n > 5, m > 3) is
(a) n – 3Cm – 2 (b) mC2 (n – 3)m – 2
(c) m (m – 1) (n – 5)m – 2 (d) nC2 . nCm
Thus, number of ways of arranging the numbers = m(m -1)(n - 5)m – 2
9. Total number of ways of selecting two numbers from the set {1, 2, 3, 4, …., 3n} so that their sum is
divisible by 3 is equal to:
10. There are m points on a straight line AB and n points on the line AC none of them being the point
A. Triangles are formed with these points as vertices, when
COMBINATORICS 10

(i) A is excluded (ii) A is included

The ratio of number of triangle in the two cases is:
11. In a plane there are 6 lines, no two of which are parallel & no three are concurrent. How many
triangles can be formed with their points of intersection as vertices
12. The number of ways in which we can choose 3 squares of unit area on a chess board such that one
of the squares has its two sides common to other two squares
13. Given 11 points, of which 5 lies on one circle, other than these 5, no 4 lie on one circle. Then the
maximum number of circles that can be drawn so that each contains atleast three of the given points
is:
14. Two classrooms A and B having capacity of 25 and (n – 25) seats respectively. An denotes the
number of possible seating arrangements of room ‘A’, when ‘n’ students are to be seated in these
rooms, starting from room ‘A’ which is to be filled up full to its capacity.
If An – An – 1 = 25 ! (49C25) then ‘n’ equals
15. In how many ways it is possible to select six letters, including at least one vowel from the letters of
the word “F L A B E L L I F O R M”. (It is a picnic spot in U. S. A.)
16. The total number of permutations of 4 letters that can be made out of the letters of the word
EXAMINATION is
17. Number of ways in which letters of the word ENGINEER can be arranged :
(a) so that the word starts with E but does not end with N.
(b) so that the word neither starts with E nor ends with N.
(c) so that vowels occur in alphabetical order.
(d) so that no two alike letters are together.
18. The number of divisors of 23 . 33 . 53 . 75 of the form 4n + 1, n ∈ N is :
19. A disarranged number from the set 1 – 9 is an arrangement of all these number so that all numbers
take up its unusual position. (e.g. 1 is in any place other than the first position, 2 is in any place
other than the second position ......... all the way to 9). Number of ways in which at least six number
stake up their usual positions, is
20. How many ten digits whole number satisfy the following property they have 2 and 5 as digits, and
there are no consecutive 2's in the number (i.e. any two 2's are separated by at least one 5).
21. How many 4 digit numbers are there which contains not more than 2 different digits?
COMBINATORICS 11

22. There are counters available in 7 different colours. Counters are all alike except for the colour and
they are at least ten of each colour. Find the number of ways in which an arrangement of 10
counters can be made. How many of these will have counters of each colour.
23. The number of seven digit integers, with sum of the digits equal to 10 and formed by using the
digits 1,2 and 3 only, is
24. Let the product of all the divisors of 1440 be P. If P is divisible by 24x, then the maximum value of
x is
25. The number of three digit numbers of the form xyz such that x < y and z  y is
26. Consider the network of equally spaced parallel lines(6 horizontal and 9 vertical) shown in the
figure. All small squares are of the same size. A shortest route from A to C is defines as a route
consisting 8 horizontal steps and 5 vertical steps.

(a). The number of shortest routes through the junction P is:

(b) The number of shortest routes which go following street PQ must be
(c) The number of shortest routes which passes through junction P and R
27. The minimum marks required for clearing a certain screening paper is 210 out of 300. The
screening paper consists of ‘3’ sections each of Physics, Chemistry, and Maths. Each section has
100 as maximum marks. Assuming there is no negative marking and marks obtained in each
section are integers, find the number of ways in which a student can qualify the examination is
(Assuming no cut–off limit).
28. 10 identical balls are to be distributed in 5 different boxes kept in a row and labled A, B, C, D and
E. Find the number of ways in which the balls can be distributed in the boxes if no two adjacent
boxes remain empty
29. Find how many three digit numbers, lying between 100 and 999 inclusive, have two and only two
cosecutive digits identical.
COMBINATORICS 12

30. Let X = {1,2,3,…17}. Find the number of subsets Y of X with odd cardinalities.
31. How many integers are there between 0 and 105 having the digit sum of equal to 8?
32. Find the largest positive integer n such that n! ends with exactly 100 zeroes.
33. Suppose 40 objects are placed along a circle at equal distances. In how many ways can 3
objects be chosen from among them so that no two of the three chosen objects are adjacent nor
diametrically opposite?
34. Five students A, B, C, D and E from a team to take part in a 5 leg relay competition. If A cannot
run the first leg and D cannot run the last leg, how many ways can we arrange them to run the relay
?
35. Suppose that each of n people knows exactly one piece of information, and all n pieces are
different. Every time person A phones person B, A tells B everything he known, while B tells A
nothing. What is the minimum of phones called between pairs of people needed for everyone to
know everything?
36. For each positive integer n, let an denote the number of n digit integers formed by some or all of the
digits 0,1,2 and 3 which contain neither a block of 12 nor a block of 21. Evaluate a9
37. As shown in the picture, the knight can move to any of the indicated squares of the 8 x 8
chessboard in 1 move. If the knight starts from the position shown, find the number of possible
landing positions after 20 consecutive moves

38. How many four digit numbers greater than 5000 can be formed from the digit 0, 1, 2, 3, 4, 5, 6, 7,
8, 9 if only the digit 4 may be repeated?
COMBINATORICS 13

39. There girls A,B and C, and nine boys are to be lined up in a row. Let n be the number of ways ths
can be done if B must lie between A and C, and A, B must be separated by exactly 4 boys.
Determine [n/7!]
40. Determine the number of positive integer divisors of 99849999 that are not the divisors of 99849998
41. Consider a 2008 x 2008 chess board. Let M be the smallest number of rectangles that can be drawn
on the chess board so that the sides of every cell of the board is contained in the sides of the one of
the rectangles. Find the value of M. (For example for the 2 x 3 chess board, the value of M is 3).
42. Determine the number of 8-digit positive integers such that after deleting any one digit, the
remaining 7-digit number is divisible by 7.
43. In how many ways can a team of 6 horses be selected out of a stud of 16, so that there shall always
be 3 out of A B C A’ B’C’, but never A A’ , B B’ or C C’ together.
44. There are n straight lines in a plane, no 2 of which parallel, & no 3 pass through the same point.
Their point of intersection are joined. Show that the number of fresh lines thus introduced is n(n -
1)(n - 2)(n - 3)/8
45. Prove that if each of m points in one straight line be joined to each of n in another by straight lines
terminated by the points, then excluding the given points, the lines will intersect
¼ mn(m – 1)(n –1) times.
46. Find the number of words each consisting of 3 consonants & 3 vowels that can be formed from the
letters of the word “circumference”. In how many of these all ‘c’s will be together.
47. How many different ways can 15 Candy bars be distributed between Ram, Shyam, Ghanshyam and
Balram, if Ram can not have more than 5 candy bars and Shyam must have at least two. Assume all
Candy bars to be alike.
48. How many integers between 1000 and 9999 have exactly one pair of equal digit such as 4049 or
9902 but not 4449 or 4040?
49. In a box there are 10 balls, 4 red, 3 black, 2 white and 1 yellow. In how many ways can a child
select 4 balls out of these 10 balls ? (Assume that the balls of the same color are identical)
In a certain test, ai students gave wrong answers to at least i question, where i = 1, 2,...., k. No
student gave more that k wrong answers. Find the total number of wrong answer given.
n2 !
50. Use permutation or otherwise, prove that is an integer, where n is a positive integer.
( n !)
n

51. Number of positive integral solutions satisfying the equation (x1 + x2 + x3) (y1 + y2) = 77, is
COMBINATORICS 14

52. In the figure, two 4–digit numbers are to be formed by filling the places with digits. The number of
different ways in which the places can be filled by digits so that the sum of the numbers formed is
also a 4–digit number and in no place the addition is with carrying is :

53. The number of different ways the letters of the word VECTOR can be placed in 8 boxes given
below such that no row remains empty is equal to:

54. The number of ways of choosing triplets (x, y, z) such that z ≥ max {x, y} and x, y, z ∈{1, 2, . . . . ,
n} is
55. Total number of positive integral solution of 15 < x1 + x2 + x3 ≤ 20 is equal to
Ans. 685
56. The number of ways in which we can choose 2 distinct integers from 1 to 100 such that difference
between them at most 10 is:
(a) 40C2 (b) 70C2 (c) 100C2 – 99C2 (d) None of these
57. Number of different words that can be formed using all the letters of the word “DEEPMALA” if
two vowels are together and the other two are also together but separated from the first two is :
(a) 960 (b) 1200 (c) 2160 (d) 1440
58. The number of permutation of the letters of the word HINDUSTAN such that neither the pattern
‘HIN’ nor ‘DUS’ nor ‘TAN’ appears, are:
9! 7!
3. = − (7 !+ 7 !+ ) + 3(5!) − 3!
2! 2!
=169194
59. There are 720 permutation of the digits 1, 2, 3, 4, 5, 6. Suppose these permutations are arranged
from smallest to largest numerical values, beginning from 1 2 3 4 5 6 and ending with 6 5 4 3 2 1.
(a) What number falls on the 124th positions?
COMBINATORICS 15

(b) What is the position of the number 321546?

60. A forecast is to be made of the results of five cricket matches, each of can be win, a draw or a lost
for Indian team. Find
(i) the number of different possible forecasts
(ii) the number of forecasts containing 0, 1, 2, 3, 4 and 5 errors respectively
61. In Indo-Pak one day International cricket match at Sharjah , India needs 14 runs to win just before
the start of the final over. Find the number of ways in which India just manages to win the match
(i.e. scores exactly 14 runs) , assuming that all the runs are made off the bat & the batsman can not
score more than 4 runs off any ball
62. A question paper on mathematics consists of twelve questions divided into three parts. A, B and C,
each containing four questions. In how many ways can an examinee answer five questions,
selecting at least one from each part.
63. The number of ways in which 8 distinguishable apples can be distributed among 3 boys such that
every boy should get at least 1 apple and at most 4 apples is K. 7P3 where K has the value equal to
64. There are 12 books on Algebra and Calculus in our library, the books of the same subject being
different. If the number of selections each of which consists of 3 books on each topic is greatest
then the number of books of Algebra and Calculus in the library are respectively :
65. A gentleman invites a party of m + n (m ≠ n) friends to a dinner and places m at one table T1 and n
at another table T2, the table being round. If not all people shall have the same neighbor in any two
arrangement, then the number of ways in which he can arrange the guests, is
66. Find the number of integer between 1 and 10000 with at least one 8 and at least one 9 as digits.
67. Sameer has to make a telephone call to his friend Harish, Unfortunately he does not remember the 7
digit phone number. But he remembers that the first three digits are 635 or 674, the number is odd
and there is exactly one 9 in the number. The maximum number of trials that Sameer has to make to
be successful is
68. Six faces of an ordinary cubical die marked with alphabets A, B, C, D, E and F is thrown n times
and the list of n alphabets showing up are noted. Find the total number of ways in which among the
alphabets A, B, C, D, E and F only three of them appear in the list.
Ways = 6C3[3n – 3C12n + 3C2]
COMBINATORICS 16

LEVEL III
1. Find the number of integers in the set {1,2,3,….,2009} whose sum of the digits is 11.
2. A four digit number consists of two distinct pairs of repeated digits (for example 2211, 2626 and
7007). Find the total number of such possible numbers that are divisible by 7 or 101 but no both
3. Using the digits 0,1,2,3 and 4, find the number of 13 digit sequence that can be written so that the
difference between any two consecutive digits is 1
Examples of such 13 – digit sequence are 0123432123432, 2323432321234 and 23010101234323
4. Three are eight envelops numbers 1 to 8. Find the number of ways in which 4 identical red buttons
and 4 identical blue buttons can be put in the envelops such that each envelope contains exactly one
button, and the sum of the numbers on the envelops the red buttons is more than the sum of the
numbers on the envelops containing the blue buttons.
5. Find the number of positive divisors of (20083 + (3 X 2008 X 2009) + 1)2
6. Find the number of 2-element subsets {a, b} of {1,2,3,…,99, 100} such that ab + a + b is a multiple
of 7.
Find the number of 0–1 binary sequences for by six 0’s and six 1’s such that no three 0’s are
together. For example,110010100101 is such a sequence but 101011000101 and 11010110001 are
not
7. Using the digits 1,2,3,4,5,6,7,8, we can form 8!(=40320) 8–digit numbers in which the eight digits
are all distinct. For 1 ≤ k ≤ 40320 , let “a” denote the kth number if these numbers are arranged in
increasing order:
12345678, 12345687, 12345768,……87654321 ;
that is a1 = 12345678, a2 = 1245687, ….a40320 = 87654321. Find a2009 – a2008
8. Let A be an n -element subset of {1, 2,……,2009} with the property that the difference between
any two numbers in A is not a prime number. Find the largest possible value of n. Find a set with
this number of elements. (Note : 1 is not a prime number)
9. Let S = {1, 2, 3,……, 30}. Determine the number of vectors (x, y, z, w) with x, y, z, w ∈ S such
that x < w and y < z < w.
10. Let f(n) be the number of 0’s in the decimal representation of the positive integer n. For example
f(10001123) = 3 and f (1234567) = 0. Find the value of f(1) + f(2) + f(3) +….f(99999)
11. Let S= {1.2,3,4,…16}. In each of the following subsets of S.
{6}, {1,2,3}, {5,7,9,10,11,12}, {1,2,3,4,5,6,7,8,9}
COMBINATORICS 17

The sum of the all the elements is a multiple of 3. Find the total number of non empty subsets A of
S such that the sum of all elements in A is a multiple of 3.
12. Determine the number of ways of tilling a 4 x 9 rectangle by tiles of size 1 x 2.
13. Find the number of 7 digit positive integer such that the digits from left to right non increasing
(Examples of 7 digit non increasing numbers are 9998766 and 555555 ; An example of a number
that is NOT non increasing is 7776556).
14. Determine the number of 4-elements subsets {a, b, c, d} of {1,2,3,4,…,20} such that a + b + c + d is
divisible by 3.
15. There are 5 white, 4 yellow, 3 green, 2 blue & 1 red balls. The balls are all identical except for
color. Five of these are to be arranged in a line. Find the number of distinct arrangements.
16. There are 20 books on Algebra & Calculus in our library. Prove that the greatest number of
selections each of which consists of 5 books on each topic is possible only when there are 10 books
on each topic in the library.
17. 6 white & 6 black balls of the same size are distributed among 10 different urns. Balls are alike
except for the color & each urn can hold any number of balls. Find the number of different
distribution of the balls so that there is at least 1 ball in each urn.
18. How many 15 letter arrangements of 5 A's, 5 B's and 5 C's have no A's in the first 5 letters, no B's
in the next 5 letters, and no C's in the last 5 letters?
19. Let an denote the number of all n-digit positive integers formed by the digits 0, 1 or both such that
no consecutive digits in them are 0. Let bn = The number of such n-digit integers ending with digit 1
and cn = The number of such n-digit integers ending with digit 0.
i. Which of the following is correct?
(a) a17 = a16 + a15 (b) c17 ≠ c16 + c15
(c) b17 ≠ b16 + c16 (d) a17 = c17 + b16
ii. The value of b6 is
(a) 7 (b) 8 (c) 9 (d) 11
20. In an examination the maximum marks for each of three papers is n and that for fourth paper is 2n.
If marks obtained in each paper are whole numbers, then the number of ways in which a candidate
can get 3n marks is
21. Determine the number of 3-digit numbers in base 10 having
(i) At least one 5 and having no 3 and (ii) At least one 5 and having exactly one 3 separately.\
COMBINATORICS 18

22. Find the number of combinations n together of 3n letters of which n are 'a' and n are 'b' and the rest
unlike.
= (n + 2). 2n-1
23. Let A be any k element subset of the set {1, 2, 3, 4…, 100}. Determine the minimum value of k
such that we can always guarantee the existence of two numbers a and b in A such that
|a–b| ≤ 4
COMBINATORICS 19

ANSWERS KEY
LEVEL I
1. (i) 24, (ii) 576, (iii) 360 2. (i) 468000, (ii) 421200
3. (i) 840, (ii) 120, (iii) 400, (iv) 240, (v) 480, (vi) 40, (vii) 60
4. 243, 5. 47 6. 90720, 7. 1024, 8. (26)3 9. 720
10. 999, 11. 2880, 12. 128, 13. (a) 120, (b) 343 14. 972, 15. 4 x 4!, 3!
16. 5  49 17. 320 18. 365 19. 738
20. (i) 120, (ii) 40, (iii) 40, (iv) 80, (v) 20 21. 720 22. (a) 60, (b) 107
23. 45000 24. (59) 25. (a) 6894720, (b) 33022080 26. 775 27. 4464
28. 64 29. (a) 20, (b) 21, (c) 10 30. 276 31. 624 32. 378
33. 80 34. 12, 35. 90 36. (a) 212 – 1, (b) (25 – 1)(23 – 1)(24 – 1), (c) 900
37. 54 38. 711, 39. (a) 31, (b) 80, (c) 105 (d) 81 40. 7 : 9 41. 204,
(n − 1)(n − 2)
42. 43. 131, 44. 60, 45. 15,
2
8!
46. (a) 151200, (b) , (c) 5C4 4!4! 47. 967680 48. 120
4!
4!3!
49. 64800 50. ( 9 C5 ) 51. (a) 100, (b) 614 52.
2!
53. 1386000 54. 21, 55. (a) 60, (b) 0, (c) 36, (d)1500400,
56. (a) 48, (b) 11, (c) 2, 57. (a) 23, (b) 32 58. (p + m + n + 1) (n + 1) – 1
n2 + n − 2
59. (a) 265, (b) 16, (c) 56 60. 2
Cn−1 61. mn – m

12! 52!
62. (a) (b) 63. 630 64. 2940 65. 4851, 66. 28,
(17!) 3!
3
8!4!

67. (a) 36, (b) 120, (c) 16 (d) 33 68. 21, 69. 56, 70. 24,
71. 4, 72. 1, 73. (a) 6, (b) 15, (c) 2, (d) 6 74. 8C6 16 / 7

75. 12600 76. 241920 77. 480

COMBINATORICS 20

LEVEL II
1. 300 2. 4 x 7! 3. (a) 216, (b) 744 4. 41, 5. 3150
3n 2 − n
6. (a) 243, (b) 81, (c) 270 7. 1560 8. m (m – 1) (n – 5)m – 2 9. =
2
m+n−2
10. 11. 395 12. 292 13. 156 14. 50
m+n
15. 296 16. 2454 17. (a) 900, (b) 1620, (c) 840, (d) 960
18. 47 19. 205 20. 143 21. 576,
22. 710, (49/6)10! 23. 77, 24. 30, 25. 276,
26. (a) 560 (b) 350 (c) 240 27. 93C3 28. 771 29. 162, 30. 65536,
31. 495 32. 409, 33. 7720, 34. 78 35. 2n – 2
36. 73368 37. 32 38. 2645 39. 3024 40. 99999
41. 2009 42. 64 43. 960 46. 22100, 52, 47. 440
48. 3888, 49. 20 50. a1 + a2 + a3 +…….+ ak
52. 420, 53. 36 (55)3 54. 26 × 6! 55. n + 1C3 + n + 2 C3
56. 685 57. d 58. d 59. 169194
60. (a) 213564, (b) 267th 61. (i) 243; (ii) 1, 10, 40, 80, 80, 32 62. 1506
63. 624 64. 22 65. 6, 6 66. (m + n)!/4mn 67. 974,
68. 3402, 69. 6C3[3n – 3C1(2n – 2) – 3C2]

LEVEL III
1. 133, 2. 97, 3. 3402, 4. 31, 5. 91
6. 602 7. 357, 8. 11754, 9. 441 10. 504
11. 90335, 12. 38889, 13. 21855, 14. 6336 15. 11439,
16. 11901, 17. 2111, 19. 26250, 20. 2252 21. a, b
1
22. (n + 1) (5n2 + 10n + 6) 23. (i) 200, (ii) 249
6
24. (n + 2). 2n-1 25. 21,
COMBINATORICS 21

SOLUTIOS
LEVEL I
Arrangement Based
1. There are 6 roads between A & B and 4 roads between B & C.
(i) In how many ways can one drive from A to C by way of B?
(ii) In how many ways can one drive from A to C and back to A, passing through B on both trips?
(iii) In how many ways can one drive the circular trip described in (ii) without using the same road
more than once.
Sol: (i) Given, roads from A to B is 6 and roads from B to C is 4
⸫ Number of ways to drive A to C via B = 6 × 4 = 24
(ii) Since number of ways to drive from A to C via B is 24
⸫ A to C and back via B = 24 × 24 = 576 ways
(iii) Since we cant use the road more than once
Thus, while returning back, we have to avoid one road from C to B and B to A
⸫ Total number of ways = (24) (5 × 3 ) = 360
2. (i) How many car number plates can be made if each plate contains 2 different letters of English
alphabet, followed by 3 different digits.
(ii) Solve the problem, if the first digit cannot be 0.
Sol: (i) As there are 26 different alphabets and 10 different digits
⸫ Total number of number plates = (26 × 25) (10 × 9 × 8) = 468000
(ii) Since first digit cant be zero
⸫ Number of ways = (26 × 25) (9 × 9 × 8) = 421200
3. (i) Find the number of four letter word that can be formed from the letters of the word HISTORY.
(each letter to be used at most once)
(ii) How many of them contain only consonants?
(iii) How many of them begin & end in a consonant?
(iv) How many of them begin with a vowel?
(v) How many contain the letters Y?
(vi) How many begin with T & end in a vowel?
(vii) How many being with T & also contain S?
COMBINATORICS 22

Sol: (i) Given, H, I, S, T, O, R, Y i.e. 7 letters

⸫ Number of four letters word
= 7  6 5 4
= 840
(ii) Number of four letter words that contain only consonants
= 5 4  3 2
= 120
(iii) We require word to begin and end with a consonant
This can be done as

= 25  16
= 400
(iv) Words beginning with a vowel are

= 240
(v) Words containing the letter Y
= Total words – words which don’t contain Y
= 840 − ( 6  5  4  3)
= 840 − 360
= 480
(vi) Begin with T and end with a vowel

=5×4×2
= 40
(vii) Begin with T and also contain S
COMBINATORICS 23

TS-- or T-S- or T—S

Blank space can be filled by remaining 5 letters
⸫ Total words = 3 × 5 × 4 = 60
4. In how many ways can 5 letters be mailed if there are 3 different mailboxes available if each letter
can be mailed in any mailbox?
Sol: Here every letter have 3 ways or 3 mail boxes in which they can go
⸫ Total number of ways = 3  3  3  3  3 = 243
5. Every telephone number consists of 7 digits. How many telephone numbers are there which do not
include any other digits but 2, 3, 5 & 7?
Sol: Here every digit of telephone number has 4 ways to be filled with 4 digits
⸫ Total number of ways
= 4 4 4 4 4 4 4
= 47
6. How many of the arrangements of the letter of the word “LOGARITHM” begin with a vowel and end
with a consonant?
Sol: There are 3 vowels (O, I, A) and six consonants (L, G, R, T, H, M)
⸫ Word with begin with a vowel and end with a consonant are

⸫ Total number of ways = 90720

7. In a telephone system four different letter P, R, S, T and the four digits 3, 5, 7, 8 are used. Find the
maximum number of “telephone numbers” the system can have if each consists of a letter followed
by a four-digit number in which the digit may be repeated.
Sol: Since we can start a telephone number by any of 4 letters, and then a four digit number where digits
can be repeated can be done as

⸫ Total numbers = 45 = 1024

8. Find the number of 5 lettered palindromes which can be formed using the letters from the English
alphabets.
COMBINATORICS 24

Sol: Palindromes are those where reverse order gives the same word again
Thus 5 letter palindrome can be formed from 26 alphabets in

⸫ Total number of ways = (26)3

9. Number of ways in which 7 different colours in a rainbow can be arranged if green is always in the
middle.
Sol: Rainbow where green is always in the middle

⸫ Total different rainbow

= 6  5  4  3  2 1
= 6! = 720
10. A letter lock consists of three rings each marked with 10 different letters. Find the number of ways in
which it is possible to make unsuccessful attempts to open the lock.
Sol: All different kinds of attempts from 10 different letters = 10 × 10 × 10 = 1000
Out of these only 1 is correct
⸫ Number of unsuccessful attempts are = 1000 – 1 = 999
11. It is required to seat 5 men and 4 women in a row so that the women occupy the even places. How
many such arrangements are possible?
Sol: Out of 9 seats there are 4 even places, thus 4 women can seat on them in 4! ways and remaining 5
boys in odd places in 5! ways
⸫ Total number of ways = 4! × 5! = 2880
12. In how many ways can clean & clouded (overcast) days occur in a week assuming that an entire day
is either clean or clouded.
Sol: Since each day can be either calm or clouded
Thus,
Total number of ways
= 2 2 2 2 2 2 2
= 27 = 128
COMBINATORICS 25

13. How many 4 lettered words starting with ‘V’ can be formed using letters of VEDANTU if (a)
Repetition not allowed (b) Repetition allowed
Sol: (a) We have to make 4 lettered word from letters V, E, D, A, N, T, U
Such that they start with V
This can be done as

= 120 ways
(b) when repetition is allowed then = 7  7  7 = 343 ways
14. A new flag is to be designed with six vertical strips using some or all of the colours yellow, green,
blue and red. Then, the number of ways this can be done such that no two adjacent strips have the
same colour is
Sol: Given, we have 4 colours and flag consists of 6 strips
Such that no two adjacent strip is same then
Total number of flags = 4  3  3  3  3  3
= 12  81
= 972
15. In how many ways Five friends F1, F2, F3, F4 & F5 have to be arranged in a 5 seater car having 2 seats
in front (including driver seat) & 3 seats in the back, such that F1 doesn’t drive. Also, in how many
ways it can be done such that if F1 drives then F2 has to be sit next to him.
Sol: If F1 don’t drives, then driver can be among any four of other friends and remaining seat can be
arranged in 4! Ways
⸫ Total number of ways when F1 is not driving = 4 × 4! ways
Also, if F1 drives such that F2 sit next to him, then only 3 back seats are left where F3, F4 & F5
can arrange in 3! Ways.
16. How many 10 digit numbers can be made with odd digits so that no two consecutive digits are same.
Ans. 5⨯49
Sol. 5⨯4⨯4⨯4⨯4……..⨯4 = 5⨯49
17. Find the number of different signals that can be generated by arranging at least 2 flags in order (one
below the other) on a vertical staff, if five different flags are available.
Sol. Since a signal may consist of either 2 flags, 3 flags, 4 flags or 5 flags. Therefore,
Total number of signals = Number of 2 flags signals
COMBINATORICS 26

+ Number of 3 flags signals

+ Number of 4 flags signals
+ Number of 5 flags signals
=5×4+5×4×3+5×4×3×2+5×4×3×2×1
= 20 + 60 + 120 + 120 = 320
18. Find all possible three digits even numbers which can be formed with the condition that if 5 is one of
the digit, then 7 is the next digit.
Ans. 365
CASE I: if 5 come’s the next digit is 7
5 7 Even No.
1⨯1⨯5 = 5 ways
CASE II: if 5 doesn’t come then may or may not come.
Any no. excluding 0 & 5Any no. excluding 5Even No.
8⨯9⨯5 = 360 ways
Total = 360 + 5 = 365 ways
19. How many natural numbers are there from 1 to 1000 which have none of their digits repeated?
Sol: Natural numbers 1 to 1000 where digits are not repeated
Single digit numbers = 9
Two digit numbers = 9 × 9 = 81
Three digit numbers = 9 × 9 × 8 = 648
⸫ Total numbers = 9 + 81 + 648 = 738
20. If repetitions are not permitted
(i) How many 3 digit numbers can be formed from the six digits 2, 3, 5, 6, 7 & 9?
(ii) How many of these are less than 400?
(iii) How many are even?
(iv) How many are odd?
(v) How many are multiples of 5?
Sol: (i) Three digit number from 6 digit
COMBINATORICS 27

= 6 × 5 × 4 = 120
(ii) Numbers less than 400

= 2 × 5 × 4 = 40
(iii) even numbers

= 2 × 5 × 4 = 40
(iv) Odd numbers

= 5 × 4 × 4 = 80
(v) Multiples of 5

= 5 × 4 × 1 = 20
21. Find the number of six digit numbers that can be formed from the digits 1, 2, 3, 4, 5, 6 & 7 so that
digits do not repeat and the terminal digits are even.
Sol: Given digits are 1, 2, 3, 4, 5, 6 and 7
Six digit number whose terminal digit are even are

⸫ Total numbers = 3  5  4  3  2  2
COMBINATORICS 28

= 720
22. How many numbers between 400 and 1000 (both exclusive) can be made with the digit 2, 3, 4, 5, 6, 0
if
(a) Repetition of digits not allowed (b) Repetition of digits is allowed
Sol: (a) Given digits 2, 3, 4, 5, 6, 0
Number more than 400 and less than 1000, when repetition of digits not allowed are

= 3 × 4 × 5 = 60
(b) Repetition of digits are allowed

= 3 × 6 × 6 = 108
But it includes 400, thus
Total numbers = 108 – 1 = 107
23. Find the number of 5 digit numbers such that the sum of their digits is even.
Sol: As there are total 90,000 5 digit natural numbers, out of which half will give sum even and half will
give sum odd
⸫ 5 digit numbers such that the sum of their digit is even is = 45000
24. Find the number of 9 digit numbers that can be formed by using the digits 1, 2, 3, 4 & 5.
Ans: (59)
Sol: Number of 9 digit number that can be made using 5 digits = 59
25. There are 11 players P1, P2,…..,P11 in a team. How many batting orders are possible if
(a) Either P1 is at first position or P5 is at last position
(b) Neither P1 is at first position nor P5 is at last position.
Sol: (a) Let n(A) be number of batting order when P1 is at first position n(B), when P5 is at last position
n ( A  B ) , when P1 is at first position and P5 is at last.
COMBINATORICS 29

n ( A ) = 10! = 3628800
n ( B ) = 10! = 3628800
n ( A  B ) = 9! = 362880

 n ( A  B ) = n ( A) + n ( B ) − n ( A  B )
= 10!+ 10!− 9!
= 6894720
(b) Neither P1 is at first position nor P5 is at last position
= Total possible order – when either P1 is at first or P5 is at last
= 11!− (10!+ 10!− 9!)
= 39916800 − ( 6894720 )
= 33022080
26. How many of the 900 three digit numbers have at least one even digit?
Ans: (775)
Sol: Three digit numbers which must have at least one even digit
= Total three digit numbers – Numbers not having even digits
= 900 – 125 = 775
27. Find the number of natural number from 1000 to 9999 (both inclusive) that do not have all 4 different
digits.
Ans (4464)
Sol: Natural numbers from 1000 to 9999 that do not have all 4 different digits are
= Total numbers – Numbers which have all different digits
= 9000 – 4536
= 4464

Selection Based
28. A box contains two white balls, three black balls and four red balls. In how many ways can three balls
be drawn from the box if at least one black ball is to be included in the draw?
Sol: Number of ways such that at least one black ball is included
= Total number of ways – No black ball is taken
= 9C3 − 6C3
= 84 − 20 = 64
29. In how many ways can 5 colours be selected out of 8 different colours including red, blue and green
COMBINATORICS 30

(a) If blue and green are always to be included

(b) If red is a always excluded
(c) If red and blue are always included but green excluded?
Sol: (a) If blue and green are always to be included
= 8−2C5−2
= 6C3 = 20
(b) Red is always excluded
= 8−1C5
= 7C5 = 21
(c) Red and blue balls are always included but green excluded
= 8−2−1C5−2
= 5C3 = 10
30. A student has to answer 10 out of 13 questions in an examination. Find the number of ways in which
he can answer if he must answer atleast 3 of the first five questions.
Ans: (276)
Sol:

⸫ Total number of ways

= 5C3  8C7 + 5C4  8C6 + 5C5  8C5
= 80 + 140 + 56
= 276
31. A paper on mathematics consists of twelve questions divided into three parts. A, B and C, each
containing four questions. In how many ways can an examinee answer five questions, selecting at
least one from each part?
Ans (624)
Sol: Here, selection can be done as
COMBINATORICS 31

Total number of ways

= 3 ( 4 C1  4C1  4C3 ) + 3 ( 4 C2  4C2  4C1 )
= 192 + 432
= 624
32. A woman has 11 close friends. Find the number of ways in which she can invite 5 of them to dinner,
if two particular of them are not on speaking terms and will not attend together.
Ans: (378)
Sol: Either these two will come together or one of them

⸫ Number of ways
= 9C5 + 9C4  2C1
= 126 + 252
= 378
33. A rack has 5 different pairs of shoes. Find the number of ways in which 4 shoes can be chosen from it
so that there will be no complete pair.
Ans: (80)
Sol: Given 5 pair of shoes

Thus if take selection from left column then have to have corresponding shoes pair of right
⸫ Selection can be done as
COMBINATORICS 32

= 2 ( 5 C4 ) + 2 ( 5 C3  2C1 ) + 5C2  3C2

= 10 + 40 + 30
= 80
(M2) 5C4⨯24 = 80
34. Everybody in a room shakes hands with everybody else. The total number of handshakes is 66. Find
the total number of persons in the room.
Ans (12)
Sol: As we require two different person for a handshake
Let n be total person
⸫ Number of handshake = nC2
 nC2 = 66
n ( n − 1)
 = 66
2
 n ( n − 1) = 132
 n = 12
35. Three ladies have each brought a child for admission to a school. The head of the school wishes to
interview six people one by one, taking care that no child is interviewed before his/her mother. In
how many different ways can the interviews be arranged?
Ans. 90
6
Sol. C2 ⨯4C2 ⨯2C2 = 90
36. There are 5 different physics, 3 different chemistry and 4 different math books. In how many ways
books can be selected:
(a) If at least one book is selected.
(b) If at least one book is selected from each subject.
(c) If at least one and at most two books are selected from each subject.
Ans. (a) 212 – 1, (b) (25 – 1)(23 – 1)(24 – 1), (c) 900
Sol. (a) 212 – 1
(b) (25 – 1)(23 – 1)(24 – 1)
(c) (5C1 + 5C2)(3C1 + 3C2)(4C1 + 4C2) = 900
37. The interior angles of a regular polygon measure 150° each. Find the number of diagonals of the
polygon.
Sol: Let n be the number of sides of a polygon
COMBINATORICS 33


( n − 2 )180 = 150
n
 ( n − 2 ) 6 = 5n
 6n − 5n = 12
 n = 12
Number of diagonal = 12C2 − 12
= 66 − 12 = 54
38. 18 points are indicated on the perimeter of a triangle ABC (see figure). How many triangles are there
with vertices at these points?

Ans: (711)
Sol: There are total 18 points
Out of which 7, 7, 7 are respective collinear points on sides
⸫ Total number of triangles

= 18C3 − 3 ( 7 C3 )
= 711
39. Consider 9 points out of which 4 are collinear. Joining these points how many
(a) lines will be made (b) triangles will be made
(c) Quadrilaterals will be made (d) Pentagons will be made
Sol: (a) Given out of 9 points, 5 are non-collinear and 4 are collinear
⸫ Number of lines = 9C2 − 4C2 + 1
= 36 − 6 + 1 = 31
(b) Triangles can be made
= 5C3 + 5C2  4C1 + 5C1  4C2
= 10 + 40 + 30
= 80
(c) quadrilateral can be made
COMBINATORICS 34

= 5C4 + 5C3  4C1 + 5C2  4C2

= 5 + 40 + 60
= 105
(d) Pentagons can be made
= 5C5 + 5C4  4C1 + 5C3  4C2
= 1 + 20 + 60
= 81
40. Triangles are formed joining the marked points as vertices, when
(i) A is excluded &
(ii) A is included
Find ratio of number of triangles.

Ans: (7:9)
Sol: (i) when A is excluded then
Number of triangles
= 9C3 − 4C3 − 5C3
= 84 − 4 − 10
= 70
(ii) when A is included, then
Number of triangles
= 10C3 − 5C3 − 6C3
= 90
70
⸫ ratio = = 7:9
90
41. How many squares & rectangles are there in 8 × 8 chessboard
Ans: (204)
Sol: In a chess board there are 9 vertical lines and 9 horizontal lines
COMBINATORICS 35

⸫ Number of rectangles = 9C2  9C2 = 1296

For squares, we have to take lines at equal distance

Means 1-2, 2-3, 3-4, …. , 8-9 (8 horizontal and 8 vertical)
or 1-3, 2-4, …., 7-9 (7 horizontal and 7 vertical)
and so on
⸫ Number of squares
= 82 + 7 2 + 62 + ... + 22 + 12
8 ( 8 + 1)(16 + 1)
=
6
= 204
42. There are n concurrent lines and another line parallel to one of them. The number of different
triangles that will be formed by the (n + 1) lines, is
(n − 1)(n − 2)
Ans.
2
Sol. In this case, one side will be the parallel line which is non-concurrent.
The other parallel line cannot form any triangle.
So, the remaining two sides can be chosen in n-1C2 ways
(n − 1)(n − 2)
=
2
43. In how many ways we can pick 5 letters out of ARRANGEMENT
Sol: (a) Given, 2A, 2R, 2N, 2E, 1M, 1T, 1G
Different 5 letter combination can be
(i) 2 alike, 2 alike, 1 different = 4C2  5C1
= 6  5 = 30
(ii) 2 alike, 3 different = 4C1  6C3
= 4  20 = 80
(iii) All different = 7C5 = 21
⸫ total number of ways = 30 + 80 + 21 = 131
44. The total number of selections of fruit which can be made from 3 bananas, 4 apples and 2 oranges is
Ans: 60
Sol: Total number of selection
= (3 + 1)(4 + 1)(2 + 1)
COMBINATORICS 36

=4×5×3
= 60

Arrangement and Selection

45. Find the number of ways in which 4 boys and 2 girls (all are of different heights) can be arranged in a
line so that boys as well as girls among themselves are in decreasing order of height (from left to
right).
Ans. 15
6
Sol. C2⨯1⨯1 = 15
46. (a) Out of seven consonants and four vowels, the number of words of six letters, formed by taking
four consonants and two vowels is (Assume that each ordered group of letter is a word):
(b) Find the number of permutations of the word “AUROBIND” in which vowels appear in an
alphabetical order.
(c) Find the number of permutations of the word “AUROBIND” in which no two vowels come
together.
Sol: (a) Six letters words containing 4 consonants out of given 7 consonants and 2 vowels out of given 4
vowels
= 7C4  4C2  6!
= 151200
8!
(b) Arrangements in which vowels appear in alphabetical order =
4!
(c) 5C4 4!4!

47. Find the number of ways in which letters of the word VALEDICTORY be arranged so that the
vowels may never be separated.
Ans: (967680)
Sol: Given, V, L, D, C, T, R, Y, A, E, I, O
Keeping vowels together
Number of different words = 8! × 4! = 967680
48. Four visitors A, B, C & D arrive at a town which has 5 hotels. In how many ways can they disperse
themselves among 5 hotels, if 4 hotels are used to accommodate them.
Ans (120)
Sol: Out of 5 hotels only 4 are used to accommodate
COMBINATORICS 37

⸫ Number of ways = 5C4 × 4!

= 5 × 24 = 120 ways
49. Number of six digit numbers which have 3 digits even and 3 digits odd, if each is to be used atmost
once is ..............
Ans (64800)
Sol: Here, we have 5 odd digits and 5 even digits which includes 0 also which can’t be in the first position
Total such number
= 5C3  5C3  6!− 5C3  4C2  5!
= 72000 − 7200
= 64800
50. If m denotes the number of 5 digit numbers if each successive digits are in their descending order of
magnitude and n is the corresponding figure, when the digits are in their ascending order of
magnitude then (m – n) has the value
Ans: ( 9 C5 )

Sol: Here, m denotes 5 digit number in descending order = 10C5

n denotes 5 digit number in ascending order = 9C5
 m − n = 10C5 − 9C5 = 9C5
51. (a) If the letters of the word “VARUN” are written in all possible ways and then are arranged as in a
dictionary, then the rank of the word VARUN is
(b) The letters of the word RANDOM are written in all possible orders and these words are written
out as in a dictionary then the rank of the word RANDOM is
Sol: (a) Arranging letters in alphabetical order
A, N, R, U, V

Rank of Varun = 4 ( 4!) + 2 + 1 + 1

COMBINATORICS 38

= 96 + 4 = 100
(b) Arranging letters of RANDOM in alphabetical order, we get
A, D, M, N, O, R
Thus before words starting from ‘R’
We will have 5(5!) words
Now,

⸫ Total words or rank of Random

= 5 ( 5!) + 2 ( 3!) + 2
= 600 + 12 + 2
= 614

Arrangement of Alike Objects

52. The total number of arrangements which can be made out of the letters of the word ‘Algebra’, without
altering the relative position of vowels and consonants is
Sol: Here, without altering the relative position means, vowels will arrange where vowels are there and
consonants will arrange where consonants are there
4!3!
Total number of ways =
2!
53. The total number of ways of arranging the letters AAAA BBB CC D E F in a row such that letters C
are separated from one another is
Sol: Here,
 A  A  A  A  B B B D E  F
If C is arranged in these gaps then they are not together
⸫ Number of ways
10!
= 11C2 
4!3!
= 1386000
COMBINATORICS 39

54. The number 2006 is made up of exactly two zeros and two other digits whose sum is 8. The number
of 4 digit numbers with these properties (including 2006) is :
Ans. 21
Sol. let the other two digits a and b.
a+b=8
(1,7), (2,6), (3,5), (4,4)
Number of digits = 3×2×3 + 3 = 21

Divisor, Sum of Divisors & Exponent of p in n!

55. For the number 34  52  73 , find
(a) Number of divisors
(b) Number of even divisors
(c) Number of divisors which are multiple of 21
(d) Sum of all the divisors
Sol: (a) Given, 34  52  73
Number of divisors = (4 +1) (2 + 1) (3 + 1)
= 5 × 3 × 4 = 60
(b) Number of even divisors = 0 (as no even digit is there)
(c) Number of divisors which are multiple of 21
= ( 4 )( 2 + 1)( 3)
= 4  3 3
= 36
(d) Sum of all divisors
 35 − 1  53 − 1  7 4 − 1 
=   
 3 − 1  5 − 1  7 − 1 

=
( 242 )(124 )( 2400 )
2 46
= 1500400
56. Find exponent of
(a) 3 in 100!
(b) 10 in 100!
(c) Power of 5 in 30C12
COMBINATORICS 40

Sol: (a) Exponent of 3 in 100!

100  100  100  100  100 
= + 2 + 3 + 4 + 5 + .....
 3   3   3   3   3 
= 33 + 11 + 3 + 1 + 0
= 48
(b) Exponent of 10 in 100!
100  100  100 
= + + + ....
 10   10   10 
2 3

= 10 + 1 + 0
= 11
30 !
(c) 30C12 =
18!12 !
 30   30 
 5  +  25  = 7

18  12 
 5  = 3,  5  = 2

Exponent of 5 = 7-3-2=2
57. (a) In how many ways the number 7056 can be resolved as a product of 2 factors.
(b) Find the number of ways in which the number 300300 can be split into 2 factors which are
relatively prime.
Ans. (a) 23 (b) 32
Sol. (a) 7056 = 24 .32 .73
5 3 3 +1
= 23
2
(b) 300300 = 22 .52 .3.11.13.7
There are 6 primes.
Ways = 26 = 32
58. The number of odd proper divisors of 3p . 6m . 21n is :
Ans. (p + m + n + 1) (n + 1) – 1
Sol. Number given
=3p 6m21n
= 3p . 2m . 3m . 3n . 7n
= 2m . 3(p+m+n) . 7n
COMBINATORICS 41

As we have to exclude even divisors, we will consider only 3 and 7.

So,
Number of proper divisors (excluding 1)
= (p + m + n + l) (n + l)–1

De arrangement
59. In how many ways 6 letters can be placed in 6 envelopes such that
(a) No letter is placed in its corresponding envelope.
(b) At least 4 letters are placed in correct envelopes.
(c) At most 3 letters are placed in wrong envelopes
Sol. (a) Using dearrangernent theorem.
Number of ways to place 6 letters in 6 envelopes such that all are placed in wrong envelopes.
 1 1 1 1
6 1 − + − + ... 
 1 2 3 6

= 265
(b) Number of ways to place letters such that at least 4 letters are placed in correct envelopes = 4
letters are placed in correct envelopes and 2 in wrong + 5 letters are placed in correct envelopes and 1
in wrong + All 6 letters are placed in correct envelopes = 6C4  1 + 0 (not possible to place 1 in wrong
65
envelope) + 1 = + 1 = 16
2
(c) Number of ways to place 6 letters in 6 envelopes such that at most 3 letters are placed in wrong
envelopes = 0letter is wrong envelope and 6 in correct + 1 letter in wrong envelope and 5 in correct 2
letters in wrong envelopes and 4 are in correct + 3 letters in wrong envelopes and 3 in correct =1 + 0
(not possible to place 1 in wrong envelope)
 1 1 1
+ 6C4 1 + 6C3 3 1 − + − 
 1 2 3

6 5 6 5 4  3 − 3 
=1+ +  − 
2 6  2 3 

= 1 + 15 + 20  2 = 56.
COMBINATORICS 42

Distribution of item into Groups

60. Find the total number of ways in which n2 number of identical balls can be put in n numbered boxed
(1, 2, 3, ......... n) such that ith box contains at least i number of balls.
n2 + n − 2
2
Ans. Cn−1
Sol. B1 + B2 + …..+ Bn = n2 and Bi ≥ i
n(n + 1)
B1 + B2 + …..+ Bn = n 2 − and Bi ≥ 0
2
n2 − n
B1 + B2 + …..+ Bn = and Bi ≥ 0
2
n2 + n − 2
2
Ways = Cn−1
61. Find the number of ways in which n different prizes can be distributed amongst m (< n) persons if
each is entitled to receive at most n – 1 prizes.
Ans. mn – m
Sol. Each prize can go to any one of m persons i.e. has m options.
At most n - 1 prizes = All ways - Ways of distributing n prizes to a single person
All ways = mn
Ways of distributing n prizes to a single person = m
 Numbers of ways = mn - m
62. (a) The number of ways in which 12 balls can be divided between two friends, one receiving 8 and
the other 4, is
(b) The number of ways in which 52 cards can be divided into 4 sets, three of them having 17 cards
each and the fourth one having just one card
12! 52!
Ans: (a) (b)
(17!) 3!
3
8!4!

Sol: (a) Since, one can have 8 and other 4

12! 12!
Total number of ways =  2! =
8!4!2! 8!4!
(b) As any three of them will get 17 cards and remaining will get 1 card
52!
Total number of ways =
(17!)
3
3!
COMBINATORICS 43

63. Seven different coins are to be divided amongst three persons. If no two of the persons receive the
same number of coins but each receives at least one coin and none is left over, then the number of
ways in which the division may be made is:
Ans: (630)
Sol: If each receives at least 1 coin, then division can be done only as (1, 2, 4)
 7! 
Total number of ways = 3!  = 630
1!2!4!
64. Number of different ways in which 8 different books can be distributed among 3 students, if each
student receive at least 2 books is ...............
Sol: If each receives at least two books then the division can be done as (2, 2, 4) or (3, 3, 2)
 8! 8! 
Total number of ways = 3!  +  = 2940
 ( 2!) 4!2! ( 3!) 2!2! 
2 2

65. The number of ordered triplets of positive integers which are solutions of the equation
x + y + z = 100 is
Ans (4851)
Sol: Given, x + y + z = 100, x  1, y  1, z  1
Let x = x + 1, y = y + 1, z = z + 1
 x + y + z = 97, x, y, z  0
⸫ Number of ordered pairs
= 97+3−1C3−1
= 99C2 = 4851
66. The total number of ways of selecting six coins out of 20 one rupee coins, 10 fifty paise coins and 7
twenty five paise coins is
Ans: (28)
Sol: Let x be 1 rupee coin, y be 50 paise coin and z be 25 paise coin
 x + y + z = 6; x, y, z  0
⸫ Number of ways
= 3+ 6−1C3−1
= 8 C2
= 28
67. Find number of integral solutions of:
COMBINATORICS 44

(a) x + y + z = 10 ; x  0, y  2, z  0
(b) x + y + z + w = 12 ; x  4, y  −2, z  −3
(c) 2 x + y + z = 10 ; x  2, y  0, z  0
(d) x + y + z = 12 ; 1  x  3, y  0, z  0
Sol: (a) Given, x + y + z = 10 ; x  0, y  2, z  0 or z  1
Let y = 2 + y & z = 1 + z
 x + y + z = 7; x, y, z  0
⸫ Number of solution
= 3+7 −1C3−1
= 9C2 = 36
(b) Given, x + y + z + w = 12 ; x  4, y  −2, z  −3
Let x = 4 + x, y = −2 + y, z = 3 + z
 x + y + z + w = 7; x, y, z, w  0
⸫ Total number of solution
= 4+ 7 −1C4−1
= 10C3
= 120
(c) Given, 2 x + y + z = 10 ; x  2, y  0, z  0
 y + z = 10 − 2 x
When x = 2, y + z = 6
Number of solutions = 7
When x = 3, y + z = 4
Number of solutions = 5
When x = 4, y + z = 2
Number of solutions = 3
When x = 5, y + z = 0
Number of solutions = 1
Total number of solutions = 7 + 5 + 3 + 1 = 16
(d) Given, x + y + z = 12 ; 1  x  3, y  0, z  0
COMBINATORICS 45

x can have values 1, 2, or 3

When x = 1, y + z = 11
Number of solutions = 12
When x = 2, y + z = 10
Number of solutions = 11
When x = 3, y + z = 9
Number of solutions = 10
⸫ Total number of solutions = 12 + 11 + 10 = 33
68. In how many ways 5 fruits can be selected out of unlimited identical bananas, identical apples &
identical oranges.
Sol: Let banana be B , Apples be A and Oranges be O
 B + A + O = 5; B, A, O  0
Number of ways
= 3+5−1C3−1
= 7 C2
= 21
69. Find number of non-negative integral solutions of: x + y + z  5
Ans: (56)
Sol: Given, x + y + z  5
It means x + y + z can take values 0, 1, 2, 3, 4 or 5
⸫ Number of non-negative integral solution are
= 3+5−1C3−1 + 3+4−1C3−1 + 3+3−1C3−1 + 3+2−1C3−1 + 3+1−1C3−1 + 3−1C3−1

= 7 C2 + 6C2 + 5C2 + 4C2 + 3C2 + 2C2

= 21 + 15 + 10 + 6 + 3 + 1
= 56
70. Find the number of positive integer solutions of x + y + z = 10, where x, y, z are unequal
Ans: (24)
Sol: x, y, z, these are (1, 2, 7), (3, 6, 1), (1, 4, 5), (2, 3, 5)
Total = 3! 4 = 24 = 20 + 4
71. There are three piles of identical red, blue and green balls each pile contains at least 10 balls. The
number of ways of selecting 10 balls if twice as many red balls as green balls are to be selected is
COMBINATORICS 46

Ans: (4)
Sol: Let the number of green balls be x.
Then the number of red balls is 2x.
Let the number of blue balls be y
Then,
x + 2 y + y = 10
 3 x + y = 10
 y = 10 − 3 x
Clearly, x can take values 0, 1, 2, 3
The corresponding values of y are 10, 7, 4 and 1.
Thus, the possibilities are (0, 10, 0), (2, 7, 1), (4, 4, 2) and (6, 1, 3), where (r, b, g) denotes the
number of red, blue, green balls
72. The number of ways in which 5 identical balls can be kept in 10 identical boxes, if not more than one
can go into a box, is
Ans: (1)
Sol: One way
73. 5 balls are to be placed in 3 boxes. Each box can hold all the 5 balls. Number of ways in which the
balls can be placed so that no box remains empty, if :
(a) balls are identical but boxes are different
(b) balls are different but boxes are identical
(c) balls as well as boxes are identical
(d) balls as well as boxes are identical but boxes are kept in a row
Sol. (a) x1 + x2 + x3 = 5
xi  1
No. of solutions = 5-3+2C2
= 4 C2 = 6
(b) As boxes are identical
Case I : (3, 1, 1) distribution 5C3 = 10 ways
Case II : (2, 2, 1) distribution
 (5C2  3C2  1)/2 (for boxes)
= 15 ways
Total 25 ways
COMBINATORICS 47

(c) Balls and Boxes are identical

3 balls in 3 boxes → 1 way
Remaining 2 balls in 3 boxes → 2 ways (2, 0) and (1, 1)
Total = 2 ways
(d) Box Box Box
1 1 3
3 1 1
1 3 1
1 1 3
2 2 1
1 2 2
2 1 2
6 ways

Circular Arrangement
74. There are 16 men sitting on a round table. Find the number of ways to select 7 men such that no two
are consecutive.
Ans. 8
C6 16 / 7

Sol. Number of ways to select one man = 16C1

⇒ Adjacent men of that man can’t come.

To select 6 more from remaining 13 = 8C6
Each selection repeated 7 times.
16
C1 8C6
Ways =
7
75. How many garlands of 6 flowers of different colours be made out of 10 flowers of different colors?
Ans: (12600)
Sol: Given, 10 flowers and garland of 6 flowers has to be prepared
Number of ways
COMBINATORICS 48

= 10C6 .
( 6 − 1)!
2
5!
= 10C6
2
= 12600
76. In how many ways a team of 11 cricket players may sit on a round table so that captain, vice captain
& wicket keeper are together.
Ans: (241920)
Sol: We want captain, vice-captain and wicket keeper to be together
Thus assuming them as 1 and arrange with remaining 8 players
Total number of ways
= ( 9 − 1)! 3!
= 8! 3!
= 241920
77. Find the number of ways in which seven persons can be arranged at a round table if two particular
persons may not sit together.
Ans: (480)
Sol: Number of ways in which 7 persons can be arranged at a round table if two particular person may
not sit together
= Total arrangement – when two particular person are together
= ( 7 − 1) !− ( 6 − 1)!2!
= 6!− 5!2
= 720 − 240
= 480
COMBINATORICS 49

LEVEL II
69. Find the number of times the digit 5 will be written when listing integers from 1 to 1000.
Ans. 300
Sol. One digit occurrence = 1
Occurrence in 2 digit numbers
Ten's place (50 to 59)= 10
9
Unit's place (15, 25...95) =
19
Occurrence in 3 digit numbers:
Hundreds place (500 to 599) = 100
Tens’s Place - (150, 150 … 159
250, 251 … 259
   = 90
950, 951 … 959
 105, 115, 125 ... 195
Unit’s Place - 
 205, 215, 225 ... 295
   = 90
905, 915, 925 ... 995) 280

 Number of times digit 5 will be written

= 280 + 19 + 1
= 300
70. A seven digit number divisible by 9 is to be formed by using 7 out of numbers {1, 2, 3, 4, 5, 6, 7, 8,
9}. Find the number of ways in which this can be done.
Sol. Sum of all digits = 45
For a number to be divisible by 9, sum of all digits should be divisible by 9.
 The sum of digits of the required 7 digit numbers = 36.
Less than 36 is not possible.
So, we have to exclude two digits whose sum is, 9 i.e. (1, 8), (2, 7), (3, 6), (4, 5) = 4 ways
The 7 digits can be arranged in 7! ways
Number of ways = 47!
COMBINATORICS 50

71. (a) A 5 digit number divisible by 3 is to be formed using the numerals 0, 1, 2, 3, 4 & 5 without
repetition. Find the total number of ways.
(b) How many five digits numbers divisible by 3 can be formed using the digits 0, 1, 2, 3, 4, 7 and
8
if each digit is to be used at most once?
Ans. (a) 216, (b) 744
Sol : (a) For divisibility of 3, sum of all digits should be divisible by 3
Here, 1, 2, 3, 4, 5 or 0, 1, 2, 4, 5 these two cases are only possible
Case I: Total five digit number = 5! = 120
Case II: Number which don’t start with 0
= 5!− 4! = 120 − 24 = 96
⸫ Total number = 120 + 96 = 216
(b) Minimum sum of 5 digits = 10
Maximum sum of 5 digits = 24
Sum of 7 digits = 25
We have to remove 2 digits such that remaining sum divisible by 3.
Pairs are (0,1), (1,3),(0,4), (0,7)(3,4)(2,8)(3,7)
Number of ways = 3⨯5! + 4⨯4⨯4! = 360 + 384 = 744
72. A committee of 5 is to be chosen from a group of 9 people. Find the number of ways in which it
can be formed if two particular persons either serve together or not at all and two other particular
persons refuse to serve with each other.
Ans: (41)
Sol: Out of 9, two will serve together, and other two will not come if one of them is there

Total number of ways

= 5C5 + 5C3  2C2 + 5C2  2C2  2C4 + 5C4  2C1
= 1 + 10 + 20 + 10
= 41
COMBINATORICS 51

73. In a certain algebra exercise book there are 4 examples on arithmetical progressions, 5 examples of
permutation – combination and 6 examples on binomial theorem. Find the number of ways a teacher
can select for his pupils atleast one but not more than 2 examples from each of these sets.
Ans: (3150)
Sol: Here solution can be done as

⸫ Total number of ways

= 4C1  5C1  6C1 + 4C1  5C1  6C2 + 4C1  5C2  6C1 + 4C2  5C1  6C1
+ 4C2  5C2  6C1 + 4C1  5C2  6C2 + 4C2  5C1  6C2 + 4C2  5C2  6C2
= 120 + 300 + 240 + 180 + 360 + 600 + 450 + 900 = 3150
(M2) (4C1 + 4C2)(5C1 + 5C2)(6C1 + 6C2) = 10⨯15⨯21 = 3150
74. How many ordered pairs (P, Q) of subsets of {a, b, c, d, e} can be made such that:
(a) P  Q = 

(b) P  Q = a

(c) P  Q Contains exactly 2 elements

Sol: Here every element (let say x) has four ways in which they can be arranged
xP and x Q
xP and x Q
xP and x Q
xP and x Q
(a) For P  Q = 
Then every element has 3 ways
⸫ Total number of ways = 35 = 243
(b) P  Q = a

So, here element ‘a’ has only one way and other four has to go in other three ways
COMBINATORICS 52

⸫ Total number of ways = 34 = 81

(c) For exactly 2 elements in common, number of ways
= 5C2  33
= 10  27
= 270
75. A seven digit number with distinct digits is in form of abcdefg (g, f, e, etc. are digits at units, tens,
hundred place etc.) where a < b < c < d > e > f > g. Find the number of such numbers.
Ans. Case I if zero not included
Select seven digits = 9C7 ways
Select largest digit (= d) = 1 way
Select 3 digits from remaining 6 for abc = 6C3
These 3 digits allocated to a, b, c in one way only = 1
Remaining 3 selected for efg = 3C3
These 3 digits allocated to e, f, g in one way only = 1
Number of ways = 9C7⨯1⨯6C3⨯1⨯3C3⨯1 = 36⨯20 = 720
Case II if zero included
Zero must be the digit g.
Number of ways = 9C6⨯1⨯5C3⨯2C2 = 84⨯10 = 840
Total = 1560
76. The number of ways of arranging ‘m’ number out of 1, 2, 3, . . . . ., n so that maximum is (n – 2)
and minimum is 2 (repetitions of numbers is allowed) such that maximum and minimum both occur
exactly once, (n > 5, m > 3) is
(a) n – 3Cm – 2 (b) mC2 (n – 3)m – 2
(c) m (m – 1) (n – 5)m – 2 (d) nC2 . nCm
Ans. c
Sol. m numbers out of which one is 2 and one is n – 2
we have to choose m - 2 numbers from 3, 4, 5…n - 3 i.e. n - 5 numbers.
So, number of ways of selecting m numbers = (n – 5)m-2
Arranging 2 and n - 2 can be done in m(m - 1) ways
Thus, number of ways of arranging the numbers = m(m -1)(n - 5)m – 2
77. Total number of ways of selecting two numbers from the set {1, 2, 3, 4, …., 3n} so that their sum is
divisible by 3 is equal to:
COMBINATORICS 53

Sol: Given numbers can be rearranged as

1, 4, 7.....,3n − 2 → 3 − 2 type
2,5,8....,3n − 1 → 3 − 1 type
3, 6,9....,3n → 3 type
That means we must take two numbers from last row or one number each from first and second row
Total ways = n C2 + nC1. nC1

n ( n − 1)
= + n2
2
3n 2 − n
=
2
78. There are m points on a straight line AB and n points on the line AC none of them being the point
A. Triangles are formed with these points as vertices, when
(i) A is excluded (ii) A is included
The ratio of number of triangle in the two cases is:
m+n−2
Ans: ( )]
m+n
Sol: Generalizing, given m points on AB and n points on AC (excluding A)
(i) Number of triangles when A is excluded
= m+ nC3 − mC3 − nC3
= m+n−2
(ii) Number of triangles when A is included
= m+ n +1C3 − m+1C3 − n +1C3
= m+n
m+n−2
⸫ ratio =
m+n
79. In a plane there are 6 lines, no two of which are parallel & no three are concurrent. How many
triangles can be formed with their points of intersection as vertices
Ans: (395)
Sol: Here, 6 lines will give point of intersection = 6C2 = 15
Also, all other 5 lines intersect collinearly on one line such that those 5 points are collinear
⸫ Number of triangles
COMBINATORICS 54

= 15C3 − 6 ( 5 C3 )
= 455 − 6 (10 )
= 455 − 60
= 395
80. The number of ways in which we can choose 3 squares of unit area on a chess board such that one
of the squares has its two sides common to other two squares
Ans. 292
Sol. Total number of square having unit area on chess board = 88 =64
1 1'
2 2'
3 3'
For square at 1 position, No of ways of chasing 3 square = 1
For square at 1’ position, No of ways of choosing 3 square = 3
For square at 2 position, No of ways of choosing 3 square = 3
At position 2, Number of ways of choosing 3 square = 6,
So, Total number of ways of chessing 3 square

=
( 2 1 + 6  3)  2 +
(3  2 + 6  6 )  6
upper and lower row middle row

= 40 + ( 42 )  6

= 292
81. Given 11 points, of which 5 lies on one circle, other than these 5, no 4 lie on one circle. Then the
maximum number of circles that can be drawn so that each contains atleast three of the given points
is:
Ans. 156
Sol. Given that, In 11 points, 5 lie on one circle, other than these, no 4 lie on one circle. As we know,
from 3 points one circle will be formed.
So,
i) Selecting 2 points from 5 lies on one circle and 1 from other circle. = 5C2 x 6C1
= 60
ii) Selecting 1 points from 5 lie on one circle and 2 from other circle = 5C1 x 6C2
= 75
COMBINATORICS 55

iii) Selecting all 3 points from other 6 points = 6C3

iv) One circle is already drawn from 5 points
Total number of circles = 60 + 75 + 20 + 1=156
82. Two classrooms A and B having capacity of 25 and (n – 25) seats respectively. An denotes the
number of possible seating arrangements of room ‘A’, when ‘n’ students are to be seated in these
rooms, starting from room ‘A’ which is to be filled up full to its capacity.
If An – An – 1 = 25 ! (49C25) then ‘n’ equals
Ans. 50
Sol We can clearly assume n > 25
An = nC25!
[Selecting 25 students from n students and arranging them in 25 positions]
A n = n C25 .25!
We have
A n − A n −1 = 25! 49C25
n
C25 .25!− n −1C25 .25! = 25! 49C25
n
C25 − n −1C25 = 49C25

83. In how many ways it is possible to select six letters, including at least one vowel from the letters of
the word “F L A B E L L I F O R M”. (It is a picnic spot in U. S. A.)
COMBINATORICS 56

Ans. 296

84. The total number of permutations of 4 letters that can be made out of the letters of the word
EXAMINATION is
Sol: Given, 2A, 2I, 2N, 1E, 1X, 1M, 1T, 1O
Different permutation are
4!
(i) 2 alike, 2 alike = 3C2  = 18
2!
4!
(ii) 2 alike, 2 different = 3C1  7 C2  = 756
2!
(iii) all different = 8C4  4! = 1680

Total words = 18 + 756 + 1680 = 2454

85. Number of ways in which letters of the word ENGINEER can be arranged :
(a) so that the word starts with E but does not end with N.
(b) so that the word neither starts with E nor ends with N.
(c) so that vowels occur in alphabetical order.
COMBINATORICS 57

(d) so that no two alike letters are together.

Ans. 900, 1620, 840, 960
7! 6!
Sol. (a) − = 900
2!2! 2!
(b) Total – words either start with E or end with N
8!  7! 7! 6! 
1. − + − 
3!2!  2!2! 3! 2! 

 14 7 7 1 
= 6! − − + 
 3 4 6 2
 112 − 42 − 28 + 12 
= 6! 
 24 
 112 − 42 − 28 + 12  720  9
= 6! =
 24  4
= 1620
4!
(c) 8C4  1 = 840
2!
(d) No alike letter together = No E together – (No E together and N together)
5! 5
2. = 6C3 − C3 4!
2!
3. = 1200-240
=960
86. The number of divisors of 23 . 33 . 53 . 75 of the form 4n + 1, n ∈ N is :
Ans. 47

87. A disarranged number from the set 1 – 9 is an arrangement of all these number so that all numbers
take up its unusual position. (e.g. 1 is in any place other than the first position, 2 is in any place other than
COMBINATORICS 58

the second position ......... all the way to 9). Number of ways in which at least six number stake up their
usual positions, is
Ans. 205

88. How many ten digits whole number satisfy the following property they have 2 and 5 as digits, and
there are no consecutive 2's in the number (i.e. any two 2's are separated by at least one 5).
Ans. 143
Sol. One 2, Two 2’s, Three 2’s,…., , Five 2’s
One 2 cases = 10
Two 2’s cases = 9C2
Three 2’s cases = 8C3
Four 2’s cases = 7C4
Five 2’s cases = 6C5
Total = 10 + 36 + 56 + 35 + 6 = 143
89. How many 4 digit numbers are there which contains not more than 2 different digits?
Ans. 576
Sol. aaaa type numbers = 9
aabb type numbers =Total – starting with zero
COMBINATORICS 59

4! 9 3!
= 10C2 − C1 = 270 − 27 = 243
2!2! 2!
abbb type numbers = Total – starting with zero
4! 9  3! 
= 10C2 2C1 − C1  + 1 = 360 − 36 = 324
3!  2! 
Total = 576
90. There are counters available in 7 different colours. Counters are all alike except for the colour and
they are at least ten of each colour. Find the number of ways in which an arrangement of 10 counters can
be made. How many of these will have counters of each colour.
Ans. 710, (49/6)10!
Sol. (i) 7.7.……7 = 710
(ii) Different combinations are:
(a) 2, 2, 2, 1, 1, 1, 1
10! 35
2. 7C3 = 10!
2 !2 !2 ! 8
(b) 3, 2, 1, 1, 1, 1, 1
10! 7
7
C2 2C1 = 10!
3!2! 2
(c) 4, 1, 1, 1, 1, 1, 1
10! 7
7
C1 = 10!
4! 24
35 7 7 105 + 84 + 7
Total = 10!+ 10!+ 10! = 10!
8 2 24 24
196 49
= 10 ! = 1 0 !
24 6
91. The number of seven digit integers, with sum of the digits equal to 10 and formed by using the
digits 1,2 and 3 only, is
Ans. 77
Sol. There are two possible cases
Case I Five 1’s, one 2’s, one 3’s
Number of numbers =7!/ 5!= 42
COMBINATORICS 60

Case II Four 1’s, three 2’s

Number of numbers =7!/ 4!3! = 35
 Total Number of numbers = 42 +35 = 77
92. Let the product of all the divisors of 1440 be P. If P is divisible by 24x, then the maximum value of
x is
Ans: (30)
Sol: 1440 = 25.32.51
Number of divisors = ( 5 + 1) . ( 2 + 1) . (1 + 1) = 36

Product of divisors = 1.2.3…480.720.1440.

Here all the 36 divisors ae written in the increasing order
They can be clubbed into 18 pairs, as shown below
(1.1440).(2.720).(3.480)…..etc

⸫ Product of divisors = (1440 ) = 290.336.518

18

= ( 23.3) .36.518 = 2430.36.518 which is divisible by 24x

30

Maximum value of x = 30
93. The number of three digit numbers of the form xyz such that x < y and z  y is
Ans (276)
Sol: If zero is included it will be at 9 C2 numbers

 x, y, z all diff  9
C3  21

If zero is excluded  x = z  y  9
C2
 x y=z  9
C2 numbers

Total number of ways = 276

(r − 1) = 276
9
2
Alternate method: y can be from 2 to 9 so total number of ways =
r =2

94. Consider the network of equally spaced parallel lines(6 horizontal and 9 vertical) shown in the
figure. All small squares are of the same size. A shortest route from A to C is defines as a route
consisting 8 horizontal steps and 5 vertical steps.
COMBINATORICS 61

(a). The number of shortest routes through the junction P is:

(b) The number of shortest routes which go following street PQ must be
(c) The number of shortest routes which passes through junction P and R
Ans. 560, 350, 240
Sol. (a) 5C2⨯8C3 = 560
(b) 5C2⨯7C3 = 350
(c) 5C2⨯4C1⨯4C2 = 240
95. The minimum marks required for clearing a certain screening paper is 210 out of 300. The
screening paper consists of ‘3’ sections each of Physics, Chemistry, and Maths. Each section has
100 as maximum marks. Assuming there is no negative marking and marks obtained in each
section are integers, find the number of ways in which a student can qualify the examination is
(Assuming no cut–off limit).
93
Ans. C3
Sol. Let x1 be the marks lost in physics, x2 be the marks lost in chemistry and x3 be the marks lost in
maths so,
x1 + x2 + x3  90
So, for integral solution
x1 + x2 + x3 = 90
no of ways = 92C2
x1 + x2 + x3 = 89
no of ways = 91C2
.
.
.
x1 + x2 + x3 = 0
COMBINATORICS 62

no of ways = 2C2
so, total number of ways = 2C2 + 3C2 + 4C2 +…..+92C2 = 93C3
96. 10 identical balls are to be distributed in 5 different boxes kept in a row and labled A, B, C, D and
E. Find the number of ways in which the balls can be distributed in the boxes if no two adjacent
boxes remain empty
Ans. 771
Sol. Case I : No box vacant
x1 + x2 + x3 + x4 + x5 = 5
[Assuming 5 balls went into 5 boxes]
5+5-1
C4 = 9C4 = 126
Case II : One box vacant
x1 + x2 + x3 + x4 = 6
6+4-1
C3 

= 9C3  5 = 420
Case III: Two boxes vacant
x1 + x2 + x3 = 7 Boxes that can be vacant [AC, AD, AE, BD, BE, CE]
9
C2  6 = 216
Case III: Three boxes vacant
x1 + x2 = 8, Boxes that can be empty A,C,E
9
C1 = 9
Total ways = 126 + 420 + 216 + 9 = 771
97. Find how many three digit numbers, lying between 100 and 999 inclusive, have two and only two
cosecutive digits identical.
Sol. 162
Thee are two possible formats for three digit numbers to have two and only two consecutive digis
identical :
(i) aac where a  0 and c  a, or

(ii) abb where a  0and a  b

Thus the number of such integers is
9 x 9 + 9 x 9 = 162
COMBINATORICS 63

98. Let X = {1,2,3,…17}. Find the number of subsets Y of X with odd cardinalities.
Sol. 65536
The answer is

( ) + ( ) + ( ) + ....( ) = 2
17
1
17
3
17
5
17
17
16
= 65536

99. How many integers are there between 0 and 105 having the digit sum of equal to 8?
Sol. 495
Each integer can be written as x1x 2 x 3 x 4 x 5 where each xt = 0, 1, 2,…..9 with x1 + x2 + x3 + x4 + x5 =

8. The number of non -negative integer solutions to the above equation is 495. So there are 495
such integers.
100. Find the largest positive integer n such that n! ends with exactly 100 zeroes.
Sol. (409)
If n! ends with exactly 4100 zeroes, then in the prime factorization of n!, the prime factor 5 occurs
exactly 100 times (we need not worry about the prime factor 2 since it will occur more than 100
times). He number of times that 5 occurs in n! is given by
n   n   n 
 5  +  52  +  53  + ..

Also the factor 5 occurs 24 times in 100! Thus the answer is about 400 Now
 400   400   400 
 5  +  52  +  53  + .....80 + 16 + 3 = 99

It follows that 400! ends with exactly 99 zeros. Thus the answer is 409
101. Suppose 40 objects are placed along a circle at equal distances. In how many ways can 3
objects be chosen from among them so that no two of the three chosen objects are adjacent nor
diametrically opposite?
Sol: One can choose 3 objects out of 40 objects in 40 3 ways. Among theese choices all would be
together in 40 cases; exactly two will be together in 40 × 36 cases. Thus three objects can be chosen
such that no two adjacent in 40 3 - 40 - (40 × 36) ways. Among these,
furthrer, two objects will be diametrically opposite in 20 ways and the third would be on either
semicircle in a non adjacent portion in 40 - 6 = 34 ways. Thus required number is
COMBINATORICS 64

102. Five students A, B, C, D and E from a team to take part in a 5 leg relay competition. If A cannot
run the first leg and D cannot run the last leg, how many ways can we arrange them to run the relay
?
Sol. (78)
Total number of ways is
5! – 4! – 4! + 3! = 120 – 24 – 24 + 6 = 78
Alternatively, we consider the following cases
Case (i) A and ‘D do not run the first or last leg, In this case, the number of arrangements is 3 x 2 x
3! = 26
Case (ii) D does not run the first leg and A runs the last leg. In this case, number of ways is
3 x 3! = 18
Therefore, total number of ways = 36 + 24 + 18 = 78.
103. Suppose that each of n people knows exactly one piece of information, and all n pieces are
different. Every time person A phones person B, A tells B everything he known, while B tells A
nothing. What is the minimum of phones called between pairs of people needed for everyone to
know everything?
Sol. we claim that the minimum of calls needed is 2n–2. Let A be a particular person, the 2n–2 calls
made by A to each of the persons and vice versa will leave everybody informed. Thus at most 2n
–2 calls are needed.
Next we prove that we need at least 2n–2 calls. Suppose that there is a sequence of calls that
leaves everybody informed. Let B be the first person to be fully informed and that he receives his
last piece of information at the pth call. Then each of the remaining n–1 people must have placed
at least one call prior to p so that B can be fully informed. Also these people must received at least
one call after p since they were till not full informed at the pth call. Thus we need at least 2(n-1)
calls.
104. For each positive integer n, let an denote the number of n digit integers formed by some or all of
the digits 0,1,2 and 3 which contain neither a block of 12 nor a block of 21. Evaluate a9
Sol. 73368
For n ≥ 3, among the an such integers, let bn denote the number of those that end with1. By
symmetry the number of those that end with 2 is also equal to bn. Also the number of those that end
with 0 or 3 are both an–1. Thus
COMBINATORICS 65

a n = 2a n −1 + 2bn
Among the bn integers that end with 1, the number of those that end with 11 is bn–1 while the
number of those that end with 01 or 31 are both an-2. Thus
bn = bn–1 + 2an-2
Solving, we get a n = 3a n −1 + 2a n −2 .Since a1 = 3 and a 2 = 10 we get a 9 = 73368

105. As shown in the picture, the knight can move to any of the indicated squares of the 8 x 8
chessboard in 1 move. If the knight starts from the position shown, find the number of possible
landing positions after 20 consecutive moves

106. How many four digit numbers greater than 5000 can be formed from the digit 0, 1, 2, 3, 4, 5, 6, 7,
8, 9 if only the digit 4 may be repeated?
Sol. 2645

Let abcd represent the integer a 103 + b 102 + c 10 + d

Note that abcd > 5000 iff a ≥ 5 and b,c,d are not all 0, a must be a number in {5,6,7,8,9}. Suppose
that a is selected from {5,6,7,8,9}
If 4 is not repeated, then the number of ways to choose b,c,d is 9 x 8 x 7
If 4 appears exactly twice, then the number of ways to choose b,c,d is (3C2) x 8
If 4 apperts exactly three times, then the number of ways to choose b,c,d is 1
Hence the answer is
COMBINATORICS 66

5  ( 9  8  7 + 3 C 2  8 + 1) = 2645

107. There girls A,B and C, and nine boys are to be lined up in a row. Let n be the number of ways ths
can be done if B must lie between A and C, and A, B must be separated by exactly 4 boys.
Determine [n/7!]
Sol. 3024
Let f be the set of arrangemnts of there girls and boys the condition that A, B mut be separated by
exactly 4 boys. Form a block P with A,B at the two ends and exactly 4 boys between them . The
number of ways to form such a block P is.
9
2     4!
 4
Then we have
9
 = 2     4!  7!
 4
As we can consider such a block P as one item, and there are still 5 boys and one girl (i.e.C).
Note that in any arrangement in f,C is outside the block between A and B. In exactly half the
arrangements of f, B is between A and C. Hence
9
n =  / 2    4! 7!
 4
9
Hence the answer is    4! = 3024
 4
108. Determine the number of positive integer divisors of 99849999 that are not the divisors of 99849998
Sol. 99999
Note that 998 = 2 × 499, and 499 is a prime. Any divisor of 99849999 has the form d= 2a499b, where
a and b are positive integrs between 0 and 49999. This divisor d does not divide 99849998 only n two
cases wich are either a = 49999 or b = 49999. In the first case d can be 249999, 249999499, 249999492
,….249999 49949999. In the second case d can be 49949999, 499499992,4994999922,….49949999 249999. In
each case, there are 50000 possible values, but the number 249999 49949999 is counted twice. Thus the
total number of required divisors is 2 x 50000 – 1 = 99999.
109. Consider a 2008 x 2008 chess board. Let M be the smallest number of rectangles that can be drawn
on the chess board so that the sides of every cell of the board is contained in the sides of the one of
the rectangles. Find the value of M. (For example for the 2 x 3 chess board, the value of M is 3).
COMBINATORICS 67

Sol. The answer is M = 2009. All the horizontal sides can be covered by 1004 pieces of 1 x 2008
rectangles except the boundary of the chess board which can be covered by the boundary rectangle.
The remaining vertical sides can be covered by1004 pieces of 2008 x 1 rectangles. Thus M ≤ 2009.
Now supose that the chess borard has been covered by M rectangles in the desired way. Let a of the
rectangles have their top and bottom on the top and bottom of the board, b of the rectangles have
their top on the top of the board r of the rectangles have their bottom on the bottom of the board and
d of the rectangles have neither thir top nor bottom on the top or bottom of the board.
Since there are 2007 internal horizontal lines we have b + c + 2d ≥ 2007.Since ther are 2009 vertical
lines intersecting the top of theboard we hae 2a + 2b ≥ 2009 or a + b ≥ 1005. Sjmiliary a + c ≥ 1005.
Thus 2a + b + c ≥ 2010. Hence 2(a + b + c + d) ≥ 4017 i.e. M = a + b + c + d ≥ 2009
110. Determine the number of 8-digit positive integers such that after deleting any one digit, the
remaining 7-digit number is divisible by 7.
Ans. 64

111. In how many ways can a team of 6 horses be selected out of a stud of 16, so that there shall always
be 3 out of A B C A’ B’C’, but never A A’ , B B’ or C C’ together.
Ans. 960
10
Sol. C3⨯2C1⨯2C1⨯2C1 = 960
112. There are n straight lines in a plane, no 2 of which parallel, & no 3 pass through the same point.
Their point of intersection are joined. Show that the number of fresh lines thus introduced is n(n -
1)(n - 2)(n - 3)/8
Sol. No. of intersections = nC2 = n(n-1)/2
Every line intersect by remaining n-1 line therefore n-1 point are collinear
COMBINATORICS 68

n (n −1)
No. of fresh lines = 2
C2 − n n −1C2

n(n − 1)(n − 2)(n + 1) n(n − 1)(n − 2)

2. −
8 2
n(n − 1)(n − 2)(n − 3)
=
8
113. Prove that if each of m points in one straight line be joined to each of n in another by straight lines
terminated by the points, then excluding the given points, the lines will intersect
¼ mn(m – 1)(n –1) times.
Sol. Two point from each line give one intersection.
No. of intersection = mC2nC2
114. Find the number of words each consisting of 3 consonants & 3 vowels that can be formed from the
letters of the word “circumference”. In how many of these all ‘c’s will be together.
Ans. 22100, 52
Sol. cccrrmfn, iueee
cccrrmfn Iueee
3 same = 1C1 3 same = 1C1
2same 1 different = 2C1 x 4C1 2same 1 different = 1C1 x 2C1
3 different = 5C3 3 different = 3C3
 1C 2C  4C1 5  1C1 1C1  2C1 3 
Number of words = 6! 1 + 1 + C3  + + C3 
 3! 2!  3! 2! 
=22100
 1C1 1C1  2C1 3 
(ii) 4! + + C3 
 3! 2! 
=52
115. How many different ways can 15 Candy bars be distributed between Ram, Shyam, Ghanshyam and
Balram, if Ram can not have more than 5 candy bars and Shyam must have at least two. Assume all
Candy bars to be alike.
Ans. 440
Sol. a + b + c + d = 15 & a ≤ 5 & b ≥ 2
a + b + c + d = 13 & a ≤ 5 & b ≥ 0
Required ways = Total – (cases in which a≥6)
COMBINATORICS 69

a + b + c + d = 13 & a ≥ 6 & b ≥ 0
a+b+c+d=7&a≥0&b≥0
Required ways = 16C3 – 10C3 = 560 – 120 = 440
116. How many integers between 1000 and 9999 have exactly one pair of equal digit such as 4049 or
9902 but not 4449 or 4040?
Ans. 3888
Sol. Total – Starting with zero
4! 9  2 3! 
= 10C3 3C1 − C2  C1 + 3!
2!  2! 
= 4320 – 432 = 3888
117. In a box there are 10 balls, 4 red, 3 black, 2 white and 1 yellow. In how many ways can a child
select 4 balls out of these 10 balls ? (Assume that the balls of the same color are identical)

118. In a certain test, ai students gave wrong answers to at least i question, where i = 1, 2,...., k. No
student gave more that k wrong answers. Find the total number of wrong answer given.
Ans. a1 + a2 + a3 +…….+ ak
Sol. (a1 – a2)+2(a2 – a3)+3(a3 – a4)+…………….+ (k-1)(ak-1 – ak) + kak = a1 + a2 + a3 +…….+ ak
n2 !
119. Use permutation or otherwise, prove that is an integer, where n is a positive integer.
( n !)
n

Sol. Here, n2 objects are distributed in n groups, each group containing n objects.
COMBINATORICS 70

−n −2n −3 n
= n Cn .n
2 2 2 2
Cn .n Cn .n Cn ....n Cn

=
( n )! . ( n − n )! ... n ! = ( n )!
2 2 2

n !( n − n )! n !( n − 2n )! n !.1 ( n !)
2 2 n

 Integer (as number of arrangement has to be integer).

120. Number of positive integral solutions satisfying the equation (x1 + x2 + x3) (y1 + y2) = 77, is
Ans. 420
(x1 + x2 + x3) (y1 + y2) = 77
77 = 1  77 [This case not possible]
= 7  11
So, only possible cases are
(i) x1 + x2 + x3 = 7 and y1 + y2 = 11
(ii) x1 + x2 + x3 = 11 and y1 + y2 = 7
Case I:
x1 + x2 + x3 = 7 and y1 + y2 = 11
where xi, yi  1
Number of solution = 7-3+2C2  11-2+1C1
= 6C2  10C1
= 150
Case II:
x1 + x2 + x3 = 11 and y1 + y2 = 7
Number of solution = 11-3+2C2  7-2+1C1
= 10C2  6C1
45  6
= 270
Total solution = 420
121. In the figure, two 4–digit numbers are to be formed by filling the places with digits. The number of
different ways in which the places can be filled by digits so that the sum of the numbers formed is
also a 4–digit number and in no place the addition is with carrying is :
COMBINATORICS 71

Ans. 36 (55)3
Sol. 0 → 0 to 9 → 10 options
0 → 0 to 8 → 9 options
2 → 0 to 7 → 8 options
9→0 → 1 option
55 options

For every place, we have 55 options. For thousand's place, first digit cannot be zero.
So, we have 55 – 19 = 36 options
Total ways = (55)3  36
122. The number of different ways the letters of the word VECTOR can be placed in 8 boxes given
below such that no row remains empty is equal to:

Ans. 26 × 6!
Sol. VECTOR we have to till nodes so that no rows will be empty.
Total number of ways of arranging 6 letters in 8 boxes = 8C6  6!
Now, 1st row can’t be empty.
Number of ways in arranging words it any rows will be empty = 2  6!
So, required number of ways
= 8C6  6! - 2  6!
= 26  6!
123. The number of ways of choosing triplets (x, y, z) such that z ≥ max {x, y} and x, y, z ∈{1, 2, . . . . ,
n} is
Ans. n + 1C + n + 2 C3
3
COMBINATORICS 72

Sol. CASEI: z = x = y
No. of triplets = n
CASEII: Any two equal(z = x > y or z = y > x or z > x = y)
No. of triplets = 3 x nC2
CASEIII: All 3 different(z > x > y or z > y > x)
No. of triplets = 2 x nC3
Total = nC1 + 3 x nC2 + 2 x nC3 = n+1C3 + n+2C3.
124. Total number of positive integral solution of 15 < x1 + x2 + x3 ≤ 20 is equal to
Ans. 685
Sol. 15 < x1 + x2 + x3 ≤ 20
For positive integeral soluton 0 must be excluded
x1' = x1 − 1
x2' = x2 − 1
x3' = x3 − 1
So,
15  x1' = x2' + x3' + 3  20

12  x11 = x12 + x31  17

So, Number of positive integral solution
= 15C2 + 16C2 + 17C2 + 18C2 + 19C2
15 14 16 15 17 16 18 17 19 18
= + + + +
2 2 2 2 2
= 685
None of these
125. The number of ways in which we can choose 2 distinct integers from 1 to 100 such that difference
between them at most 10 is:
(a) 40C2 (b) 70C2 (c) 100C2 – 99C2 (d) None of these
Ans. d
Sol. Maximum ways of choosing 2 numbers = 100C2
For 1 I can choose from {2, 3 …11} = 10
For 2 I can choose from {1, 3, 4…12} = 11
For 10 I can choose from {1,2…9,11,12…20} = 19
COMBINATORICS 73

From 11 to 90 each number has 20 choices

From 91 to 100, each number has again 19, 18, 17…10
choices
(Refer to case of 1,2…10)
Therefore, total cases possible
= 80  20 +(19 +18+17...10)
= 1600 + 290
= 1890
But we have to consider (a, b) and (b, a) as same.
Thus, total ways = 945
126. Number of different words that can be formed using all the letters of the word “DEEPMALA” if
two vowels are together and the other two are also together but separated from the first two is :
(a) 960 (b) 1200 (c) 2160 (d) 1440
Ans. d
Sol. There are two groupings possible of vowels: (EE, AA) or (AE, AE).
Case I :
Groups AA, EE and 4 consonants.
Total cases possible = 6!
Now, cases when AA and EE are together
(Block AAEE or EEAA + 4 consonants)
= 2  5!
Thus, total faourable cases = 6! - 2 5!
= 480
Case II :
Groups AE, AE and 4 consonants
= 2 6!
Now, cases when AE, AE are together
(Block AEAE or AEEA or EAEA or EAAE)
+4 consonants = 4 5!
Thus, total favorable cases = 2 6!- 4 5!
COMBINATORICS 74

= 960
Thus total words = 480 + 960 = 1440
127. The number of permutation of the letters of the word HINDUSTAN such that neither the pattern
‘HIN’ nor ‘DUS’ nor ‘TAN’ appears, are:
Ans. 169194
Sol. Let A = words contain ‘HIN’, B = words contain ‘DUS’, C = words contain ‘TAN’
2. n(A B C) = n(T) − n(A B C)
9! 7!
4. = − (7 !+ 7 !+ ) + 3(5!) − 3!
2! 2!
=169194
128. There are 720 permutation of the digits 1, 2, 3, 4, 5, 6. Suppose these permutations are arranged
from smallest to largest numerical values, beginning from 1 2 3 4 5 6 and ending with 6 5 4 3 2 1.
(a) What number falls on the 124th positions?
(b) What is the position of the number 321546?
Ans. (a) 213564, (b) 267th
Sol. numbers starting with 1 = 5 ! = 120
213456, 213465, 213546, 213564
(b) 1 _ _ _ _ _ = 5 !
2 _ _ _ _ _ = 5!
31_ _ _ _ = 4 !
3214 _ _ = 2 !
321546 = 1
267th
129. A forecast is to be made of the results of five cricket matches, each of can be win, a draw or a lost
for Indian team. Find
(iii) the number of different possible forecasts
(iv) the number of forecasts containing 0, 1, 2, 3, 4 and 5 errors respectively
Ans. (i) 243; (ii) 1, 10, 40, 80, 80, 32
Sol. 35 = 243
(ii) zero error = 15 = 1
One error = 5C1⨯2⨯14 = 10
Two error = 5C2⨯22⨯13 = 40
COMBINATORICS 75

Three error = 5C3⨯23⨯12 = 80

Three error = 5C4⨯24⨯1 = 80
Three error = 5C5⨯25 = 32
130. In Indo-Pak one day International cricket match at Sharjah , India needs 14 runs to win just before
the start of the final over. Find the number of ways in which India just manages to win the match
(i.e. scores exactly 14 runs) , assuming that all the runs are made off the bat & the batsman can not
score more than 4 runs off any ball
Ans 1506
Sol. a + b + c + d + e + f = 14, & 0≤a,b,c,d,e≤4
4 – p + 4 – q + 4 – r + 4 – s + 4 – m + 4 – n = 14, & 0 ≤p, q, r, s, m, n ≤4
p + q + r + s + m + n = 10, & 0 ≤p, q, r, s, m, n ≤ 4
Ways = 15C5 – (Cases when score more than 4 on some ball)
(a) when p ≥ 5
p' + q + r + s + m + n = 5 & p’ ≥ 0
10
C5
= 10C5
(b) When p and q ≥ 5
p' + q’ + r + s + m + n = 0
= 1 way
Ways = 15C5 – 6C1(10C5) + 6C2 ⨯1 = 3003 – 1512 + 15 = 1506
131. A question paper on mathematics consists of twelve questions divided into three parts. A, B and C,
each containing four questions. In how many ways can an examinee answer five questions,
selecting at least one from each part.
Ans. 624
Sol. Cases are: (1, 1, 3), (2, 2, 1)
3
C2⨯4C1⨯ 4C1⨯ 4C3 + 3C2⨯4C2⨯ 4C2⨯ 4C1 = 192 + 432 = 624
132. The number of ways in which 8 distinguishable apples can be distributed among 3 boys such that
every boy should get at least 1 apple and at most 4 apples is K. 7P3 where K has the value equal to
Ans. 22
Sol. Cases are: (1, 4, 3), (2, 2, 4), (2, 3, 3)
 8! 8! 8! 
2. = 3! + + 
 4!3! 2!2!2!4! 2!3!3!2! 
COMBINATORICS 76

3!7 !  4 4
=  +1+ 
4!  3 3
22  7 !
=
4!
133. There are 12 books on Algebra and Calculus in our library, the books of the same subject being
different. If the number of selections each of which consists of 3 books on each topic is greatest
then the number of books of Algebra and Calculus in the library are respectively :
Ans. 6, 6
Sol. let algebra books x then calculus books = 12 – x
Number of selections = xC3 ⨯ 12-xC3
C3 12− xC3
x
Consider x −1 13− x  1
C3 C3

x(10 − x)
1
(x − 3)(13 − x)
6 x  39  x  6.5
X =6
134. A gentleman invites a party of m + n (m ≠ n) friends to a dinner and places m at one table T1 and n
at another table T2, the table being round. If not all people shall have the same neighbor in any two
arrangement, then the number of ways in which he can arrange the guests, is
Ans. (m + n)!/4mn
Sol. Total ways = m+nCm(m-1)!(n-1)!
(m + n) !
2.
mn
Neighbors are same in clockwise and anticlockwise arrangement.
Therefore in every four arrangements [(Clock, clock), (Clock, Anti clock),(Anti Clock, Anti
clock),(Anti Clock, clock), we count one.
(m + n) !
Ways =
4mn
135. Find the number of integer between 1 and 10000 with at least one 8 and at least one 9 as digits.
Ans. 974
Sol. 104 – (94 + 94 – 84) = 974
COMBINATORICS 77

136. Sameer has to make a telephone call to his friend Harish, Unfortunately he does not remember the 7
digit phone number. But he remembers that the first three digits are 635 or 674, the number is odd
and there is exactly one 9 in the number. The maximum number of trials that Sameer has to make to
be successful is
Ans. 3402
Cas1 if 9 is not the last digit = 2⨯3C1⨯92⨯4 = 1944
Case2 if 9 is the last digit = 2⨯93⨯1 = 1458
Total = 1944 + 1458 = 3402
137. Six faces of an ordinary cubical die marked with alphabets A, B, C, D, E and F is thrown n times
and the list of n alphabets showing up are noted. Find the total number of ways in which among the
alphabets A, B, C, D, E and F only three of them appear in the list.
Ans. 6C3[3n – 3C1(2n – 2) – 3C2]
Sol. using inclusion exclusion principle
Ways = 6C3[3n – 3C12n + 3C2]

LEVEL III
24. Find the number of integers in the set {1,2,3,….,2009} whose sum of the digits is 11.

25. A four digit number consists of two distinct pairs of repeated digits (for example 2211, 2626 and
7007). Find the total number of such possible numbers that are divisible by 7 or 101 but no both
COMBINATORICS 78

26. Using the digits 0,1,2,3 and 4, find the number of 13 digit sequence that can be written so that the
difference between any two consecutive digits is 1
Examples of such 13 – digit sequence are 0123432123432, 2323432321234 and 23010101234323

27. Three are eight envelops numbers 1 to 8. Find the number of ways in which 4 identical red buttons
and 4 identical blue buttons can be put in the envelops such that each envelope contains exactly one
COMBINATORICS 79

button, and the sum of the numbers on the envelops the red buttons is more than the sum of the
numbers on the envelops containing the blue buttons.

28. Find the number of positive divisors of (20083 + (3 X 2008 X 2009) + 1)2

29. Find the number of 2-element subsets {a, b} of {1,2,3,…,99, 100} such that ab + a + b is a multiple
of 7.
COMBINATORICS 80

30. Find the number of 0–1 binary sequences for by six 0’s and six 1’s such that no three 0’s are
together. For example,110010100101 is such a sequence but 101011000101 and 11010110001 are
not
Sol 357
First put the six 1’s in one sequence. Then there are 7 gaps before the first 1, between two adjacent
1’s and after the last 1. For each such gap, we can put a single 0 or double 0’s (that is 00). If there
are exactly I double 0’s then there are exactly 6- 2i single 0’s where i = 0,1,2,3. Therefore the
 7  7 − i 
umber of such binary sequences with exactly I double 0’s is    . Hence the answers
 i  6 − 2i 
3
 7  7 − i 
  i  6 − 2i  = 357
i =0   
In each of the following 6-digit positive integers 555555,555333,818811, 300388 every digit in the
number appears at least twice. Find the number of such 6-digit positive integers.
Ans 11754
COMBINATORICS 81

Sol. First note that if every digit in the 6-digit number appears at least twice, then there cannot be four
distinct digits in the number. In the other words, the number can only be formed by using one digit,
two distinct digits or three distinct digits respectively. Therefore we consider three cases.
Case : 1 The 6- digit number is formed by only one digit.
Then the number of such 6 – digit numbers is clearly 9.
Case 2: The 6- digit number is formed by two distinct digits.
First, the number of such 6- digit numbers formed by two given digits I and j, where 1 ≤ i < j ≤ 9, is
6 6 6
 2  +  3  +  4  = 50
     
Next, the number of such 6-digit numbers formed by 0 and a given digit ii, where 1 ≤ I ≤ 9, is

 5  5  5 
 2  +  3  +  4  = 25.
     
Therefore the total number of such 6- digit numbers formed by two distinct digits is

9
 2   50 + 9  25 = 2025.
 
Case 3: The 6-digit number is formed by three distinct digits.
First, the number of such 6- digit numbers formed by three given digits i, j and k, where 1 ≤ I < j < k ≤9,
is
6 4
 2  .  2  = 90
  
Next, the number of such 6-digit numbers formed by 0 and two given digits I and j, where 1 ≤ I < j ≤ 9, is

5 4
 2  .  2  = 60
  
Therefore the total number of such 6- digit numbers formed by three distinct digits is

9 9
 3   90 +  2   60 = 9720
   
Hence is the answer is 9 + 2025 + 920 = 11754.
31. Using the digits 1,2,3,4,5,6,7,8, we can form 8!(=40320) 8–digit numbers in which the eight digits
are all distinct. For 1 ≤ k ≤ 40320 , let “a” denote the kth number if these numbers are arranged in
increasing order:
12345678, 12345687, 12345768,……87654321 ;
that is a1 = 12345678, a2 = 1245687, ….a40320 = 87654321. Find a2009 – a2008
COMBINATORICS 82

Ans 441

Sol First we determine a2008 and a2009. Suppose that a 2008  x1x 2 x 3 x 4 x 5 x 6 x 7 x 8 , where the xi’s are distinct
digits in {1,2,3,4,5,6,7,8}
Let A = {ak : k = 1,2,….,40320}
Since 7! = 5040 > 2008, we deduce that x1 = 1, there are more than 2008
Number in A such that the first digit is 1.
As 2  6! < 2008 < 3  6!, we have x2 = 4, as there are less than 2008 numbers in A such that the
first digit is 1 and the second digit is 2 or 3, but there are more than 2008 numbers in A such that
the first digit is 1 and the second digit is 2,3 or 4. Similarly, Since 2  6! + 4  5! < 2008 < 2  6! +
5  5 !, we see that the third digit x3 is 7. By repeating the argument and using the inequalities.
2  6! + 4  5! + 3 + 4! < 2008 < 2  6! + 4 5! + 4  4! and 2004 = 2  6! + 4  5! + 3  4! + 2  3! <
2008 < 2  6! + 4  5! + 3  4! + 3  3!, we obtain x4 = 6, x5 = 5. Note also that among the
numbers I A of the form 146****, the digit 5 first appears as the fifth digit in a2005 if the numbers
are arranged in increasing order. Consequently, as the last three digit are 2,3 and 8, we have a2005 =
14765238. It follows that a2006 = 14765283, a2007 = 14765328, a2008 =14765382, and a2009 14765823.
Hence a2009 – a2008 = 14765823 – 14765382 = 441.
32. Let A be an n -element subset of {1, 2,……,2009} with the property that the difference between
any two numbers in A is not a prime number. Find the largest possible value of n. Find a set with
this number of elements. (Note : 1 is not a prime number)
Sol. If n  A, then n + I  A, i = 2,3,5,7. Among n + 1, n + 4, n + 6 at most one can be in A. Thus
among any 8 consecutive integers, at most 2 can be in S. Hence |A| ≤ 2 [2009/8] = 504. Such a set is
{4k + 1 : k = 0,1,….,502}
33. Let S = {1, 2, 3,……, 30}. Determine the number of vectors (x, y, z, w) with x, y, z, w ∈ S such
that x < w and y < z < w.
Ans 903335
Sol There are two cases consider Case (1) x  {y,z} and Case (2) : x  {y,z}. For case (1), there are
 30   30 
2   ways and for Case (2), there are 3   ways. Hence, total number of ways = 90335
3 4
34. Let f(n) be the number of 0’s in the decimal representation of the positive integer n. For example
f(10001123) = 3 and f (1234567) = 0. Find the value of f(1) + f(2) + f(3) +….f(99999)
Ans 38889
COMBINATORICS 83

Sol. Let S = {1,2,3,….,99999}, and Si = {n  S : f(n) = 1} for I  0. Thus,

S = U0i4Si .
For 0 ≤ i ≤ 4, if n  Si, and n has exactly k digits in the decimal representation, then exactly we have
k – I digits are non zero. Thus,

 k − 1  k −i
Si =  k =i +1 
5
9
 i 
Then, it is clear that
M =| S1 + 2 S2 + 3 S3 4 S4 = 38889 .

35. Let S= {1.2,3,4,…16}. In each of the following subsets of S.

{6}, {1,2,3}, {5,7,9,10,11,12}, {1,2,3,4,5,6,7,8,9}
The sum of the all the elements is a multiple of 3. Find the total number of non empty subsets A of
S such that the sum of all elements in A is a multiple of 3.
Ans 21855.
Sol. Let Si {x  S: x = I (mod 3)} for i = 0,1,2.Note that |S0| = 5, |S2| = 5. Let  be the set of all subsets
A of s such that Sx x is a multiple of 3. Note that for any A  S,
2

x = 
xA

i =0 xA Si
x  A  S1 + 2 A  S2 ( mod 3) .

Then A   if and only if |A  S1| = |A  S2| (mod 3.) Thus it is clear that

 = 2 0 m,where
S

 6   6   6   5   5    6   6    5   5  
m =   +   +     +    +   +    +   +   
 0   3   6   0   3    1   4    1   4  
 6   6   5   5  
  +     +    = 683
 2   5   2   5  
Hence || = 25  683 = 21856. Since want only non empty subsets, we have 21855.
36. Determine the number of ways of tilling a 4 x 9 rectangle by tiles of size 1 x 2.
Sol. Let fn be the number of ways of tiling a 4 x n rectangle. Also let gn be the number of ways of tiling
a 4 x n rectangle with the top or bottom two squares in the last column missing, and let hn be the
number of ways of tiling a 4 x n rectangle with the top and bottom squares in the last column
missing. Set up a system of recurrence relations involving fn, gn and hn by considering the ways to
cover the nth column of a 4 x n rectangle. If two vertical tiles re used, then there are fn-1 ways. If
COMBINATORICS 84

one vertical tile and two adjacent horizontal tiles are used, then there are 2gn-1 ways. If one vertical
tile and two non adjacent horizontal tiles are used, then there are hn-1 ways. If four horizontal tiles
are used, then there are fn-2 ways. Similarly, one can establish the recurrence relations for gn and hn .
In conclusion, we obtain for n  2.
fn = gn-1 + fn-2 + 2gn-1 + hn-1
gn = gn-1 + fn-1
hn = hn-2 + fn-1
with initial conditions f0 = f1 = g1 = h1 = 1 and h0 = 0. Solving fn recursively, we obtain
f9 = 6336.
37. Find the number of 7 digit positive integer such that the digits from left to right non increasing
(Examples of 7 digit non increasing numbers are 9998766 and 555555 ; An example of a number
that is NOT non increasing is 7776556).
Ans 11439
Sol Each 16 – digit binary sequence containing exactly nine ‘0’ and seven ‘1’ can be matched uniquely
to such a 7- digit integer or 00000 as follows : Each ‘1’ will be replaced by a digit from 0 to 9 in
this way : the number of ‘0’s to the right of a particular ‘1’ indicates the value of the digit. For
example 011000010101101 ~ 8832110 and 11110000000111 ~ 9999000.
16 
Thus, required number =   − 1 .
7
38. Determine the number of 4-elements subsets {a, b, c, d} of {1,2,3,4,…,20} such that a + b + c + d is
divisible by 3.
Sol. 11901
For i = 0, 1, 2, let
Ai = {j: 1 ≤ j ≤20 , j  i(mod3}
Note that |A0| = 6, |A1| = 7 and |A2| = 7
It can be shown that for a,b,c,d  a + b + c + d is divisible by 3 iff

(i) a, b, c, d  A i = 2 for alli = 1, 2, or

(ii) a, b, c, d  A 0 = 1 and a, b, c, d  A i = 3for some i :1  i  2; or

(iii) a, b, c, d  A 0 = 2 and a, b, c, d  A i = 1for alli = 1, 2;or

(iv) a, b, c, d  A 0 = 4
COMBINATORICS 85

Thus the number of 4 – elements subsets {a,b,c,d} OF {1,2,3,4,….,20} such that a + b + c + d is divisible by 3
is

 A1  A 2   A0  A1   A1   A2   A0   A1 
  +  + + +   A1  A 2 +  
 2  2   1  3   1   3   2   4 
2 2
7 7  6  6
=   + 6    2 +    7 2   = 11901
 2  3  2  4
39. There are 5 white, 4 yellow, 3 green, 2 blue & 1 red balls. The balls are all identical except for
color. Five of these are to be arranged in a line. Find the number of distinct arrangements.
Ans. 2111
Sol. Cases
(1) All are different
(2) A pair and 3 different
(3) 2 Pair of different colors and 1 different color
(4) A pair and triad of different colors
(5) A triad of 1 color and 2 singles of different colors
(6) A quad of single color and a singles of another color
(7) All five balls of same color
⇒(1)+(2)+(3)+(4)+(5)+(6)+(7)
⇒5! + 4C1×4C3×5!/2! + 4C2×3C1×5!/2!×2! + (3C1)2×5!/2!×3! + 3C1×4C2×5!/2!+2C1×4C1×5!/2!+1
=2111
40. There are 20 books on Algebra & Calculus in our library. Prove that the greatest number of
selections each of which consists of 5 books on each topic is possible only when there are 10 books
on each topic in the library.
Ans. (M1)
Let x books of Algebra
⇒ 20-x books on Calculus
Selections = xC5 ⨯ 20-xC5 (Clearly 5 ≤ x ≤ 15)
x
C5 20− xC5
Consider, x −1
1
C5 21− xC5

(x)(16 − x)
1
(x − 5)(21 − x)
COMBINATORICS 86

(x)(16 − x)  (x − 5)(21 − x)
16 x  26 x − 105
x ≥ 10.5
x = 10
(M2) let x books of Algebra
⇒ 20-x books on Calculus
Selections = xC5 ⨯ 20-xC5 (Clearly 5 ≤ x ≤ 15)
x(x − 1)(x − 2)(x − 3)(x − 4)(20 − x)(19 − x)(18 − x)(17 − x)(16 − x)
5!5!
x(x − 1)(x − 2)(x − 3)(x − 4)(20 − x)(19 − x)(18 − x)(17 − x)(16 − x)
 x + (20 − x)   x − 1 + (19 − x)   x − 2 + (18 − x)   x − 3 + (17 − x)   x − 4 + (16 − x) 
2 2 2 2 2

         
 2   2   2   2   2 

x(x − 1)(x − 2)(x− 3)(x− 4)(20 − x)(19 − x)(18 − x)(17 − x)(16 − x)  (10.9.8.7.6)2
Equality holds when x = 20 – x & x – 1 = 19 – x………& x – 4 = 16 – x
⇒ x= 10
41. 6 white & 6 black balls of the same size are distributed among 10 different urns. Balls are alike
except for the color & each urn can hold any number of balls. Find the number of different
distribution of the balls so that there is at least 1 ball in each urn.
Ans. 26250
Sol. Cases are
(i) 2B, 2B,…. (ii) WB, BB,.. (iii) 2W, 2W,…. (iv) WB, WW,….
(v) WB, WB,…… (vi) 3B,… (vii) 3W,… (viii) 2BW,….
(ix) 2WB,… (x) BB, WW,…..
10! 10! 10! 10! 10! 10!
2 + 2 + + 2 + 2 + =26250
2 !6 ! 2 ! 5!3! 4!4!2! 6!3! 5!4! 4!4!
42. How many 15 letter arrangements of 5 A's, 5 B's and 5 C's have no A's in the first 5 letters, no B's
in the next 5 letters, and no C's in the last 5 letters?
Ans. 2252
Sol. let x B’s in first 5 then (5 – x) C’s in first 5, x C’s in 2nd 5 letters, (5-x) A’s in 2nd 5 letters, x A’s in
last 5 letters, (5-x) B’s in last 5 letters.


5 5
x =0
C x 5C x 5C x
COMBINATORICS 87

=1 + 125 + 1000 + 1000 + 125 + 1

= 2252
43. Let an denote the number of all n-digit positive integers formed by the digits 0, 1 or both such that
no consecutive digits in them are 0. Let bn = The number of such n-digit integers ending with digit 1
and cn = The number of such n-digit integers ending with digit 0.
i. Which of the following is correct?
(a) a17 = a16 + a15 (b) c17 ≠ c16 + c15
(c) b17 ≠ b16 + c16 (d) a17 = c17 + b16
ii. The value of b6 is
(a) 7 (b) 8
(c) 9 (d) 11
Ans. a, b
Sol. From given information
an = bn + cn
Also bn = an-1 and cn = bn-1
a17 = b17 + c17 = a16 + b16 = a16 + a15
c17 = b16 = a15 = b15 + c15 = c16 + c15
b17 = a16 = b16 + c16
Method2:
bn = 1 + n-2C1 + n-3C2 + n-4C3 + n-5C4 + n-6C5 +….
cn = 1 + n-3C1 + n-4C2 + n-5C3 + n-6C4 +….
an = 1 + n-1C1 + n-2C2 + n-3C3 + n-4C4 +…..
a17 = 1 + 16C1 + 15C2 + 14C3 + 13C4 + 12C5 + 11C6 + 10C7 + 9C8 + 8C9
a16 = 1 + 15C1 + 14C2 + 13C3 + 12C4 + 11C5 + 10C6 + 9C7 + 8C8
a15 = 1 + 14C1 + 13C2 + 12C3 + 11C4 + 10C5 + 9C6 + 8C7
a17 = a16 + a15 so option 1 is correct for bn.
first and last place are fixed by 1 so case (1) if only one zero is used such cases = n-2C1.
Case (2) if two zero are used the two zeros are such that no two zeros arc consecutive = n-3C2.
Case (3) if three zeroes are used then the positing of three zeros such that no two zeros are
consecutive = n-4C3 +
So bn = n-2C1 + n-3C2 + n-4C3 + n-5C4 + n-6C5……
For b6 = 4C1 + 3C2 + 1
COMBINATORICS 88

When no zero is used then b6 = 8.

44. In an examination the maximum marks for each of three papers is n and that for fourth paper is 2n.
If marks obtained in each paper are whole numbers, then the number of ways in which a candidate
can get 3n marks is
1
Ans. (n + 1) (5n2 + 10n + 6)
6
Sol. Let a, b, c, d be the marks lost in each paper.
 (n – a) + (n – b) + (n – c) + (2n – d) = 3n
i.e. a + b + c + d = 2n
Non-negative solution = 2m+3C3
But we need to deduct those cases
where a, b, c are greater than n
Say a = a' + n + l
 a' + b + c + d = n – 1
Solutions = n+2C3
Similarly for b and c
Thus, total ways = 2n+3C3 – 3xn+2C3
1
= ( 2n + 3)( 2n + 2 )( 2n + 1) − 3 ( n + 2 )( n + 2 ) n 
6
1
= ( n + 1)  2 ( 2n + 3)( 2n + 1) − 3 ( n + 2 ) n 
6
1
= ( n + 1) 8n2 + 16n + 6 − 3n2 − 6n 
6
1
= ( n + 1) 5n2 + 10n + 6
6
45. Determine the number of 3-digit numbers in base 10 having
(i) At least one 5 and having no 3 and (ii) At least one 5 and having exactly one 3 separately.\
Sol. (i) Here we first count the whole set and subtract the number of 3-digit numbers having
no 5 from it. Since 3 is not there and 0 cannot be the first digit, we can fill the first digit
in 8 ways. But we can fill the second and third digits in 9 ways(as 0 can be included).
Thus we get 8 × 9 × 9 such numbers. If no 5 is there, then the number of such numbers is7 × 8 × 8.
Thus the number of 3-digit numbers not containing 3 and having at least one 5 is (8 × 9 × 9) - (7 × 8
× 8) = 8(81 - 56) = 200.
COMBINATORICS 89

(ii) If 3 is there as a digit, then it can be the first digit or may be the second or third digit.
Consider those numbers in which 3 is the first digit. The number of such numbers having at
least one 5 is (9 × 9) - (8 × 8) = 81 - 64 = 17. The number of 3-digit numbers in which the
second digit is 3 and having at least one 5 is (8 × 9) - (7 × 8) = 16. Similarly, the number of 3-digit
numbers in which the third digit is 3 and having at least one 5 is (8×9)-(7×8) = 16. Thus we get 17
+ 16 + 16 = 49 such numbers.Therefore the number of 3-digit numbers having at most one 3 and at
least one 5 is 200+49 = 249.
46. Find the number of combinations n together of 3n letters of which n are 'a' and n are 'b' and the rest
unlike.
Ans. (n + 2). 2n-1
Sol. let x a’s, y b’s and n-(x+y) unlike ⇒ Combinations are = nCn −(x + y) = nC(x + y)

Total = nCn + 2 nCn-1 + 3nCn-2 + ………+ (n+1) nC0

n n n n

 (r + 1) nCn−r =  (r + 1) nCr =  n n−1Cr −1 +  nCr

r =0 r =0 r =1 r =0

= (n + 2). 2n-1
47. Let A be any k element subset of the set {1, 2, 3, 4…, 100}. Determine the minimum value of k
such that we can always guarantee the existence of two numbers a and b in A such that
|a–b| ≤ 4
Ans. 21
Sol. If A is the set of multiples of 5 in {1,2,3,…,100} then |A| = 20 and |a–b| ≥ 5 for every two number
in A. Thus, if |A| = 20, the existence such two numbers cannot be guaranteed. However, if |A| = 21,
by the pigeonhole principle, there must be two numbers a, b in one of the following twenty sets :
{1,2,3,4,5}, {6,7,8,9,10}, {96,97,98,99,100}
And so |a–b| ≤ 4 Thus the answer is 21