(These set of problems and solutions are due Laszlo Lovasz, “Combinatorial Problems and Exercises, AMS-Chelsea Publishing:

**Problem 1) **

Prove the identity:

when and is if .

**Proof: **

*Some basics of the inclusion-exclusion principle are in order (by the way, this is also known as the sieve theory, named after the Sieve of Eratosthenes):*

One powerful tool in the theory of enumeration as well as in prime number theory is the inclusion-exclusion principle (sieve of Eratosthenes). This relates the cardinality of the union of certain sets to the cardinalities of intersection of some of them, these latter cardinalities often being easier to handle. However, the formula does have some handicaps: it contains terms alternating in signs, and in general, it has too many of them!

(a) **The Sieve Formula:**

Let be arbitrary events of a probability space . For each, , let

;

and let ,

Then,

(b) **(Inclusion-Exclusion Principle)**

Let where S is a finite set, and let ; .

Then,

**Solution :**

Let , . Then, the number of those tmappings of X into Y which are onto Y is, obviously,

if , and , if .

On the other hand, let denote the set of mappings of X into and let S be the set of all mappings of X into Y. Then, we are interested in . By the inclusion-exclusion formula:

Here, is the set of mappings of X into , hence,

. So,

which proves the assertion.

If , the result of the same inclusion-exclusion procedure is the number of mappings of X onto Y, which is .

**Problem 2)**

Prove the following Abel identities:

(2a)

**Proof (2a):**

We prove (2a) by induction on n. For , it is trivial. Let . We have

The two right-hand sides here are equal by the induction hypothesis. To prove the identity, it suffices to show that (a) holds for any one value of n. Choose . Then, the right hand side vanishes while the left hand side is

as .

Note: In the last step we have used the following:

.

(2b) **Prove:**

**Proof:**

The left hand side of (2a) can be rewritten as

Here, the second term is

by 2a. Hence,

Dividing by identity (b) follows.

(2c) **Prove:**

**Proof:**

Subtract from both sides of then we get,

Letting , we obtain (c).

**Problem 3:**

Let . Prove that . Find other examples of such equations of polynomials.

**Proof: TBD.
**

**Problem 4:**

**Proof: TBD.**

**Problem 5:**

The number of non-congruent triangles with circumference and integer sides is equal to the number of non-congruent triangles with circumference and integer sides. This number is also equal to the number of partitions of n into exactly three terms. Determine this number.

**Proof:**

The first assertion is easy. If integers a, b, c are the sides of a triangle with circumference , then trivially also satisfy the triangle inequality, and so they are the sides of a triangle with circumference . Conversely, if a, b, c are the sides of a triangle with circumference , then

and since, is odd, we have

Hence, , , are the sides of a triangle with circumference .

To prove the second assertion, observe that if , where x, y, z are positive integers, then

, that is, are the sides of a triangle with circumference 2n. Conversely, if integers a, b, c are the sides of such a triangle then, setting , we have

, , and also

.

Thus, we have a one-to-one correspondence between partitions of n and triangles with circumference (and integer sides).

To determine the number of partitions of n into exactly three terms we observe first that the number of partitions of m into exactly two terms not exceeding a is

, when

when ,

, if .

Hence, the number of partitions , where is

or equivalently,

It is seen that the result depends on the residue of n mod 6, example, if , then the result is .

More conundrums coming soon …!

Nalin Pithwa