Bhavnagar University 2007 M.Sc Mathematics DISCRETE AND COMBINATORIAL - Question Paper

M.Sc. DEGREE EXAMINATION, DECEMBER 2007.
Mathematics
DiscRETE AND COMBINATORIAL MATHEMATICS
Time : 3 hours Maximum : 100 marks
ans any 5 ques..
All ques. carry equal marks.
1. (a) Prove the identity

in 2 ways.
(b) Find the numbers of r-digit quaternary sequences that contain an even number of 0’s.
2. (a) Solve the difference formula : .
(b) Find the number of n-digit binary sequences that have exactly r pairs of adjacent 1’s and no adjacent 0’s.
3. (a) Find the number of integers ranging from one and 250 that are not divisible by any of the integers 2, 3, five and 7.
(b) Define derangement. obtain the number of derangements of n objects.
4. (a) In how many ways can the letters be organizes so that all the letters of the identical type are not in the single block?
(b) Explain the permutations with forbidden positions. describe hit polynomial and find a formula for it.
5. (a) Find the number of distinct strings of length two that are made up of blue beads and yellow beads.
(b) Find the number of all possible ways of painting 3 distinct balls in solid colors when there are 3 types of paint available, an expensive type of red paint, a cheap type of red paint, and a blue paid.
6. (a) Show that the number of equivalence classes of functions from to is provided by where is the number of functions of which are such that for all in .
(b) Show further that the above number is the value of the expression evaluated at .
7. (a) Show that the lattice is modular but not distributive and that is not modular.
(b) Show that a lattice is distributive if and only if it has no sublattices isomorphic to or
8. (a) Define Boolean expressions, Minterm, maxterm, Hasse diagram and Canonical forms.
(b) Find the dual canonical form of the function

Earning:   Approval pending.