More tough combinatorics tutorial for RMO: continued

Practice. Practice. Practice.

1) In how many ways, can a total of 16 be obtained by rolling 4 dice once?

2) Calculate the coefficient of t^{12} in (\frac{1-t^{6}}{1-t})^{4}.

3) Observe the identity of answers to Problem 1 and 2. If you think it is a mere coincidence, experiment with other numbers in place of 16 and 4. If you do not think it is a mere coincidence, explain it and go to Problem 4. If you cannot explain its identity, experiment with other numbers.

4) Express the number N(n,p) of ways of obtaining a total of n by rolling p dice, as a certain coefficient in a suitable product of binomial expansion in powers of t. If you cannot do this problem, go to problem 3.

5) Verify that the number of increasing words of length 10 out of the alphabet (a,b,c,d,e) with a<b<c<d<e is the coefficient of t^{10} in (1-t)^{-5}. Try to explain why this is so.

6) A child has a store of toy letters consisting of 4 A's, 3 B's, and 2 E's. (6a) How many different increasing four-letter words (given A<B<E) can it make? The child does not worry about the meanings of the words. (6b) Show that there exists a bijection between the set of increasing four-letter words of all possible lengths and the set of terms of the expansion (1+A+A^{2}+A^{3})(1+B+B^{2}+B^{3})(1+E+E^{2}). (6c) Can you obtain the answer to (6a) as certain numerical coefficient in a suitable expansion of products?

7) The Parliament of India, in which there are n parties represented, wants to form an all-party committee (meaning, a committee in which there is at least one member from each party) of r \geq n members. Assuming (a) that there exist sufficient members available for the committee in each party and (b) that the members of each party are indistinguishable among themselves(!), find the number of distinct ways of forming the committee. Show that this number may be expressed as a suitable coefficient in the binomial expansion of (1-t)^{n-r}

8) Find the number N of permutations of the multiset (a,a,b,b,b) taken three at a time. If you have to express N as the coefficient t^{3} or t^{3}/3! or 3!t^{3} (the choice is yours) in the expansion of one of
8a) (1+t)^{2}(1+t)^{3}
8b) (1+t)^{-2}(1+t)^{-3}
8c) (1+t+t^{2})(1+t+t+t^{2})
8d) (1+t+\frac{t^{2}}{2!})(1+t+\frac{t^{2}}{2!}+\frac{t^{3}}{3!})

which one would you choose? Can you justify your choice without using the value of N?

9) A family of 3, another family of 2, and two bachelors go for a joy ride in a giant wheel in which there are three swings A, B, C. In how many ways can they be seated in the swings (assuming there are sufficient number of seats in each swing) if the families are to be together? List all the ways.

10) n lines in a plane are in general position, that is, no two are parallel and no three are concurrent. What is the number of regions into which they divide the plane?

11) If (a_{n}) is a sequence of numbers satisfying a_{n}-na_{n-1}=-(a_{n-1}-(n-1)a_{n-2}), find a_{n}, given that a_{0}=1 and a_{1}=0.

12) If a_{n} is the number of ways in which we can place parentheses to multiply the n numbers x_{1}, x_{2}, \ldots, x_{n} on a calculator, find a_{n} in terms of the a_{k}‘s where k=1,2, \ldots, (n-1).

13) A graph G=G(V,E) is a set V of vertices a, b, c, \ldots, together with a set E=V \times V of edges (a,b), (a,a), (b,a), (c,b), \ldots. If (x,y) is considered the same as (y,x), we say this graph is undirected. Otherwise, the graph is said to be directed, and we say ‘(a,b) has a direction from a to b’. The edge (x,x) is called a loop. The graph is said to be of order |V|.

If the edge-set E is allowed to be a multiset, that is, if an edge (a,b) is allowed to occur more than once (and this may be called a ‘multiple edge’), we refer to the graph as a general graph.

\phi_{5}(n) and \psi_{5}(n) denote the numbers of undirected (respectively,directed) loopless graphs of order 5, with n edges, none of them a multiple edge, find the series \sum \phi_{5}(n) t^{n} and \sum \psi_{5}(n) t^{n}.

Cheers,
Nalin Pithwa.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.