Combinatorics — DU B.Sc. (Prog) Physical Sciences courses pertaining to Mathematical Sciences Previous Year Question Papers

Q1. (a) How many non-empty different collections can be formed from 6 identical bananas and 7 identical mangoes? (b) How many ways are there to arrange the seven letters in the word SUCCESS? In how many of these arrangements do the two Cs appear together? (c) If there are n objects, with ry of type 1, r2 of type 2,..., and rm of type m, where r1 + 72+. + Tm = n, then prove that the number of arrangements P(n; 71, "2...,"m) of these n objects is given by Qz. (a) In bridge, the 52 cards of a standard card deck are randomly dealt 13 apiece to four players. What is the probability that each player has one Ace? (b) Let M be a multi-set with r distinct objects X1, X2,..., X, each with infinite multiplicity. Let C (r, k) denote the number of k-combinations of M. Then, prove that (c) Let X be a finite set and let Pi; i = 1,2,.., n be a set of n properties satisfied by (some of the elements of X. Let A_i denote the set of those elements of X that satisfy the property Pj. Show that the size of the set A, nAz n ...n An of all those elements that do not satisfy any one of these properties is given by Q3. (a) Find a generating function for modelling the number of distributions of 16 chocolate bunny rabbits into four Easter baskets with at least three rabbits in each basket. Which coefficient do we want? (b) How many ways are there to select 25 toys from seven types of toys with between two and six of each type? (c) Define exponential generating function. Find the number of different r arrangements of objects chosen from unlimited supplics of n types of objects. Q4. (a) Find and solve a recurrence relation for the number of matches played in a tournament with z players, where n is a power of 2. (b) Find a formula for an satisfying the relation an + 2an-z+ an-4 = 0 with initial condition ao = 0, a1 = 1, a2 = 2 and a3 = 3. (c) Find a functional equation for g(x) =do+a,x+azx?+...+anx"+... where an satisfies the recurrence relation an = n + an-1 for all n ≥ 1. Os. (a) An elf has a staircase of n stairs to climb. Each step it takes can cover either one or two or three stairs. Find a recurrence relation for an, the number of different ways for the elf to ascend the n stairs. (b) For a natural number n, let p(n) denote the number of partitions of n. Then find p(5) (c) Define the conjugate of a partition t = (a1,02,., k). Find the conjugate of the partitions 71 = (10,5, 5, 3, 2, 2,1) and 11z = (7,5,4,2, 1, 1). Q6. (a) Show that Pall part partitions (x) = 1(1 -x/) (b) Define Ferrers Diagram. Which of the following is/are Ferrers Diagrams? Give Reasons. Also, draw Ferrers diagram for the partition t = (4, 3, 3, 2, 1). (c) Define Durfee Square of Ferrers Diagram. Show that for any m E ZIt, Durfee Square Dm is also a Ferrers Diagram of some partition. Draw the Ferrers Diagram of the partition т = (10,5,4,3,3,3,3, 2) and highlight the Durfee Square in the same.