BSc Mathematics SEM III 2019 2020 Oct 2020 MATHS DISCRETE MATHEMATICS PAPER III Question Paper - Mumbai University | munotes

Questions asked in this paper

• Figures to the right indicate marks for respective parts,

1. Q1 Choose correct alternative in each of the following : 20 marks
   • i) The number of elements in Ag is li) The recurrence system with the initial condition = 0 and recurrence relation
   • a) Degree 2 and non homogeneous b) Degree | and non homogeneous
   • c) Degree 1 and homogeneous d) None of these
   • iii) Sequence a, = 6(1/3)", then Q, is
   • iv) Let S(n, k) denote stirling number of second kind on n-set into k disjoint nun empty ordered subset then S(0, 0) is
   • c) n d) None of these The number of functions from a set with m elements to one with n elements are mxn d) None of these
   • vi) The Cartesian Product of two countable sets A and B is
   • a) Countable b) Uncountable
   • C) Finite d) None of these
   • vii) A student 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
   • c) 14 d) None of these
   • ix) How many solutions are there to the equation x; + x, + %3 + X4 = 17 have, where and x4 are non negative integers ? C(21,3) d) None of these
   • x) Ata party there are n men and n women. In how many ways can the n women choose male partners for the dance?
   • c) (n—2)! d) None of these
2. Q2 Attempt any ONE question from the following : 8 marks
   • a) Show that if the characteristic equation x* — — of the recurrence relation = hasa single root then the explicit formula is li. Prove that Product of two disjoint cycles is commutative
   • b) Attempt any TWO question from the following : 12
   • i. Define an even permutation. Express = Sg asa product of disjoint cycles. Determine whether g is odd or even, li. Define signature of a permutation. If o is any permutation in S,, then show that the sign of a is +1, the recurrence relation = —
   • iv. A bank pays 8% interest each year on money in the savings account. F ind the recurrence relation for the amounts a person would have after n years if it follows the investment strategy of 4a) investing 1000 and leaving it in the bank for n
   • (b) investing 1000 at the end of each years
3. Q3 Attempt any ONE question from the following : 8 marks
   • a) i. Show that the interval [0,1] is uncountable,
   • ii. Define Stirling number S(n, k) of second kind. Prove that
   • b) Attempt any TWO question from the following : 12
   • i. Letnandkbe Positive integers. Show that the number of surjective functions from an n- set to a k-set is equal to where S(n, k) is Stirling number of second li. Pigeonhole Principle. There are 60 rooms and 1000 students of particular class ina college. Show that at least one class has at least 17 students, ili. Addition and Multiplication principle. How many different four letters initials can people have? Also find how many of them have no repetition in their initials?
   • iv. 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 (but the first letter is a K or W) How many of the 4- letter call letters (starting with K or W) with no repeats end
4. Q4 Attempt any ONE question from the following : 8 marks
   • a) i, Prove by giving combinatorial argument: ( ( = ( li. Define Eulerg function. Let n > 2 be an integer whose prime factorization is N= where e; > 1,Vi,1 <j ST, prove that
   • b) Attempt any TWO question from the following : and Prove Binomial Theorem multiset with objects of k different types each with an infinite repetition number (multiplicity), Show that the number of r- combinations of S equals ili. Define Derangement D,,. Show that Dyn = + D, = Oand 12
   • iv. the coefficient of x*yz? in the expansion of (2x — 3y + Also find the numbers of terms and sum of all the coefficients in the expansion,
5. Q5 Attempt any FOUR question from the following : 20 marks
   • a) Define Even permutation. Prove that product of two even permutation is even,
   • b) Solve the linear non homogeneous recurrence relation = 3a,_; =3
   • c) Prove by Mathematical induction S(n,n — 1) ={ )n>2
   • d) Prove that if seven distinct numbers are selected from 1} ,thentwo of these numbers sum to 12,
   • e) How many 11 letter words can be made from the letters of the word MISSISSIPP]?
   • f) How many solutions does the equation %1 = 20 have, in which

Read from the scan above, so a character or two may differ. The scan is the original.