Jimma University

College of Natural Science

Department of Mathematics
Discreet Mathematics & Combinatorics
Work sheet
Chapter 1&2
1. A farmer buys 3 cows, 2 pigs and 4 hens from a man who has 6 cows, 5 pigs and 8
hens. How many choices does the farmer have?
2. Find n if
a) p(n, 4)  42 p(n, 2)
b) 2 p(n, 2)  50  p(2n, 2)
3. In how many ways can a committee consisting of three men and two women be
chosen from seven men and five women?
4. A bag contains six white marbles and five red marbles .Find the number of ways four
marbles can be drawn from the bag if
a) They can be any co lour.
b) Two must be white and two red.
c) They must all be of the same color.
5. A club has 25 members
a) How many ways are there to choose four members of the club to serve on an
executive committee?
b) How many ways are there to choose a president, vice president, secretary, and
treasure of the club?
6. Suppose that a department contains ten men and 15 women. How many ways are
there to form a committee with six members if it must have the same number of men
and women?
n  n  1
7. Prove that if n and k are integers with 1  k  n ,then k    n  .
k   k  1
 n  r   n  n  k 
8. Prove the identity        , whenever n, r and k are non negative
 r  k   k  r  k 
integers with r  n and k  r .
  n  1  n 
9. Show that if n and k are positive integers, then     n  1  /k .
 k   k  1
 2n   2n   2n  2 
10. Let n be a positive integer .Show that      /2 .
 n  1  n   n  1 
11. Show that for all integers n , r  0 if n  1  r, then

 n 1 
P(n  1, r )    P(n, r ) .
 n 1 r 
12. Suppose A and B are events with p( A)  0.6 , P( B)  0.3 , and P( A  B)  0.2 . Find
the probability that :
a) A does not occur
b) B does not occur.
c) A or B occurs.
d) Neither A nor B occurs.
13. A pair of fair dice is thrown. Find the probability p that the sum is 10 or greater if
a) 5 appear on the first die.
b) 5 appear on at least one die.
14. Prove that if A and B are independent events, then Ac and B c are independent
events.
15. In the expansion of (2 x  3 y ) 27 what is the coefficient of x13 y14 .

16. Which term contains x 8 in the expansion of ( x 2  21)10 ?

10 
17. The row of Pascal’s triangle containing the binomial coefficients   , 0  k  10 ,
k 
is 1 10 45 120 210 252 210 120 45 10 1
Use Pascal’s identity to produce the row immediately following this row in Pascal’s
triangle.
18. How many positive integers not exceeding 1000 are divisible by 7 or 11?
19. What is the row of Pascal’s triangle containing the binomial coefficients?
C(9, k ) , 0  k  9 ?

20. What is the expansion of ( x  y )10

  2n   n 
21. If n is a positive integer, show that   =2   + n 2 .
2 2
22. A box contains 3 white balls and 2 black balls. Two balls are drawn without
replacement. What is the probability that the second ball is black given that the first is
black?
23. Sam is going to assemble a computer by himself. He has the choice of chips from two
brands, a hard drive from four, memory from three, and an accessory bundle from
five local stores. How many different ways can Sam order the parts?
24. In one year, three awards (research, teaching, and service) will be given to a class of
25 graduate students in a statistics department. If each student can receive at most one
award, how many possible selections are there?
25. A coin is tossed twice. What is the probability that at least 1 head occurs?
26. A die is loaded in such a way that an even number is twice as likely to occur as an
odd number. If E is the event that a number less than 4 occurs on a single toss of the
die, find P(E).
27. A statistics class for engineers consists of 25 industrial, 10 mechanical, and 10
electrical and 8 civil engineering students. If a person is randomly selected by the
instructor to answer a question, find the probability that the student chosen is
a) an industrial engineering major and
b) a civil engineering or an electrical engineering major.
28. John is going to graduate from an industrial engineering department in a university by
the end of the semester. After being interviewed at two companies he likes, he
assesses that his probability of getting an offer from company A is 0.8, and his
probability of getting an offer from company B is 0.6. If he believes that the
probability that he will get offers from both companies is 0.5, what is the probability
that he will get at least one offer from these two companies?
29. The probability that a regularly scheduled flight departs on time is P(D) = 0.83;the
probability that it arrives on time is P(A) = 0.82; and the probability that it departs
and arrives on time is P(D ∩A) = 0.78. Find the probability that a plane
a) Arrives on time, given that it departed on time, and
b) Departed on time, given that it has arrived on time.
30. A small town has one fire engine and one ambulance available for emergencies. The
probability that the fire engine is available when needed is 0.98, and the probability
that the ambulance is available when called is 0.92. In the event of an injury resulting
from a burning building, find the probability that both the ambulance and the fire
engine will be available, assuming they operate independently.
31. A lot containing 7 components is sampled by a quality inspector; the lot contains 4
good components and 3 defective components. A sample of 3 is taken by the
inspector. Find the expected value of the number of good components in this sample.
32. In a survey of 60 people, it is found that 25 like to drink milk, 26 coffee and 26 tea.
Also 9 like milk and tea, 11 like milk and coffee, 8 like coffee and tea, and 8 like
none of the three drinks. Find the number of peoples who like the three drinks and the
number of people who like exactly one of the three drinks.
33. A die is rolled twice. What is the probability that the sum of the faces is greater than
7, given that
a) The first outcome was a 4?
b) The first outcome was greater than 3?
c) The first outcome was a 1?
d) The first outcome was less than 5?
34. There are 345 students at a college who have taken a course in calculus, 212 who
have taken a course in discrete mathematics, and 188 who have taken course in both
calculus and discrete mathematics. How many students have taken a course in either
calculus or discrete mathematics?

Chapter 3
Recurrence Relations
1. The Lucas numbers satisfy the reoccurrence relation Ln  Ln 1  Ln  2, and the initial

conditions L0  2 and L1  1 then show that Ln  f n 1  f n 1 for n  2,3,...

where f n is the n th Fibonacci number.

2. Solve the following Homogenous recurrence relations using the characteristic roots
method.
 a) a n  6a n 1  8a n  2 for n  2 where a0  2 and a1  5

b) a n  3a n1  4a n2 for n  2 where a0  1 and a1  1

c) a n  5a n 1  6a n  2 for n  2 where a0  0 and a1  1

3. If a0  0, a1  1, a2  4 and a3  37 satisfy the recurrence relation

a n 2  ba n 1  ca n  0 where n  0 and b , c are constants, determine b , c and

solve for an .

4. Determine the values of the constants A and B so that a n  An  B is a solution of

the recurrence relation a n  2a n 1  n  5.

5. Solve the recurrence relation a n  a n1  n for n  1, where a0  2.

6. Solve the recurrence relation a n  a n 1  n 2 for n  1, where a 0  7.

7. Solve the recurrence relation an  2an1  an2  2n  5, where a0  0, a1  1.