Discrete Mathematics - Mid Sem (Sem 2)
1. Let
be equivalence
relations on the set X. Are R1∩R2
and R1 U R2 necessarily equivalence relations?
2. Show that in a set of people, there are 2 members who
have the same number of friends.
3. Consider a 3 x 3 square board filled with numbers from
the set {1,2..,9} in a natural way, that is, row-wise. Suppose the square board
is rotated clockwise by 90 degrees. Write down the cyclic representation of the
permutation of the numbers induced by this operation. Repeat the exercise for
the reflection along the main diagonal.
4. What is the generating function for the sequence (12,
22, 32, ...) ?
5. Let bn denote the total number of partitions of a set
with n elements. Show that:
6. Let qn be the number of words of length n in the
alphabet {a,b,c,d} which contain an odd number of b's. Show that for n
≥ 1, qn+1 = 4n + 2qn. Find a generating
function Q(x) for (qn) assuming q0=0 and show that:
7. Write down the generating
function of the sequence whose nth term is the number of partitions of the
integer n in which no even number occus more than once as a part. Hence show
that this number is equal to the number of partitions of the integer n in which
each part occurs at most 3 times. (Hint: (1 - x4) = (1 - x)(1 + x + x2
+ x3). )
8. (a) Show
that the number of partitions of an integer n into exactly k parts, pk(n),
satisfies:
(b)
For a fixed k, find the generating function for (pk(n))