LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

AB 24

   B.Sc. DEGREE EXAMINATION – MATHEMATICS

FIFTH SEMESTER – November 2008

MT 5402 – COMBINATORICS

 

 

 

Date : 14-11-08                     Dept. No.                                        Max. : 100 Marks

Time : 9:00 – 12:00

SECTION-A

 

ANSWER ALL THE QUESTIONS:                                                                 (10×2 = 20)

 

1. Define Stirling number of second kind. Find
2. How many ways can one move from (0,0,0 ) to (a,b,c).
3. Find per .
4. Find the cycle of length 1, length 3 and length 4 for the permutation                                                     1 2 3 4 5 6 7 8  3 2 5 1 4 8 6 7 .
5. Define Ordinary generating function.
6. Define Ferrers graph.
7. Find the Rook polynomial for the chess board C in the diagram below,

 

 

 

 

 

 

8. Define Euler’s function.
9. Define derangement using Sieve’s formula.
10. Define cycle index of a permutation group.

 

SECTION-B

ANSWER ANY FIVE QUESTIONS:                                                                 (5×8 = 40)

 

11. An executive attending a week long business seminar has five suits of different colours. On Mondays, she does not wear blue or green, on Tuesdays, red or green, on Wednesdays, blue, white or yellow, on Fridays, white. How many ways can she dress without repeating a colour during the seminar?

 

12. Prove that the element f of R [t ] given by f(t) = has an inverse in R[t] if and only if has an inverse in R.

 

13. Prove that the cardinality of the set of permutations of m symbols taken n at a time is m(m-1) (m-2)……..(m-n+1).

 

14. State and prove Multinomial theorem .

 

15. (i) An examination paper with 10 questions consists of 6 questions in algebra and 4 questions in geometry. At least 1 question from each section is to be attempted. In how many ways can this be done?

(ii) Find the number of ways of selecting 4 letters from the word EXAMINATION.       (5+3)

 

 

 

16. (i) Define exponential generating function.

(ii) How many permutations can be formed from the two symbols and  with the added condition that  may occur at most twice and  may occur at most once. Illustrate the problem using exponential generating function.

(3+5)

17. If the number of permutation in of type (λ) = , then show that .

 

18. Describe the following Symmetric functions with an example

(a) Monomial (b) Complete homogenous (c) Elementary.

 

SECTION-C

ANSWER ANY TWO QUESTIONS                                                                (2×20 = 40)

 

19. (i) If there exists a bijection between the set of n-letter words with distinct letters out of an alphabet of m letters and the set of n-tuples on m letters, without repetitions. Show that the cardinality of each of these sets is

m(m-1)(m-2)…(m-n+1).

(ii) Define increasing and strictly increasing of a word. Also prove that there  exists a bijection between the set of increasing words of length n on m ordered letters, and the set of distributions on n non-distinct objects into m distinct boxes.

(10+10)

 

20. (i) In how many ways can a total of 16 be obtained by rolling 4 dice once?

(ii) Define a partition for the integer n. Give the recurrence formula for . Tabulate the values of for n, m = 1,2,3…7                                         (8+12)

 

21. (i) State and prove Generalized Inclusion and Exclusion principle.

(ii) With proper illustrations describe the problem of Fibonacci.

(10+10)

 

22. State and prove Burnside’s lemma.

 

 

Go To Main Page

LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

AB 15

   B.Sc. DEGREE EXAMINATION – MATHEMATICS

FIFTH SEMESTER – November 2008

MT 5406 – COMBINATORICS

 

 

 

Date : 14-11-08                     Dept. No.                                        Max. : 100 Marks

Time : 9:00 – 12:00

 

SECTION A

ANSWER ALL THE QUESTIONS:                                                                                (10×2 = 20 )

 

1. Define Binomial number.
2. Define Bell number.
3. Find the Ordinary generating function and Ordinary enumerator for the combinations of five symbols a, b, c, d, e.
4. Give all the partitions for 6.
5. Draw the Ferrers graph for λ = (764332). Also find λ.
6. Define h_λ and find h₄.
7. Prove that = pⁿ.
8. Find per .
9. Define derangement and deduce the formula for it using Sieve’s formula.
10. Define weight of a function.

 

SECTION B

ANSWER ANY FIVE QUESTONS:                                                                                (5×8 = 40 )

 

11. Give the recurrence formula for. Tabulate the values of for n, m = 1,2, …, 6.

 

12. Show that there exists a bijection between the following two sets:

(a) The set of n-tuples on m letters without repetition.

(b) The set of injections of an n-set into an m-set.

Prove that the cardinality of each of these sets is m (m-1) (m-2) … (m-n+1).

 

13. Prove that the elements f of R[t] given by f =has an inverse in R[t] if and only if  has an inverse in R.

 

 

14. Let n be a positive integer. Show that the Ordinary Enumerator,

• for the partitions of n is F(t) = .
• for the partitions of n into precisely m parts is .
• for the partitions of n into parts all of which are odd is .

15. Describe the monomial symmetric function and the elementary symmetric function with

an example.

 

16. State and prove Generalized inclusion and exclusion principle.
17. Define a rook polynomial. Prove with usual notation that R(t,) = t R(t, ) + R(t,).

 

18. List 6 elements of the group of rotational symmetries of a regular hexagon and their

types.

 

SECTION C

ANSWER ANY TWO QUESTIONS:                                                                              (2×20 = 40)

 

19. (i) Prove that number of distributions on n distinct objects into m distinct boxes with the

objects in each box arranged in a definite order is .

(ii) Define the combinatorial distribution with an example.

(15+5)

20. Explain in detail about the power sum symmetric functions.
21. (i) How many permutations of 1, 2, 3, 4 are there with 1 not in the 2^nd position, 2 not in

the 3^rd position, 3 not in the 1^st or 4^th position and 4 not in  the 4^th position.

(ii) Prove with the usual notation that.

(10+10)

22. State and prove the Burnside’s lemma.

 

 

Go To Main Page