USMT302 Discrete Mathematics sem III Revised syllabus 2018
Practical 1: Permutation, cycles and signature of permutation
Objective Questions
1. Let Nn = {1, 2, · · · , n} for a positive integer n then, f : Nn → Nn is a permutation if
(a) f is one one but not onto (b) f is one one and onto
(c) f is onto but not one one (d) f is any function.
2. What is the number of even permutations in S3?
(a) 3 (b) 4 (c) 0 (d) 6
3. The number of elements in Sn is
(a) n (b) n! (c)
(n− 1)!
2
(d) 2n
4. If α =
(
1 2 3 4 5 6 7
3 1 2 4 5 6 7
)
∈ S7 then α−1 is
(a) (1 2 3)
(b) (1 2) (3 6 7)
(c) (1 2 3) (5 6 7)
(d) (4 5)
5. If µ =
(
1 2 3 4 5 6
4 1 5 6 3 2
)
∈ S6 then, number of disjoint cycles in the expression of µ as their
product is
(a) 1 (b) 2 (c) 3 (d) 4
6. . How many permutations of S4 are expressed as composite of disjoint 2-cycles?
(a) 12 (b) 6 (c) 3 (d) 10
7. Signature of identity permutation of Sn is
(a) -1 (b) 0 (c) 1 (d) depends on n.
8. For any integer n ≥ 2, in Sn, the number of even permutations is
(a)
n
2
(b)
n!
2
(c)
n!
4
(d) Number of even permutations - 1
9. If σ = (123)(23) then σ−1 is
(a) (3 2 1)( 3 2) (b) (1 2) (c) (2 3) (d) (1 3)
10. If σ = (2534) is in S6 then, σ
k = I6 for what value of k
(a) 5 (b) 2 (c) 3 (d) 4
11. If σ ◦ τ−1 is an odd permutation then,
(a) Both σ, τ are odd.
(b) Both σ, τ are even.
(c) only if σ is odd and τ is even
(d) one of the σ, τ is odd and other is even.
12. If σ is odd, then which of the following is true?
(a) σ2 is even and σ3 is odd.
(b) σ2 is odd and σ3 is even.
(c) both σ2 and σ3 are odd.
(d) both σ2 and σ3 are odd.
13. How many transpositions does S7 has?
(a)
7!
2
(b) 14 (c) 21 (d) 42
14. How many σ ∈ S4 satisfy the equation σ2 = σ ?
(a) 1 (b) 6 (c) 9 (d) 12
15. Signature of a cycle of length r is
(a) (−1)(r)
(b) (−1)(r−1)
(c) (−1)(r+1)
(d) r
16. If a permutation σ ∈ Sn Sn can be written as a product of r transpositions and also a product
of r′ transpositions, then
(a) r − r′ even
(b) r − r′ odd
(c) r − r′ = 0
(d) |r − r′| = 1
17. Which of the following statements are true for An?
i signature of every element of An is 1.
ii product of any two elements of An is an element of An
iii Identity element belongs to An
iv inverse of every elment of An belongs to An
(a) All the four statements are true for even integer n.
(b) All the four statements are true for all integers n
Sem III Discrete Mathematics 2
(c) i, ii are true but iii, iv are not true.
(d) i, ii and iii are true.
18. If An be the set of all even permutations in Sn, then cardinality of An is
(a) always an even positive integer.
(b) an even positive integer for n > 3.
(c) is even only if n is even.
(d) is always an odd positive integer.
19. The number of elements in A6 is
(a) 6
(b) 720
(c) 360
(d) 26
Descriptive Questions
1. Write down all permutations on 3 symbols {1, 2, 3}.
2. For the following permutations α =
(
1 2 3 4 5
3 2 4 5 1
)
, β =
(
1 2 3 4 5
2 4 1 3 5
)
, γ =
(
1 2 3 4 5
2 5 3 1 4
)
,
(a) Show that αβ 6= βα
(b) Verify α(βγ) = (αβ)γ
(c) Verify (αβ)−1 = β−1α−1
3. Write each of the following permutations σ = (24)(179)(48) and τ = (164)(1379)(83) from S9
as a product of disjoint cycles and also find the product σoτ .
4. Find the inverse of σ = (1358)(2314)(67) ∈ S8 and verify that σoσ−1 = i where i is the identity
permutation in S8.
5. Find the inverse of each of the following permutations. Verify it is the inverse by computing
the product and showing it is the identity permutation.
a) α =
(
1 2 3 4
3 4 2 1
)
b) β =
(
1 2 3 4 5 6 7 8
4 1 5 7 3 8 2 6
)
6. Define an even permutation. Express σ =
(
1 2 3 4 5 6 7 8
8 2 6 3 7 4 5 1
)
∈ S8 as a product of
disjoint cycles. Determine whether σ is odd or even.
Sem III Discrete Mathematics 3
7. Let α = (1325)(143)(25) ∈ S5 Find α−1 and express it as a product of disjoint cycles. State
whether α−1 ∈ A5.
8. Find the signature of following permutation using the definition of signature. σ =
(
1 2 3 4 5
3 5 2 4 1
)
9. Express the following as product of disjoint cycles.
(a) σ =
(
1 3
) (
1 2
) (
1 2 3
)
in S3.
(b) σ =
(
4 3 5 1
) (
1 5 3
) (
1 5 3 4
)
in S5.
(c) σ =
(
1 4
) (
2 3
) (
1 3
) (
2 4
) (
1 2 3 4
)
in S4.
10. Find σ ◦ τ, τ ◦ σ, τ 2, σ−1 ◦ τ 2 for σ =
(
1 2 3 4 5 6
2 4 1 6 5 3
)
and τ =
(
1 2 3 4 5 6
3 5 1 6 2 4
)
.
11. Verify that (σ ◦ τ)−1 = τ−1 ◦ σ−1 for σ =
(
1 2 3 4 5 6
2 5 1 6 4 3
)
and τ =
(
1 2 3 4 5 6
3 5 2 6 1 4
)
.
12. Find x ∈ S5 such that σ ◦ x = τ where σ =
(
1 2 3 4 5
2 5 1 3 4
)
and τ =
(
1 2 3 4 5
3 5 2 4 1
)
.
13. Write all permutations of S3 and list all even permutations of S3.
14. State whether the given permutations from S5 are odd or even?
(a)
(
1 2 3 4 5
4 5 2 3 1
)
(b)
(
1 2 3 4 5
2 3 5 1 4
)
(c) (2 3)(1 4 3)(5 3)(1 3 2 5)
(d) (2 5)(1 3 2 4)(5 2 1)(3 4)
15. Find the number of transpositions, 3-cycles, 4-cycles in S4. Find the remaining permutations
that are not cycles but composite of cycles in S4. Further classify them into even and odd
permutations.
16. . If α = (1 3 6 2 4)(5 8 7)(9), β = (1 5 8 6 2)(3 9 4)(7) and σ = (1)(2 6 8 9 7 4)(3 5) then, show
that σασ−1 = β.
17. Show that (1 6)(1 3)(2 7)(2 5)(2 4) = (1 5)(3 5)(3 6)(5 7)(1 4)(2 7)(1 2). Find third repre-
sentation of this permutation as product of transpositions that is distinct from the given two
representations.
18. State whether following permutations are odd or even.
(a) (2 3 5) (1 3 2)(1 3)(2 4 5 1 3 )(6 1 2 4 3 5)
Sem III Discrete Mathematics 4
(b) (1 2 3)(3 4 5)(1 2)(1 3 4 5)(3 5 1 2)
19. Write down all permutations on 4 symbols {1, 2, 3, 4}. Hence write elements of A4.
20. Write the following permutations as product of disjoint cycles. Express as product of transpo-
sitions and find their signature.
(a) σ =
(
1 2 3 4 5 6 7 8 9
5 4 7 1 2 8 3 9 6
)
(b) σ =
(
1 2 3 4 5 6 7 8 9
7 3 6 5 4 2 9 8 1
)
(c) σ =
(
1 2 3 4 5 6 7 8 9
1 4 6 7 8 3 2 9 5
)
21. Write the following permutation, σ as product of disjoint cycles and find σ−1, σ2 for the given
σ. Write whether σ, σ−1, σ2 are even or odd.
(a) σ =
(
1 2 3 4 5 6 7 8 9
4 5 1 2 3 8 9 6 7
)
(b) σ =
(
1 2 3 4 5 6 7 8
6 3 7 5 4 8 2 1
)
(c) σ =
(
1 3 5 2 4
) (
2 4 1
)
in S5.
22. If σ ∈ Sn can be expressed as product of mi number of i-cycles for i = 1, 2, · · · , n. Then, c() is
defined to be the total number of cycles in a permutation σ i.e. c(σ) = m1 +m2 + · · ·+mn.
If pi = (1 3 5 7)(2 4 6)andτ = (1 5), then what is the relation between c(pi) and c(τpi)? Incase
τ = (1 2) then what is the relation between c(pi) and c(τpi)?
23. Show that (3 4 7 2) can be expressed as product of some transpositions of the form (i, i+1) ∈ S7.
Sem III Discrete Mathematics 5
Practical 2: Recurrence relation
Objective Questions
1. For the sequence 1, 7, 25, 79, 241, 727, . . . , simple formula for (an) is
(a) 3n+2 − 2 (b) 3n − 2 (c) −3n + 4 (d) n2 − 2
2. For the sequence an = 6(1/3)
n, a4 is
(a) 2/25 (b) 2/27 (c) 2/19 (d) 2/13
3. The recurrence system with initial condition a0 = 0 and recurrence relation an = an−1 + 2n− 1
is linear of
(a) degree two and non-homogeneous.
(b) degree one and non-homogeneous.
(c) degree one and homogeneous.
(d) None of these
4. Fibonacci Numbers with f0 = 1, f1 = 1 fibonacci recurrence relation fn = fn−1 + fn−2 is linear
of
(a) degree one and homogeneous
(b) degree two and non-homogeneous
(c) degree two and homogeneous
(d) None of these
5. The recurrence relation for the number of ways to arrange n distinct objects in a row is
(a) hn = hn−1 + n, h1 = 1
(b) hn = nhn−1, h1 = 1
(c) hn = nhn−1, h1 = 0
(d) None of these
6. An elf has a staircase of n stairs to climb. Each step it takes can cover either one stair or two
stairs . A recurrence relation for hn, the number of different ways for the elf to ascend the
n−stairs staircase is given by
(a) hn = nhn−1 + hn−2, h1 = 1, h2 = 2, n ≥ 3.
(b) hn = hn−1 + hn−2, h1 = 1, h2 = 2, n ≥ 3.
(c) hn = hn−1 + nhn−2, h1 = 1, h2 = 2, n ≥ 3.
(d) None of these
7. Consider the recurrence relation an = 8an−1− 15an−2 with initial conditions a0 = 0 and a1 = 2.
Which of the following is an explicit solution to this recurrence relation?
Sem III Discrete Mathematics 6
(a) an = (−3)n + (5)n
(b) an = n(−3)n + n(5)n
(c) an = n(−3)n + (5)n
(d) None of these
8. Consider the recurrence relation an = 6an−1 − 9an−2 with initial conditions a0 = 0 and a1 = 2.
Which of the following is an explicit solution to this recurrence relation, provided the constants
A and B are chosen correctly?
(a) an = A3
n +B3n
(b) an = A3
n +B(−3)n
(c) an = A3
n + nB3n
(d) an = A(−3)n +B(−3)n
9. Consider the recurrence relation an = 2an−1 with initial conditions n ≥ 1 and a0 = 3. Which
of the following is an explicit solution to this recurrence relation?
(a) an = 3.2
n (b) an = 2.3
n (c) an = 3.n
2 (d) None of these
10. Let the characteristic equation x2−a1x−a2 = 0 of the recurrence relation hn = a1hn−1+a2hn−2
has two roots q1 and q2. If hn = c1q
n
1 + c2q
n
2 is the general solution of the recurrence relation of
hn = a1hn−1 + a2hn−2 then q1 and q2 are
(a) Equal and non-zero (b) Distinct (c) non-zero (d) None of these
11. Let the characteristic equation x2−a1x−a2 = 0 of the recurrence relation hn = a1hn−1+a2hn−2
has two roots q1 and q2. If hn = c1q
n
1 + c2nq
n
2 is the general solution of the recurrence relation
of hn = a1hn−1 + a2hn−2 then q1 and q2 are
(a) Equal and non-zero
(b) Distinct and non-zero
(c) Equal
(d) None of these
12. The characteristic polynomial corresponding to the recurrence hn = −25hn−1 + 54hn−2 is
(a) 25x2 − 54x+ 1
(b) −25x2 + 54x
(c) x2 + 25x− 54
(d) x2 − 25x+ 54
13. The characteristic polynomial corresponding to the recurrence hn = 2hn−1 − hn−2 + 13hn−3 is
(a) 2x2 − x+ 13
(b) −2x2 + x− 13
Sem III Discrete Mathematics 7
(c) x3 − 2x2 + x− 13
(d) x3 + 2x2 − x+ 13
14. A recursive linear homogeneous system of order k has
(a) exactly k characteristic roots.
(b) exactly k − 1 characteristic roots.
(c) exactly k distinct characeristic roots.
(d) may not have any characteristic roots.
Descriptive Questions
1. Find the recurrence relation for the number of ways to arrange n distinct objects in a row.
2. An elf has a staircase of n stairs to climb. Each step it takes can cover either one stair or two
stairs . Find a recurrence relation for hn; the number of different ways for the elf to ascend the
n−stairs staircase.
3. Find the recurrence relation and give initial conditions for the number of binary strings of length
n, that do not have two consecutive 0′s
4. Find a recurrence relation for hn, the number of n−digit ternary sequences without any occur-
rence of the subsequence ′012′.
5. Suppose we draw n straight lines on a piece of paper so that every pair of lines intersect (but
no three lines intersect at a common point). Into how many regions do these n lines divide the
plane.
6. Words of length n using only three letters a, b, c are to be transmitted over a communication
channel subject to the condition that no word in which two a’s appear consecutively is to be
transmitted. Give a recurrence relation for the number of words of length n allowed by the
communication channel and solve it.
7. A young pair of rabbits (one of each gender) is placed on an island. A pair of rabbits does not
breed until they are 2 months old. After they are 2 months old, each pair of rabbits produces
another pair each month. Find a recurrence relation and solve it for the number of pairs of
rabbits on the island after n months, assuming that no rabbits ever die.
8. The Tower of Hanoi consists of three pegs mounted on a board together with disks of different
sizes. Initially these disks are placed on the first peg in order of size, with the largest at
the bottom. The rules of the puzzle allow disks to be moved one at a time from one peg to
another as long as a disk is never placed on top of a smaller disk.The goal of the puzzle is
to have all the disks on the second peg in order of size, with the largest at the bottom. Let
Hn denote the minimum number of moves needed to solve the Tower of Hanoi problem with
Sem III Discrete Mathematics 8
n disks. Set up a recurrence relation for the sequence {Hn} and solve it by back-tracking.
9. Solve the following recurrence relations using iteration method.
(a) an = −2an−1;n ≥ 2, a1 = 3
(b) an = 3an−1 + 7;n ≥ 2, a1 = 5
(c) an = an1 + 3, a1 = 2.
10. Solve the following linear homogeneous recurrence relations by using characteristic equation.
(a) hn = 5hn−1 − 6hn−2;h0 = 1, h1 = 0
(b) hn − 4hn−1 + 4hn−2 = 0;n ≥ 2, h0 = 1, h1 = 6
(c) hn − 6hn−1 + 9hn−2 = 0;n ≥ 2, h0 = 1, h1 = 6
(d) hn = 2hn−1 + hn−2 − 2hn−3;n ≥ 3, h0 = 1, h1 = 2, h2 = 0
(e) hn = hn−1 + hn−2;n ≥ 2, h0 = 0, h1 = 1
(f) hn = 6hn−1 − 11hn−2 + 6hn−3, h0 = 2, h1 = 5, h2 = 15
11. Solve the following linear non-homogeneous recurrence relations.
(a) hn = 3hn−1 − 4n;h0 = 2
(b) hn = 3hn−1 + 2n;h0 = 3
12. A bank pays 8% interest each year on money in the savings account. Find a recurrence relation
for the amounts of money a person would have after n years if it follows the investment strategy
of (a) investing 1000 and leaving it in the bank for n years. (b) investing 1000 at the end of
each year.
13. A child has n rupees. Each day he buys either milk for Re. 1/- or Orange juice for Rs. 2/- or
Pineapple juice for Rs. 2/-. If hn denotes the number of ways of spending all the money, find
the recurrence relation for this sequence. In how many ways can he spend Rs. 7?
Sem III Discrete Mathematics 9
Practical 3: Problems based on counting principles, Two way counting.
Objective Questions
1. If A is a countable set, and B is an uncountable set, then the most we can say about A ∪B is
that it is
(a) Finite
(b) Countable
(c) Uncountable
(d) None of these
2. If A is a countable set, and B is finite set, then the most we can say about A ∪B is that it is
(a) Finite
(b) Countable
(c) Uncountable
(d) None of these
3. If A is an uncountable set, and B is finite set, then the most we can say about A∪B is that it
is
(a) Finite
(b) Countable
(c) Uncountable
(d) None of these
4. If A is a countable set, and B is an uncountable set, then the most we can say about the
Cartesian product A×B is that it is
(a) Finite
(b) Countable
(c) Uncountable
(d) None of these
5. If a set S is such that ∃ a bijection between S and Ns and there exists a bijection between S
and Nt for some s, t ∈ N , then
(a) s = t (b) s 6= t (c) s > t (d) s < t
6. If X, Y are finite sets and there is an injective function f : X → Y then
(a) |X| = |Y | (b) |X| ≤ |Y | (c) |X| ≥ |Y | (d) |X| < |Y |
7. The number of functions from a set with m elements to one with n elements are
(a) mn (b) nm (c) m× n (d) None of these
Sem III Discrete Mathematics 10
8. A new company with just two employees, Sanchez and Patel, rents a floor of a building with
12 offices. How many ways are there to assign different offices to these two employees?
(a) 23 (b) 132 (c) 144 (d) None of these
9. In how many ways can we draw a heart or a spade from an ordinary deck of playing cards?
(a) 169 (b) 26 (c) 52 (d) None of these
10. A student can choose a computer project from one of three lists. The three lists contain 23, 15
and 19 possible projects, respectively. How many possible projects are there to choose from ?
(a) 38 (b) 57 (c) 34 (d) 42
11. There are 32 micro computers in a computer center. Each micro computer has 24 ports. How
many different ports to a micro computer in the center are there ?
(a) 56 (b) 768 (c) 8 (d) None of these
12. The number of ways to pick a sequence of two different letters of the alphabet that appear in
the word BOAT is
(a) 21 (b) 12 (c) 8 (d) None of these
13. The number of ways to pick first a vowel and then a consonant from the word MATHEMATICS
is
(a) 56 (b) 15 (c) 4 (d) None of these
14. How many ways are there to pick a man and a woman who are not husband and wife from a
group of n married couples
(a) n! (b) n(n− 1) (c) n+ (n− 1) (d) None of these
Descriptive Questions
1. Show that in any set X of people there are two members of X who have the same number of
friends in X.
2. Show that the set N is infinite.
3. Prove that if X is a subset of Y , and X is infinite, then Y is infinite.
4. Show that the set Z of all integers is countably infinite (or countable).
5. Show that every infinite subset of N is countable.
6. Prove that a subset of a countable set is either finite or countable.
7. Show that N× N is countable.
8. Show that Q+ is countable.
9. Show that Q is countable.
Sem III Discrete Mathematics 11
10. Show that (0, 1) the set of all real numbers between 0 and 1 is not countable.
11. Show that [0, 1] is uncountable.
12. Show that R is uncountable.
13. In Algebra class, 32 of the students are boys. Each boy knows five of the girls in the class and
each girl knows eight of the boys. How many girls are in the class?
14. How many different 4-letter radio station call letters (upper case) can be made
a) if the first letter must be a K or W and no letter may be repeated?
b) if repeats are allowed (but the first letter is a K or W).
c) How many of the 4-letter call letters (starting with K or W) with no repeats end in R?
15. How many ways are there to pick 2 different cards from a standard 52 card deck such that:
(a) The first card is an Ace and the second card is not a Queen?
(b) The first card is a spade and the second card is not a Queen?
16. How many ways are there to roll two dice to yield a sum divisible by 3?
17. How many nonempty different collections can be formed from five (identical) apples and eight
(identical) oranges?
18. How many two-digit numbers have distinct and non-zero digits?
19. How many ways can we get a sum of 4 or of 8 when two distinguishable dice (say red and white)
are rolled? How many ways can we get an even sum?
20. In how many ways can we draw a heart or a spade from an ordinary deck of playing cards ? A
heart or an ace ? An ace or a king ? A card numbered 2 through 10 ? A numbered card or a
king ?
21. A store carries 8 styles of pants. For each style, there are 10 different possible waist sizes, 6
pants lengths, and 4 colour choices. How many different types of pants could the store have?
22. Given eight different English books, seven different French books, and five different German
books:
(a) How many ways are there to select one book?
(b) How many ways are there to select three books, one of each language?
23. How many ways are there to form a three-letter sequence using the letters a, b, c, d, e, f:
(a) with repetition of letters allowed?
(b) without repetition of any letter?
(c) without repetition and containing the letter e?
(d) with repetition and containing e?
Sem III Discrete Mathematics 12
Practical 4: Stirling numbers of second kind, Pigeon hole principle
Objective Questions
1. Which of the following are partitions of {1, 2, . . . , 8}?
(a) {{1, 3, 5}, {1, 2, 6}, {4, 7, 8}}
(b) {{1, 3, 5}, {2, 6, 7}, {4, 8}}
(c) {{1, 3, 5}, {2, 6}, {2, 6}, {4, 7, 8}}
(d) {{1, 5}, {2, 6}, {4, 8}}
2. Let S(n, k) denote Stirling number of second kind on n-set into k-disjoint nonempty unordered
subsets, then S(0, 0) is
(a) 1 (b) 0 (c) n (d) None of these
3. Let S(n, k) denote Stirling number of second kind on n-set into k-disjoint nonempty unordered
subsets, then S(n, n) is
(a) 0 (b) 1 (c) n (d) None of these
4. Let S(n, k) denote Stirling number of second kind on n-set into k-disjoint nonempty unordered
subsets, then S(n, k) = 0 if
(a) k > n (b) k < n (c) k = n (d) None of these
5. Let S(n, k) denote Stirling number of second kind on n-set into k-disjoint nonempty unordered
subsets, then S(n, 1) is
(a) n! (b) (n− 1)! (c) 1 (d) None of these
6. If n and k be positive integers with n ≥ k, then S(n, k) has recurrence formula
(a) S(n, k) = S(n− 1, k − 1) + kS(n, k)
(b) S(n, k) = S(n− 1, k − 1) + kS(n− 1, k)
(c) S(n, k) = S(n− 1, k − 1) + kS(n, k − 1)
(d) None of these
7. A basket of fruit is being arranged out of apples, bananas, and oranges. What is the smallest
number of pieces of fruit that should be put in the basket in order to guarantee that either
there are at least 8 apples or at least 6 bananas or at least 9 oranges?
(a) 12 (b) 21 (c) 20 (d) None of these
8. What is the minimum number of students required in a discrete mathematics class to be sure
that at least six will receive the same grade, if there are five possible grades, A, B, C, D, and
F?
(a) 25 (b) 26 (c) 5 (d) None of these
Sem III Discrete Mathematics 13
9. How many students must be in a class to guarantee that at least two students receive the same
score on the final exam, if the exam is graded on a scale from 0 to 100 points?
(a) 101 (b) 102 (c) 100 (d) None of these
10. The number of pigeons are distributed among k pigeonholes, then at least one pigeonhole
contains two or more pigeons is
(a) k + 1 or more
(b) k or more
(c) k − 1 or more
(d) None of these
11. Every sequence of n2 + 1 real numbers contains a monotone subsequence of length at least
(a) n (b) n+ 1 (c) n2 + 1 (d) None of these
12. Let m objects be distributed into n boxes, then at least one box contains at least r+ 1 objects
only if,
(a) m > nr (b) m < nr (c) m = nr (d) None of these
13. Let S be a sequence of real numbers. Then either S has a monotonically increasing subsequence
with m+ 1 terms or a strictly decreasing subsequence with n+ 1 terms only if S has
(a) mn+ 1 real numbers
(b) mn− 1 real numbers
(c) m+ n+ 1 real numbers
(d) None of these
Descriptive Questions
1. Define Stirling number S(n, k) of second kind. Prove that S(n, n− 1) =
(
n
2
)
2. Prove that S(n, n− 2) =
(
n
3
)
+ 3
(
n
4
)
= 1
4
(3n− 5)
(
n
3
)
3. Prove that S(n, n− 3) = 1
2
(n2 − 5n+ 6)
(
n
4
)
4. Without finding the value of either the LHS or RHS, show that S(5, 2) =
(
5
1
)
+
(
5
2
)
.
5. Find S(7, 3) by using the recursion formula for S(n, k).
6. i Find the coefficient of ab3c6d in the expansion of (a+ b+ c+ d)11.
Sem III Discrete Mathematics 14
ii Show that there are at least 12 terms in the expansion of (a+b+c+d)11 whose coefficients
are 9240.
iii Consider the expansion of (a+ b+ c+ d)11. Obtain the coefficient of a3b5c3.
iv Do you get the same answers for (i) and (iii)? Can you comment on at least in the above
problem (ii)?
7. Let p, q and r be non-negative integers. Suppose p+ q + r = 4.
(a) Write down all the solutions of this equation.
(b) How many solutions do you get?
(c) Calculate S(5, 2).
(d) Do the answers of (b) & (c) match.
8. Let S(n, k) be the Stirling number of second kind. Find S(4, 2), S(5, 2), S(6, 2), S(6, 3)
9. Show that if we take n+ 1 numbers from the set {1, 2, . . . , 2n}, then some pair of numbers will
have no factors in common.
10. Show that if n + 1 integers are chosen from the set {1, 2, . . . , 3n}, then there are always two
which differ by at most two.
11. Given 5 points in the plane with integer coordinates, show that there exists a pair of points
whose midpoint also has integer coordinates.
12. During a month with 30 days a baseball team plays at least a game a day, but no more than
45 games. Show that there must be a period of some number of consecutive days during which
the team must play exactly 14 games.
13. A student has 6 weeks (that is, 42 days) to prepare for her examination and she has decided
that during this period she will put in a total of 70 hours towards her preparation for the
examination. She decides to study in full hours every day, studying at least one hour on each
day. Prove that no matter how she schedules her studying pattern, she will study for exactly
13 hours during some consecutive days.
14. A chess player has 77 days to prepare for a serious tournament. He decides to practice by
playing at least one game per day and a total of 132 games. Show that there is a succession of
days during which he must have played exactly 21 games.
15. A chess master who has 11 weeks to prepare for a tournament decides to pay at least one game
every day but, in order not to tire himself, he decides not to play more than 12 games during
any calender week. Show that there exists a succession of (consecutive) days during which the
chess master will have played exactly 21 games.
16. Prove that if seven distinct numbers are selected from {1, 2, . . . , 11}, then some two of these
numbers sum to 12.
Sem III Discrete Mathematics 15
17. From the integers 1, 2, . . . , 200, we choose 101 integers. Show that, among the integers chosen,
there are two such that one of them is divisible by the other.
18. Show that in any set of six people there are either three mutual friends or three mutual strangers.
Further, show that it is possible to have a group of five people such that in any collection of
three people out of these five, only two are mutual friends or only two are mutual strangers.
19. Ten line segments are drawn, joining (1, 1), (7, 5), (8, 2), (9, 4) and (4, 4). Identify a mid point
of these 10 line segments, such that both the coordinates of the mid-point are integers.
(Generalization of the above problem) Let P1, P2, P3, P4andP5 be any 5 lattice points in the
plane. (A point in the Cartesian plane is called a lattice point if both of its coordinates are
integers). Show that at least one of the line segments, determined by these lattice points has
some lattice point (not necessarily from P1 to P5) as its mid-point.
20. Show that in any set of 10 people there are either four mutual friends or three mutual strangers.
21. Is it possible to draw a regular pentagon along with all its diagonals, using two colours Red
and Blue, such that there does not exist any triangle (created by considering any three points
of the five points) which has all its sides either of Red colour or of Blue colour? (Draw such a
pentagon and confirm that the answer to this question is affirmative. While joining the points,
you may consider a continuous segment as Red colour and a dotted segment as Blue colour.)
22. If 5 points are chosen at random in the interior of an equilateral triangle of side length 2 units,
show that at least 1 pair of points has a separation of less than 1 unit.
23. If 10 points are chosen at random in the interior of an equilateral triangle of side length 3 units,
show that at least 1 pair of points has a separation of less than 1 unit.
Sem III Discrete Mathematics 16
24. If 5 points are chosen at random in the interior of a square of side length 2 units, show that at
least 1 pair of points has a separation of less than
√
2 units.
25. Show that among any five points inside an equilateral triangle of side length 1, there exist two
points whose distance is at most 1
2
.
26. For given n integers a1, a2, . . . , an, not necessarily distinct, show that there exist integers k and
l with 0 ≤ k < l ≤ n such that the sum ak+1 + ak+2 + · · ·+ al is a multiple of n.
Sem III Discrete Mathematics 17
Practical 5: Multinomial theorem, identities, permutation and combination of
multi-set
Objective Questions
1. How many 10-letter patterns can be formed from the letters of the word BASKETBALL?
(a) C(10, 10)
(b)
10!
2!2!1!1!1!1!2!
(c)
10!
2! + 2! + 1! + 1! + 1! + 1! + 2!
(d) None of these
2. In how many ways can the letters of the word ’LEADER’ be arranged?
(a) 72 (b) 144 (c) 360 (d) None of these
3. In how many ways can 15 billiard balls be arranged in a row if 3 are red, 4 are white and 8 are
black?
(a) 12 (b) 18 (c) 96 (d) None of these
4. In how many ways can a party of 9 persons arrange themselves around a circular table?
(a) 9! (b) 8! (c) 9!+8! (d) None of these
5. The number of ways of placing 8 similar balls in 5 numbered boxes is
(a) C(12, 8) (b) C(13, 8) (c) C(12, 5) (d) None of these
6. The number of terms in the expansion of (2x+ 3y − 5z)8 is
(a) C(10, 8) (b) C(11, 8) (c) C(10, 3) (d) None of these
7. How many ways are there to select a captain and a vice captain from 15 members of a cricket
team?
(a) P (15, 2) (b) P (14, 2) (c) P (15, 14) (d) None of these
8. Suppose that Sachin has to visit eight different cities. He must begin his trip in a specified city,
but later he can visit the other seven cities in any order he wishes. How many possible ways
are there for Sachin to visit these cities?
(a) 7! (b) 8! (c) 56 (d) None of these
9. How many ways are there to select five players for an inter college basket ball match from a
10-member team?
(a) C(10, 5) (b) P (10, 5) (c) C(10, 2) (d) None of these
10. How many 3 digit numbers can be formed using the digits 1, 3, 5, 7, 9, where we are allowed
to repeat the digits?
(a) 125 (b) 25 (c) 5 (d) None of these
Sem III Discrete Mathematics 18
11. Suppose that there are 9 faculty members in the mathematics department and 11 in the com-
puter science department of a college. How many ways are there to select a committee to
develop a discrete mathematics course at the college if the committee is to consist of three
faculty members from the mathematics department and four from the computer science depart-
ment?
(a) C(9, 3).C(11, 4)
(b) P (9, 3).P (11, 4)
(c) P (9, 3).C(11, 4)
(d) None of these
12. How many solutions are there to the equation x1 + x2 + x3 + x4 = 17, where x1, x2, x3, and x4
are nonnegative integers?
(a) C(20, 3) (b) C(17, 3) (c) C(21, 3) (d) None of these
13. A box contains 12 black and 8 green marbles. How many ways can 3 black and 2 green marbles
be chosen?
(a) C(12, 3) + C(8, 2)
(b) C(12, 2) + C(8, 3)
(c) C(12, 5) + C(8, 5)
(d) None of these
Descriptive Questions
1. Find the coefficient of x21x3x
3
4x5 in the expansion of (x1 + x2 + x3 + x4 + x5)
7
2. Find the coefficient of x31x2x
2
3 in the expansion of (2x1 − 3x2 + 5x3)6
3. How many 11-letter words can be made from the letters of the word ABRACADABRA?
4. How many 11 letter words can be made form the letters of the word MISSISSIPPI?
5. Evaluate the multinomial numbers
(
11
4, 3, 2, 1
)
and
(
9
5, 2
)
6. Prove that
i
∑r
k=0
(
m
k
)(
n
r − k
)
=
(
m+ n
r
)
ii
∑n
i=r
(
i
r
)
=
(
n+ 1
r + 1
)
iii
∑n
k=0
(
n
k
)2
=
(
2n
n
)
Sem III Discrete Mathematics 19
iv
∑n
k=0
(
n
k
)
= 2n
v 2n =
n∑
k=0
(−1)k
(
n
k
)
3n−k
vi 3n =
n∑
k=0
(
n
k
)
2k.
7. Provide the combinatorial proof of the following identities:
i
(
n
k
)(
k
m
)
=
(
n
m
)(
n−m
k −m
)
ii
(
2n
2
)
= 2
(
n
2
)
+ n2.
Hint:Observe the sketch, drawn below
8. How many r-permutations does an n-set have?
9. If S = {a, b, c}, then find all 1-permutations, 2-permutations, 3-permutations of S.
10. What is the number of ways to order the 26 letters of the alphabet so that no two of the vowels
a, e, i, o, and u occur consecutively?
11. How many seven-digit numbers are there such that the digits are distinct integers taken from
{1, 2, . . . 9} and such that the digits 5 and 6 do not appear consecutively.
12. Consider the multiset {3.a, 2.b, 4.c} of 9 objects of 3 types. Find the number of 8-permutations
of S.
13. Ten people, including two who do not wish to sit next to one another, are to be seated at a
round table. How many circular seating arrangements are there?
Sem III Discrete Mathematics 20
14. There are 15 people enrolled in a mathematics course, but exactly 12 attend on any given day.
There are 25 seats in the classroom. Find the number of different ways in which an instructor
might see the 12 students in the classroom.
15. How many eight-letter words can be constructed by using the 26 letters of the alphabet if each
word contains three, four or five vowels? It is understood that there is no restriction on the
number of times a letter can be used in a word.
16. What is the number of nondecreasing sequences of length r whose terms are taken from
1, 2, . . . , k?
17. Let S be the multiset {10.a, 10.b, 10.c, 10.d} with objects of four types ab, c and d. What is the
number of 10-combinations of S which have the property that each of the four types of objects
occurs at least once.
18. Write the number of integral solutions of the equation x1 + x2 + x3 + x4 = 20 in which x1 ≥
3, x2 ≥ 1, x3 ≥ 0, x4 ≥ 5
19. There are five types of color T-shirts on sale, black, blue, green, orange, and white. John is
going to buy ten T-shirts, he has to buy at least two blues and two oranges, and at least one
for all other colors. Find the number of ways that John can select ten T-shirts.
Sem III Discrete Mathematics 21
Practical 6: Inclusion-Exclusion principle. Euler phi function
Objective Questions
1. If a school has 100 students with 50 students taking French, 40 students taking Latin, and 20
students taking both languages, how many students take no language?
(a) 110
(b) 30
(c) 210
(d) None of these
2. Suppose that there are 1807 freshmen at your school. Of these, 453 are taking a course in
computer science, 567 are taking a course in mathematics, and 299 are taking courses in both
computer science and mathematics. How many are not taking a course either in computer
science or in mathematics?
(a) 1086
(b) 721
(c) 1020
(d) None of these
3. How many positive integers not exceeding 1000 are divisible by 7 or 11?
(a) 232
(b) 220
(c) 244
(d) None of these
4. Which is the following derangement of permutation 12345?
(a) 21543
(b) 21453
(c) 12345
(d) None of these
5. At a party there are n men and n women. In how many ways can the n women choose male
partners for the dance?
(a) Dn
(b) n!
(c) (n− 2)!
(d) None of these
Sem III Discrete Mathematics 22
6. At a party there are n men and n women. How many ways are there for the dance if everyone
has to change partners?
(a) n!
(b) Dn
(c) (n− 2)!
(d) None of these
7. At a party, seven gentlemen check their hats. In how many ways can their hats be returned so
that no gentleman receives his own hat?
(a) 7!
(b) D7
(c) D7
7
(d) None of these
8. At a party, seven gentlemen check their hats. In how many ways can their hats be returned so
that at least one of the gentlemen receives his own hat?
(a) 7!
(b) 7!−D7
(c) 7!×D7
(d) None of these
9. If p is a prime and k > 0, then:
(a) φ(pk) = pk
(
1 + 1
p
)
(b) φ(pk) = p
(
1− 1
p
)
(c) φ(pk) = pk
(
1− 1
p
)
(d) None of these
10. If n ≥ 2 is an integer whose prime factorization is n = pα11 pα22 . . . pαrr where αi ≥ 1, ∀i, 1 ≤ i ≤ r,
then
(a) φ(n) = n
(
1 + 1
p1
)(
1 + 1
p21
)
. . .
(
1 + 1
pr
)
(b) φ(n) =
(
1− 1
p1
)(
1− 1
p21
)
. . .
(
1− 1
pr
)
(c) φ(n) = n
(
1− 1
p1
)(
1− 1
p21
)
. . .
(
1− 1
pr
)
(d) None of these
11. For n > 2, φ(n) is:
Sem III Discrete Mathematics 23
(a) Prime number
(b) Even number
(c) Odd number
(d) None of these
12. If n > 1, is prime. Then φ(n) is:
(a) n− 1
(b) n
(c) n+ 1
(d) None of these
13. φ(13) is:
(a) 13
(b) 12
(c) 14
(d) None of these
Descriptive Questions
1. There are 73 students in the first year Humanities class at the University of California. Among
them a total of 52 can play the piano, 25 can play the violin, and 20 can play the flute, 17
can play both piano and violin, 12 can play piano and flute, and 7 can play violin and flute,
but only one student can play all three instruments. How many in the class cannot play any of
them?
2. In a class of 67 mathematics students, 47 can read French, 35 can read German and 23 can read
both languages. How many can read neither language? If, furthermore, 20 can read Russian,
of whom 12 also read French, 11 read German also and 5 read all three languages, how many
cannot read any of the three languages?
3. Find the number of ways of arranging the letters A, E, M, O, U, Y in a sequence in such a way
that the words ME and YOU do not occur.
4. Define derangement.Write formula for derangement Dn and hence find D5.
5. Define Euler φ function. Find φ(60) by using Euler formula φ(n) ?
6. A total of 1232 students have taken a course in Spanish, 879 have taken a course in French,
and 114 have taken a course in Russian. Further, 103 have taken courses in both Spanish and
French, 23 have taken courses in both Spanish and Russian, and 14 have taken courses in both
French and Russian. If 2092 students have taken at least one of Spanish, French, and Russian,
how many students have taken a course in all three languages?
Sem III Discrete Mathematics 24
7. How many positive integers < 70 are relatively prime to 70?
8. Suppose there are 100 students in a school and there are 40 students taking each language,
French, Latin, and German. Twenty students are taking only French, 20 only Latin, and 15
only German. In addition, 10 students are taking French and Latin. How many students are
taking all three languages? No language?
9. Find the number of integers between 1 and 1000, inclusive, that are not divisible by 5, 6, and
8.
10. How many permutations of the letters M, A, T, H, I, S, F, U, N are there such that none of the
words MATH, IS, and FUN occur as consecutive letters? (Thus, for instance, the permutation
MATHISFUN is not allowed, nor are the permutations INUMATHSF and ISMATHFUN.)
11. Find the number of permutations i1, i2, . . . , in of {1, 2, . . . , n} in which 1 is not in the first
position (i.e.i1 6= 1).
12. Show that e−1 = Dn
n!
where Dn is number of derangements on n symbols.
13. Define derangement Dn. Show that Dn = (n− 1)(Dn−2 +Dn−1) (n = 3, 4, 5, . . . )
14. Define derangement Dn. Show that Dn = nDn−1 + (−1)n (n = 2, 3, 4, . . . ) with D1 = 0, D2 = 1
15. How many solutions does x1 +x2 +x3 = 11 have, where x1, x2 and x3 are non-negative integers
x ≤ 3, x2 ≤ 4 and x3 ≤ 6?
16. If p is a prime and k > 0, then prove that φ(pk) = pk
(
1− 1
p
)
17. Define Euler φ function. Hence find φ(360)
18. In how many ways 5 gents and 4 ladies dine at a round table, if no two ladies are to sit together?
19. Twelve persons are made to sit around a round table. Find the number of ways they can sit
such that 2 specified are not together.
Sem III Discrete Mathematics 25
Practical 7: Miscellaneous theory questions
Unit-I
1. Prove that every permutation in Sn can be written as a cycle or as a product of disjoint cycles.
2. Prove that every permutation in Sn can be written as a product of transpositions.
3. If the pair of cycles a α = (a1, a2, . . . , am) and α = (b1, b2, . . . , bn) have no entries in common,
then show that αβ = βα.
4. Define signature of a permutation. If σ is any permutation in Sn, then show that the sign of σ
is ±1.
5. If a permutation σ ∈ Sn can be written as a product of r transpositions and also a product of
r′ transpositions, then show that either r and r′ are both even or r and r′ are both odd. (i.e.
r and r′ have the same parity).
6. Prove that, for any integer n ≥ 2, exactly half of the permutations in Sn are odd and half are
even.
7. If α, β ∈ Sn, then show that Sgn(αβ) = Sgn(α).Sgn(β).
8. Prove that for n > 1, An has order
n!
2
.
9. Define linear homogeneous recurrence relation. Let q be a nonzero number. Show that hn = q
n
is a solution of the linear homogeneous recurrence relation
hn − a1hn−1 − a2hn−2 − · · · − akhn−k = 0, (ak 6= 0, n ≥ k)− (1)
with constant coefficients if and only if q is a root of the polynomial equation xk − a1xk−1 −
a2x
k−2 − · · · − ak = 0 − (2). Hence prove that if the polynomial equation has k distinct roots
q1, q2, . . . , qk then hn = c1q
n
1 + c2q
n
2 + · · ·+ ckqnk is the general solution of (1).
10. Show that if the characteristic equation x2 − a1x − a2 = 0 of the recurrence relation hn =
a1hn−1 + a2hn−2 has two distinct non-zero roots q1 and q2 then hn = c1qn1 + c2q
n
2 is the general
solution of the recurrence relation of hn = a1hn−1 + a2hn−2.
11. Show that if the characteristic equation x2 − a1x − a2 = 0 of the recurrence relation hn =
a1hn−1 + a2hn−2 has a single non-zero roots q1 then hn = c1qn1 + c2nq
n
2 is the general solution of
the recurrence relation of hn = a1hn−1 + a2hn−2.
12. Let h0, h1, . . . , hn is a sequence of real numbers. When do we say that this sequence satisfies
a linear recurrence relation of order k? Also show that there exist constants c1, c2, . . . , ck such
that hn = c1q
n
1 + c2q
n
2 + · · ·+ ckqnk satisfies h0 = b0, h1 = b1, . . . , hk−1 = bk−1 where q1, q2, . . . , qk
are distinct real numbers and b0, b1, . . . , bk−1 are any k real numbers.
Sem III Discrete Mathematics 26
Unit-II
13. Let m be a natural number. Sow that the following statement is true for every natural number
n: If there is an injective function from Nn to Nm, then n ≤ m.
14. Let A be a nonempty set, let n ∈ N . Show that the following statements are equivalent:
(a) There is a surjective function f : Nn → A
(b) There is an injective function g : A→ Nn
(c) A is finite and |A| ≤ n.
15. If X, Y are finite sets and there is an injective function f : X → Y then show that |X| ≤ |Y |
16. If the set S is such that there is a bijection b : N→ S then Show that S is infinite
17. Let A be a nonempty set. Show that the following are equivalent:
(a) There is a surjective function f : Nn → A
(b) There is an injective function g : A→ Nn
(c) A is finite or countable.
18. If A,B are countable sets then A×B is also countable.
19. If A1, A2 are countable then A1 ∪ A2 is also countable.
20. State and prove Addition Principle and Multiplication Principle of Counting.
21. Let X and Y be finite non-empty sets, and S be a subset of X × Y . Let Rx(S) be the set of
pairs in S whose first coordinate is x and Cy(S) be the set of pairs in S whose second coordinate
is y. Then the following results hold.
(a) The size of S is given by |S| = ∑x |Rx(S)| = ∑y |Cy(S)|
(b) If |Rx(S)| is a constant r, independent of x and |Cy(S)| is a constant c, independent of y,
then r|X| = c|Y |.
22. Show the number of ways of putting n balls of distinct colours into k distinct boxes with each
box containing at least one ball is k!S(n, k), where S(n, k) is Stirling number of second type.
23. Let n and k be positive integers. Show that the number of surjective functions from an n−set
to a k−set is equal to k!S(n, k), where S(n, k) is Stirling number of second type.
24. Let n and m be positive integers and k be an integer such that 1 ≤ k ≤ m. Prove that the
number of functions from a n-set to a m-set is
mn =
m∑
k=1
(
m
k
)
k!S(n, k)
Sem III Discrete Mathematics 27
25. Define Stirling number S(n, k) of second kind. Let n and k be positive integers with n ≥ k.
Show that
S(n, k) = S(n− 1, k − 1) + kS(n− 1, k)
26. For all n ≥ 2. Show that S(n, 2) = 2n−1 − 1
27. Let S = {a1, a2, . . . , amn+1} be a sequence of mn+1 real numbers. Then show that either S has
a monotonically increasing subsequence with m+ 1 terms or a strictly decreasing subsequence
with n+ 1 terms.
28. Show that every sequence a1, a2, . . . , an2+1 of n
2 + 1 real numbers contains either an increasing
subsequence of length n+ 1 or a decreasing subsequence of length n+ 1.
Unit-III
29. State and prove Binomial Theorem.
30. Let n be a non-negative integer. Show that
(x+ y)n =
(
n
0
)
xn +
(
n
1
)
xn−1y +
(
n
2
)
xn−2y2 + · · ·+
(
n
n
)
yn
31. Define multinomial coefficient. Let S be an n-set and suppose the n objects in S are to
be put in r distinct boxes B1, B2, . . . , Br such that the i
th box Bi contains ni objects with
n1 + n2 + · · ·+ nr = n. Show that the number of ways of doing this is equal to(
n
n1, n2, . . . , nr
)
=
n!
n1!n2! . . . nr!
32. State and prove Multinomial theorem.
33. Let n be a non-negative integer. Show that
(x1 + x2 + · · ·+ xr)n =
∑
n1+n2+···+nr=n
(
n
n1, n2, . . . , nr
)
xn11 x
n2
2 . . . x
nr
n
where the summation extends over all nonnegative integers n1 + n2 + · · ·+ nr = n.
34. Let n and k be positive integers. Show that
(
n
k
)
=
(
n− 1
k
)
+
(
n− 1
k − 1
)
35. Let S be a multi-set consisting of k distinct objects, each with infinite multiplicity. Show that
the total number of r-permutations of S is kr.
Sem III Discrete Mathematics 28
36. Let S be a multiset with k distinct objects with finite repetition numbers n1, n2, . . . , nk respec-
tively. If the size of S is n = n1 + n2 + · · ·+ nk, then show that the number of permutations of
S equals
n!
n1!n2! . . . nk!
37. The number of circular r-permutations of a set of n elements is given by
P (n, r)
r
=
n!
r ∗ (n− r)!
38. For 0 ≤ r ≤ n, Prove that P (n, r) = r! ∗
(
n
r
)
. Hence prove that
(
n
r
)
=
n!
r! ∗ (n− r)!
39. Let S be a multiset with objects of k different types each with an infinite repetition number
(multiplicity). Show that the number of r-combinations of S equals(
r + k − 1
r
)
=
(
r + k − 1
k − 1
)
40. Show that the number of ways of putting r identical objects into k distinct boxes with each
box containing at least one object is
(
r − 1
k − 1
)
41. State and prove Inclusion-Exclusion principle.
42. Show that the number of derangements Dn of {1, 2, . . . , n} is given by
Dn =
{
1
0!
− 1
1!
+
1
2!
− 1
3!
+ · · ·+ (−1)n 1
n!
}
43. Let n ≥ 2 be an integer whose prime factorization is n = pα11 pα22 . . . pαrr where αi ≥ 1, ∀i, 1 ≤
i ≤ r, prove that
φ(n) = n
(
1− 1
p1
)(
1− 1
p21
)
. . .
(
1− 1
pr
)
Sem III Discrete Mathematics 29