(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