A word about basic enumeration

Reference: Combinatorial Problems and Exercises, Second Edition, Laszlo Lovasz, AMS Chelsea Publishing, Indian Edition, available Amazon India.

There is no rule which says that enumeration problems even the simplest ones, must have solutions expressible as closed formulas/formulae. 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 formulas 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 a n consecutive decisions such that there are a_{i} possible choices at the ith step. The answer would then be a_{1}a_{2} \ldots a_{n}. This is particularly useful when each decision is 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 expressions.

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.