Combinatorics — DU B.A. (Prog) Mathematics as Major Previous Year Question Papers

1. (a) There are 7 books of Hindi, 3 books of English and 9 books of German. All books are different. How many ways are there to pick an (unordered) pair of two books not both in the same language? (b) How many different 9-digit binary sequences are there with six l's and three O's? (c) A committee has to be formed from eight women and five men. In how many ways can the committee be formed if it must contain equal numbers of women and men, and the committee can be of any positive size? 2. (a) In bridge, the 52 cards of a standard deck are randomly dealt 13 each to four players. What is the probability that one specific player has all 13 (b) If a fair coin is flipped 11 times, what is the probability of 9 or more heads? (c) Prove that the number of derangements D, on n letters is given by 3. (a) Find an exponential generating function for the number of distributions of r distinct objects into n different boxes with exactly m nonempty boxes. (b) Build a generating function for a, the number of integer solutions to the equation: e1 tez test eat este=r, 0 ≤ e, ≤ 6. (c) Verify the binomial identity 4. (a) 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 a, the number of different ways for the elf to ascend the n-stair staircase. (b) Solve the recurrence relation a = 3an-1 - 2an-2 with initial conditions a = a, = 1. (c) Find functional equation for the generating function whose coefficients satisfy the following relation: 5. (a) Find the coefficient of xl2 in (b) Define a partition of a positive integer n into k parts. Write the set of all partitions of 7. Hence, deduce the value of p(7). (c) Define the conjugate of a partition a = (ay, a2..... ap. Find the conjugate of the partitions r, = (9,4,4) 6. (a) Show that Pall part partitions (x) = 11(1-xl) 1 (b) Define Ferrers Diagram. Write any two partitions of 12 into 5 parts and draw their corresponding Ferrers diagram. (c) Show that for any m e Zt, Durfee Square Dm is also a Ferrers Diagram of some partition. Draw the Ferrers Diagram of the partition n = (10, 5, 5, 3, 2, 2, 1) and highlight the Durfee Square in the same.