Basic combinatorics — basic enumeration

I. Basic Enumeration:

There is no rule which says that enumeration problems, even the simplest ones, must have solutions expressible as closed formulas. Some have, of course, and one important thing to be learnt here is how to recognize such problems. Another approach, avoiding the difficulty of trying to produce a closed formula, is to look for “substitute” solutions in other forms such as formulae involving summations, recurrence relations or generating functions. A typical (but not unique or universal) technique for solving an enumeration problem, in one or more parameters, is to find a recurrence relation, deduce a formula for the generating function (the recurrence relation is usually equivalent to a differential equation involving this function) and finally, where possible, to obtain the coefficients in the Taylor expansion of the generating function.

However, it should be pointed out that, in many cases, elementary transformations of the problems may lead to another problem already solved. For example, it may be possible by such transformations to represent each element to be counted as the result of n consecutive decisions such that there are a_{i} possible choices at the ith step. The answer would then be a_{1}a_{2}a_{3}\ldots a_{n}. This is particularly useful when each decision if independent of all the previous decisions. Finding such a situation equivalent to the given problem is usually difficult and a matter of luck combined with experience.

1) In a shop there are k kinds of postcards. We want to send postcards to n friends. How many different ways can this be done? What happens if we want to send them different cards? What happens if we want to send two different cards to each of them(but different persons may get the same card)?

Hint:

Decide about the persons one by one.

Solution:

I. i.

The first person may be sent any of the k kinds of postcards. No matter which one he is sent, we may still send the second one any of the k kinds, so there are k \times k = k^{2} ways to send cards to the first two friends. Again, whatever they are sent, the third friend can still be sent k kinds, etc. So there are k^{n} ways to send out the cards.

I.ii

If they have to be sent different cards, the first person can still be sent any of the k cards. But for any choice of this card, there are only k-1 kinds of cards left for the second person, whatever the first and second friends receive the third one can get one of k-2 postcards, etc…Thus, the number of ways to send them postcards is

k(k-1)\ldots(k-n+1) (which is, of course, 0 if n > k).

I. iii.

This is the same as the first question but we have {k \choose 2} pairs of postcards instead of k postcards. Thus the result is ({k \choose 2})^{2}.

More later,

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: