Math concept(s) : simple yet subtle

Posted by nkpithwa

Most math concepts are intuitive, simple, yet subtle. A similar opinion is expressed by Prof. Michael Spivak in his magnum opus, Differential Geometry (preface). It also reminds me — a famous quote of the ever-quotable Albert Einstein: “everything should be as simple as possible, and not simpler.”

I have an illustrative example of this opinion(s) here:

Consider the principle of mathematical induction:

Most students use the first version of it quite mechanically. But, is it really so? You can think about the following simple intuitive argument which when formalized becomes the principle of mathematical induction:

Theorem: First Principle of Finite Induction:

Let S be a set of positive integers with the following properties:

The integer 1 belongs to S.
Whenever the integer k is in S, the next integer $k+1$ must also be in S.

Then, S is the set of all positive integers.

The proof of condition 1 is called basis step for the induction. The proof of 2 is called the induction step. The assumptions made in carrying out the induction step are known as induction hypotheses. The induction situation has been likened to an infinite row of dominoes all standing on edge and arranged in such a way that when one falls it knocks down the next in line. If either no domino is pushed over (that is, there is no basis for the induction), or if the spacing is too large (that is, the induction step fails), then the complete line will not fall.

So, also remember that the validity of the induction step does not necessarily depend on the truth of the statement that one is endeavouring to prove.

More later,

Nalin Pithwa.

Learn hardcore math and programming through games :-) The Game of Nim

Posted by nkpithwa

Reference: Introductory Combinatorics, fourth edition, Richard A. Brualdi

Example : The Game of Nim:

It is a return to the roots of combinatorics —- which does lie in recreational mathematics and we investigate the ancient game of Nim. (Nim derives from the German word Nimml, meaning Take!) Its solution depends on parity, an important problem-solving concept in combinatorics. We can use parity argument in investigations of perfect covers of chessboards when we show that a board has to have an even number of squares in order that it have a perfect cover with dominoes.

Nim is a game played by two players with heaps of coins (or stones or beans or gems or diamonds !!! 🙂 🙂 …).. Suppose that there are $k \geq 1$ heaps of coins that contain, respectively, $n_{1}$ , $n_{2}$ , $\ldots$ , $n_{k}$ coins. The object of the game is to select the last coin. The rules of the game are the following:

i) The players alternate turns (let us call the player who makes the first move I and then call the other player II).

ii) Each player, when it is his or her turn, selects one of the heaps and removes at least one of the coins from the selected heap. (The player may take all of the coins from the selected heap, thereby leaving an empty heap, which is now “out of play.”)

The game ends when all the heaps are empty. The last player to make a move, that is, the player who takes the last coin(s), is the winner.

The variables in this game are the number k of heaps and the numbers $n_{1}$ , $n_{2}$ , $\ldots$ , $n_{k}$ of coins in the heaps. The combinatorial problem is to determine whether the first or second player wins and how that player should move in order to guarantee a win — a winning strategy.

In order to develop some understanding of Nim, we consider some special cases. (This is an important principle to follow in general: Consider small or special cases in order to develop understanding and intuition. Then try to extend your ideas in order to solve the problem in general.) If there is initially only one heap, then player 1 wins by removing all its coins. Now, suppose that there are $k=2$ heaps, with $n_{1}$ , and $n_{2}$ coins, respectively. Whether or not player I can win depends not on the actual values of $n_{1}$ and $n_{2}$ but on whether or not they are equal. Suppose that $n_{1} \neq n_{2}$ . Player I can remove enough coins from the larger heap in order to leave two heaps of equal size for player II. Now player I, when it is her turn, can mimic player II’s moves. Thus, if player II takes c coins from one of the heaps, then player I takes the same number c of coins from the other heap. Such a strategy guarantees a win for player I. If $n_{1}=n_{2}$ , then player II can win by mimicking player I’s moves. Thus, we have completely solved 2-heap Nim. An example of play in the 2-heap game of Nim with heaps of sizes 8 and 5, respectively, is

$8, 5 \stackrel{I}\rightarrow 5,5 \stackrel{II}\rightarrow 5,2 \stackrel{I}\rightarrow 2,2 \stackrel{II}\rightarrow 0,2 \stackrel{I}\rightarrow 0,0$

The preceding idea in solving 2-heap Nim, namely, moving in such a way as to leave two equal heaps, can be generalized to any number k of heaps. The insight one needs is provided by the concept of the base 2 numeral of an integer. Recall that each positive integer n can be expressed as a base 2 numeral by repeatedly removing the largest power of 2 which does not exceed the number. For instance, to express the decimal number 57 in base 2, we observe that

$2^{6} \leq 57 < 2^{6}$ , $57-2^{5}=25$ ,

$2^{4} \leq 25 < 2^{5}$ , $25-2^{4}=9$ ,

$2^{3} \leq 9 < 2^{4}$ , $9-2^{3}=1$ ,

$2^{0}\leq 1 <2^{1}$ , $1-2^{0}=0$ .

Thus, $57=2^{5}+2^{4}+2^{3}+2^{0}$ ,

and the base 2 numeral for 57 is 111001.

Each digit in a base 2 numeral is either 0 or 1. The digit in the ith position, the one corresponding to $2^{i}$ , is called the ith bit ( $i \geq 0$ ). We can think of each heap of coins as consisting of subheaps of powers of 2, according to its base numeral. Thus, a heap of size 53 consists of subheaps of sizes $2^{5}$ , $2^{4}$ , $2^{2}$ , and $2^{0}$ . In the case of 2-heap Nim, the total number of subheaps of each size is either 0, 1, or 2. There is exactly one subheap of a particular size if and only if the two subheaps of each size is even if and only if the two heaps have the same size — that is, if and only if, player II can win the Nim game.

Now, consider a general Nim game with heaps of sizes $n_{1}$ , $n_{2}$ , $\ldots$ , $n_{k}$ . Express each of the numbers $n_{i}$ as base 2 numerals:

$n_{1}=a_{s}\ldots a_{1}a_{0}$

$n_{2}=b_{s}\ldots b_{1}b_{0}$

$\ldots$

$n_{k}=e_{s}\ldots e_{1}e_{0}$

(By including leading 0’s we can assume that all of the heap sizes have base 2 numerals with the same number of digits.) We call a Nim game balanced, provided that the number of subheaps of each size is even. Thus, a Nim game is balanced if and only if:

$a_{s}+b_{s}+\ldots + e_{s}$ is even,

$\vdots$

$a_{i}+b_{i}+\ldots + e_{i}$ is even,

$\vdots$

$a_{0}+b_{0}+\ldots + e_{0}$ is even,

A Nim game that is not balanced is called unbalanced. We say that the ith bit is balanced, provided that the sum $a_{i}+b_{i}+\ldots + e_{i}$ is even, and is unbalanced otherwise. Thus, a balanced game is one in which all bits are balanced, while an unbalanced game is one in which there is at least one unbalanced bit.

We then have the following:

Player I can win in unbalanced Nim games, and player II can win in balanced Nim games.

To see this, we generalize the strategies used in 2-pile Nim. Suppose the Nim game is unbalanced. Let the largest unbalanced bit be the jth bit. Then, player I moves in such a way as to leave a balanced game for player II. She does this by selecting a heap whose jth bit is 1 and removing a number of coins from it so that the resulting game is balanced. No matter what player II does, she leaves for player I an unbalanced game again, and player I once again balances it. Continuing like this ensures player I a win. If the game starts out balanced, then player I’s first move unbalances it, and now player II adopts the strategy of balancing the game whenever it is her move.

For example, consider a 4-pile Nim game with heaps of sizes 7,9, 12 and 15. The base 2 numerals for these heap sizes are, respectively, 0111, 1001, 1100, and 1111. In terms of subheaps of powers of 2 we have:

$\begin{array}{ccccc} \emph{4-pile Nim game} & 2^{3}=8 & 2^{2}=4 & 2^{1}=2 & 2^{0}=1 \\ \emph{heap of size 7} & 0 & 1 & 1 & 1 \\ \emph{heap of size 9} & 1 & 0 & 0 & 1 \\ \emph{heap of size 12} & 1 & 1 & 0 & 0 \\ \emph{heap of size 15} & 1 & 1 & 1 & 1 \\ \end{array}$

This game is unbalanced with the 3rd, 2nd, and 0th bits unbalanced. Player I can remove 11 coins from the pile of size 12, leaving 1 coin. Since the base 2 numeral of 1 is 0001, the game is now balanced. Alternatively, player I can remove 5 coins from the pile of size 9, leaving 4 coins, or player I can remove 13 coins from the pile of size 15, leaving 2 coins.

A quiz:

Consider 3-heap Nim with piles of sizes 1, 2 and 4. Show that this game is unbalanced and determine a first move for player I.
Is 4-pile Nim with heaps of sizes 22, 19, 14, and 11 balanced or unbalanced? Player I’s first move is to remove 6 coins from the heap of size 19. What should player II’s first move be?
Consider 5-pile Nim with heaps of sizes 10, 20, 30, 40, and 50. Is this game balanced? Determine a first move for player I.

Have fun with math games !

Cheers,

Nalin Pithwa.

Some elegant applications of the Pigeonhole Principle

Posted by nkpithwa

Reference: Discrete Mathematics and its Applications by Kenneth H. Rosen, Seventh Edition.

In many interesting applications of the pigeonhole principle, the objects to be placed in boxes must be chosen in a clever way. A few such applications will be described here.

Example 1:

During a month with 30 days, a baseball team plays at least one game a day, but no more than 45 games. Show that there must be a period of some number of consecutive days during which the team must play exactly 14 games.

Solution 1:

Let $a_{j}$ be the number of games played on or before the jth day of the month. Then, $a_{1}, a_{2}, \ldots, a_{30}$ is an increasing sequence of distinct positive integers, with $1 \leq a_{j} \leq 45$ . Moreover, $a_{1}+14, a_{2}+14, \ldots, a_{30}+14$ is also an increasing sequence of distinct positive integers, with $15 \leq a_{j} + 14 \leq 59$ .

The 60 positive integers $a_{1}, a_{2}, \ldots, a_{30}, a_{1}+14, \ldots, a_{30}+14$ are all less than or equal to 59. Hence, by the pigeonhole principle two of these integers are equal. Because the integers $a_{j}$ , $j=1, 2, \ldots, 30$ are all distinct, there must be indices i and j with $a_{i}=a_{j}+14$ . This means that exactly 14 games were played from day $j+1$ to i.

Example 2:

Show that among any $n+1$ positive integers not exceeding 2n there must be an integer that divides one of the other integers.

Solution 2:

Write each of the $n+1$ integers $a_{1}, a_{2}, \ldots, a_{n+1}$ as a power of 2 times an odd integer. In other words, let $a_{j} = 2^{k_{j}}q_{j}$ for $j=1, 2, 3 \ldots n+1$ , where $k_{j}$ is a nonnegative integer and $q_{j}$ is odd. The integers $q_{1}, q_{2}, \ldots, q_{n+1}$ are all odd positive integers less than 2n. Because there are only n odd positive integers less than $2n$ , it follows from the pigeonhole principle that two of the integers $q_{1}, q_{2}, \ldots, q_{n+1}$ must be equal. Therefore, there are integers i and j such that $q_{i} = q_{j}$ . Let q be the common value of $q_{i}$ and $q_{j}$ . Then, $a_{i}=2^{k_{i}}q$ and $a_{j}=2^{k_{j}}q$ . It follows that if $k_{i}<k_{j}$ then $a_{i}$ divides $a_{j}$ . QED.

A clever application of the pigeonhole principle shows the existence of an increasing or a decreasing subsequence of a certain length in a sequence of distinct integers. Some definitions will be reviewed before this application is presented. Suppose that $a_{1}, a_{2}, a_{3}, \ldots, a_{n}$ is a sequence of real numbers. A subsequence of this sequence is a sequence of the form $a_{1_{1}}, a_{i_{2}}, \ldots, a_{i_{n}}$ , where $1 \leq i_{1} < i_{2} < ldots < i_{n} \leq N$ . Hence, a subsequence is a sequence obtained from the original sequence by including some of the original sequence in their original order, and perhaps, not including other terms. A sequence is called strictly increasing if each term is larger than the one that precedes it, and it is called strictly decreasing if each term is smaller than the one that precedes it.

Theorem:

Every sequence of $n^{2}+1$ distinct real numbers contains a subsequence of length $n+1$ that is either strictly increasing or strictly decreasing.

An example is presented below (before the proof) of the above:

Example:

The sequence $8, 11, 9, 1, 4, 6, 12, 10, 5, 7$ contains 10 terms. Note that $10=3^{2}+1$ . There are four increasing subsequence of length four, namely, $1, 4, 6, 12; 1, 4, 6, 7; 1, 4, 6, 10; 1, 4, 5, 7$ . There is also a decreasing subsequence of length four, namely, $11, 9, 6, 5$ .

The proof of the theorem is presented below:

Let $a_{1}, a_{2}, \ldots, a_{n^{2}}+1$ be a sequence of $n^{2}+1$ distinct real numbers. Associate an ordered pair with each term of the sequence, namely, associate $(a_{k},d_{k})$ to the term $a_{k}$ , where $i_{k}$ is the length of the longest increasing subsequence starting at $a_{k}$ , and $d_{k}$ is the length of the longest decreasing subsequence starting at $a_{k}$ .

Suppose that there are no increasing or decreasing subsequences of length $n+1$ . Then, $i_{k}$ and $d_{k}$ are both positive integers less than or equal to n, for $k=1, 2, \ldots, n^{2}+1$ . Hence, by the product rule there are $n^{2}$ possible ordered pairs for $(i_{k},d_{k})$ . By the pigeonhole principle, two of these $n^{2}+1$ ordered pairs are equal. In other words, there exist terms $a_{s}$ and $a_{t}$ , with $s<t$ such that $i_{s}=i_{t}$ and $d_{s}=d_{t}$ . We will show that this is impossible. Because the terms of the sequence are distinct, either $a_{s}>a_{t}$ or $a_{s}<a_{t}$ . If $a_{s}<a_{t}$ , then, because $i_{s}=i_{t}$ , an increasing subsequence of length $i_{t}+1$ , can be built starting at $a_{s}$ , by taking $a_{s}$ followed by an increasing subsequence of length $i_{t}$ beginning at $a_{t}$ . This is a contradiction. Similarly, if $a_{s}>a_{t}$ , the same reasoning shows that $d_{s}$ must be greater than $d_{t}$ , which is a contradiction. QED.

Quiz based on generalized pigeonhole principle:

Assume that in a group of six people, each pair of individuals consists of two friends or two enemies. Show that there are either three mutual friends or three mutual enemies in the group.

Note: This little quiz is a motivation for Ramsey theory. This theory deals with the distribution of of subsets of elements of sets.

More later,

Nalin Pithwa

The Pigeon Hole Principle — Some notes and examples

Posted by nkpithwa

Reference: Discrete Mathematics and its Applications by Kenneth H. Rosen, Seventh Edition.

The Pigeonhole Principle 1:

If k is a positive integer and $k+1$ or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.

Corollary: A function f from a set with $k+1$ or more elements to a set with k elements is NOT one-to-one.

Example 1:

Among any group of 367 people, there must be at least two with the same birthday because there are only 366 possible birthdays.

Example 2:

In any group of 27 English words, there must be at least two that begin with the same letter because there are 26 letters in the English alphabet.

Example 3:

How many students must be in a class to guarantee that at least two students receive the same score on the final exam, if the exam is graded on a scale from 0 to 100 points?

Solution:

There are 101 possible scores on the final. The pigeon hole principle shows that among any 102 students there must be at least 2 students with the same score.

The pigeonhole principle is a useful tool in many proofs, including proofs of surprising results, such as that given in the example below:

Example 4:

Show that for every integer n there is a multiple of n that has only 0’s and 1’s in its decimal expansion.

Solution 4:

Let n be a positive integer. Consider the $n+1$ integers 1, 11, 111, $\ldots$ , $11\ldots 1$ (where the last integer in this list is the integer with $n+1$ 1’s in its decimal expansion). Note that there are n possible remainders when an integer is divided by n. Because there are $n+1$ integers in this list, by the pigeonhole principle, there must be two with the same remainder when divided by n. The larger of these integers less the smaller one is a multiple of n, which has a decimal expansion consisting entirely of 0’s and 1’s.

The Generalized Pigeonhole Principle:

The pigeonhole principle states that there must be at least two objects in the same box when there are more objects than boxes. However, even more can be said when the number of objects exceeds a multiple of the number of boxes. For instance, among any set of 21 decimal digits, there must be 3 that are the same. This follows because when 21 objects are distributed into 10 boxes, one box must contain more than 2 objects.

Statement of the Generalized Pigeonhole Principle:

If N objects are placed into k boxes, then there is at least one box containing at least $\lceil N/k \rceil$ objects.

Some comments:

Please see wikipedia for properties of ceiling function. You can prove the above theorem by contradiction. Give it a try!

A common type of problem asks for the minimum number of objects such that at least r of these objects must be in one of the k boxes when these objects are distributed among the boxes. When we have N objects, the generalized pigeonhole principle tells us there must be at least r objects in one of the boxes as long as $\lceil N/k \rfloor \geq r$ . The smallest integer N with $N/k > r-1$ , namely, $N=k(r-1)+1$ , is the smallest integer smallest integer satisfying the inequality $\lceil N/k \rfloor\geq r$ . Could a smaller value of N suffice? The answer is no, because if we have $k(r-1)$ objects, we could put $r-1$ of them in each of the k boxes and no box would have at least r objects.

When thinking about problems of this type, it is useful to consider how you can avoid having at least r objects in one of the boxes as you add successive objects. To avoid adding a rth object to any box, you eventually end up with $r-1$ objects in each box. There is no way to add the next object without putting an rth object in that box.

Examples 5-8 illustrate how the generalized pigeonhole principle is applied.

Example 5:

Among 100 people there are at least $\lceil 100/12 \rceil = 9$ who were born in the same month.

Example 6:

What is the minimum number of students required in a discrete mathematics class to be sure that at least six will receive the same grade, if there are five possible grades A, B, C, D, and F?

Solution 6:

The minimum number of students needed to ensure that at least six students receive the same grade is the smallest integer N such that $\lceil N/5 \rceil = 6$ . The smallest such integer is $N= 5.5+1=26$ If you have only 25 students, it is possible for there to be five who have received each grade so that no six students have received the same grade. Thus, 26 is the minimum number of students needed to ensure that at least six students will receive the same grade.

Example 7:

(a) How many cards must be selected from a standard deck of 52 cards to guarantee that at least three cards of the same suit are chosen?

(b) How many must be selected to guarantee that at least three hearts are selected?

Solution 7:

(a) Suppose there are four boxes, one for each suit, and as cards are selected they are placed in the box reserved for cards of that suit. Using the generalized pigeonhole principle, we see that if N cards are selected, there is at least one box containing at least $\lceil N/4 \rceil$ cards. Consequently, we know that at least three cards of one suit are selected if $\lceil N/4 \rceil \geq 3$ . The smallest integer N such that $\lceil N/4 \rceil \geq 3$ is $N=2.4 +1=9$ , so nine cards suffice. Note that if eight cards are selected, it is possible to have two cards of each suit, so more than eight cards are needed. Consequently, nine cards must be selected to guarantee that at least three cards of one suit are chosen. One good way to think about this is to note that after the eighth card is chosen, there is no way to avoid having third card of some suit.

(b) We do not use the generalized pigeonhole principle to answer this question, because we want to make sure that there are three hearts, not just three cards one sort. Note that in the worst case, we can select all the clubs, diamonds, and spades, 39 cards in all, before we select a single heart. The next three cards will be all hearts, so we may need to select 42 cards to get three hearts.

Example 8:

What is the least number of area codes needed to guarantee that the 25 million phones in a state can be assigned distinct 10 digit telephone numbers? (Assume that the telephone numbers are of the form NXX-NXX-XXXX, where the first three digits form the area code, N represents a digit from 2 to 9 inclusive, and X represents any digit).

Solution 8:

There are eight million different phone numbers of the form NXX-XXXX. Hence, by the generalized pigeonhole principle, among 25 million telephones , at least $\lceil 25000000/8000000\rceil$ of them must have identical phone numbers. Hence, at least four area codes are required to ensure that all 10-digit numbers are different.

Quiz Question:

Suppose that a computer science lab has 15 workstations and 10 servers. A cable can be used to directly connect a workstation to a server. For each server, only one direct connection to that server can be active at any time. We want to guarantee that at any time any set of 10 or fewer workstations can simultaneously access different servers via direct connections. Although we could do this by connecting every workstation directly to every server (using 150 connections), what is the minimum number of direct connections needed to achieve this goal?

More later,

Nalin Pithwa.

Solution to an introductory problem in combinatorics

Posted by nkpithwa

This refers to the problems posed in the previous blog HW:

Let A denote the set for which the set $d_{1}d_{2}d_{3}$ is the same as $d_{4}d_{5}d_{6}$ and B denote the set for which $d_{1}d_{2}d_{3}$ is the same as $d_{5}d_{6}d_{7}$ . A telephone number belongs to the set $A \bigcap B$ if and only if all the seven d’s are equal, which can happen in 10 ways only. Hence, $n(A \bigcap B)=10$ . Thus, by the Inclusion-Exclusion Principle, $n(A\bigcup B) = n(A)+n(B)-n(A \bigcap B)= 10^{3}.10.1 +10^{3}.10.1 - 10=19990$ .
I will post this solution in a few days.

Regards,

Nalin Pithwa

Two introductory ptoblems in combinatorics

Posted by nkpithwa

Due: Prof. Titu Andreescu’s 104 Combinatorial Problems from Training of USA IMO Team.

Problem 1:

Call a 7-digit telephone number $d_{1}d_{2}d_{3}-d_{4}d_{5}d_{6}d_{7}$ memorable if the prefix sequence $d_{1}d_{2}d_{3}$ is exactly the same as either of the sequences $d_{4}d_{5}d_{6}$ or $d_{5}d_{6}d_{7}$ (possibly both). Assuming that each $d_{i}$ can be any of the ten decimal digits $0, 1, 2, 3, \ldots, 9$ , find the number of different memorable telephone numbers. (AHSME 1998)

Problem 2:

Two of the squares of a $7 \times 7$ checkerboard are painted yellow and the rest are painted green. Two colour schemes are called equivalent if one can be obtained from the other by a rotation in the plane of the board. How many inequivalent colour schemes are possible? (AIME 1996)

Kindly share your solutions, comments,

Nalin Pithwa

Solutions: Combinatorics conundrums for RMO and INMO practice

Posted by nkpithwa

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

http://www.amazon.in/Combinatorial-Problems-Exercises-Laszlo-Lovasz/dp/0821887084/ref=sr_1_1?s=books&ie=UTF8&qid=1477076752&sr=1-1&keywords=combinatorial+problems+and+exercises )

Problem 1)

Prove the identity:

$\sum_{i=0}^{n}(-1)^{i}{n \choose i}i^{k} = 0$ when $0 \leq k < n$ and is $(-1)^{n}n!$ if $k=n$ .

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 $A_{1}, \ldots, A_{n}$ be arbitrary events of a probability space $(\Omega, P)$ . For each, $I \subseteq \{ 1, \ldots, n\}$ , let

$A_{I} = \prod_{i \in I}A_{i}$ ; $A_{\phi}=\Omega$

and let $\sigma_{k} = \sum_{|I| = k}P(A_{I})$ , $\sigma_{0}=1$

Then, $P(A_{1}+ \ldots + A_{n}) = \sum_{j=1}^{n}(-1)^{j-1}\sigma_{j}$

(b) (Inclusion-Exclusion Principle)

Let $A_{1}, \ldots, A_{n} \subseteq S$ where S is a finite set, and let $A_{I} = \bigcap_{i \in I}A_{i}$ ; $A_{\phi} = S$ .

Then, $|S-(A_{1}\cap \ldots A_{n})|= \sum_{I \subseteq \{ 1, \ldots n\}}(-1)^{|I|}|A_{I}|$

Solution :

Let $|X| = k$ , $Y = \{ y_{1}, \ldots , y_{n}\}$ . Then, the number of those tmappings of X into Y which are onto Y is, obviously,

$0$ if $k < n$ , and $n!$ , if $k=n$ .

On the other hand, let $A_{i}$ denote the set of mappings of X into $Y - y_{i}$ and let S be the set of all mappings of X into Y. Then, we are interested in $S - (A_{1} \bigcap \ldots \bigcap A_{n})$ . By the inclusion-exclusion formula:

$|S-(A_{1}\cap \ldots A_{n})|= \sum_{I \subseteq \{ 1, \ldots n\}}(-1)^{|I|}|A_{I}|$

Here, $A_{I}$ is the set of mappings of X into $Y - \{ y_{i}: i \in I\}$ , hence,

$|A_{I}| = (n-|I|)^{k}$ . So,

$|S- (A_{1} \bigcup \ldots \bigcup A_{n})| = \sum_{j=0}^{n}(-1)^{j}{n \choose j}(n-j)^{k} = \sum_{j=0}^{n}(-1)^{n-j}{n \choose n}j^{k}$ which proves the assertion.

If $k >n$ , the result of the same inclusion-exclusion procedure is the number of mappings of X onto Y, which is $n! \{ \begin{array}{c} k \\ n \end{array}\}$ .

Problem 2)

Prove the following Abel identities:

(2a) $\sum_{k=0}^{n}{n \choose k}x(x+k)^{k-1}(y+n-k)^{n-k} = (x+y+n)^{n}$

Proof (2a):

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

$\frac{\partial}{\partial{y}}(x+y+n)^{n} = n(x+y+n)^{n-1}=n(x+(y+1)+(n-1))^{n-1}$

$\frac{\partial}{\partial{y}}\sum_{k=0}^{n}{n \choose k}x(x+k)^{k-1}y+n-k)^{n-k}$

$= \sum_{k=0}^{n}{n \choose k}x(x+k)^{k-1}(n-k)(y+n-k)^{n-k-1}$

$= n\sum_{k=0}^{n-1}{{n-1} \choose k}x(x+k)^{k-1}((y+1)+(n-1)-k)^{(n-1)-k}$

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 $y = -x-n$ . Then, the right hand side vanishes while the left hand side is

$\sum_{k=0}^{n}{n \choose k}x(x+k)^{k-1}(-x-k)^{n-k}$

$= x \sum_{k=0}^{n}{n \choose k}(-1)^{n-k}(x+k)^{n-1} =$

$= \sum_{j=0}^{n-1}{(n-1) \choose j}x^{n-j}\sum_{k=0}^{n}{n \choose k}k^{j}(-1)^{n-k}=$

$=\sum_{j=0}^{n-1}{{n-1} \choose j}x^{n-j}S(j,n)n!=0$ as $y<n$ .

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

$\{ \begin{array}{c} n \\ k \end{array} \} = \frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}{k \choose j}j^{n}$ .

(2b) Prove:

$\sum_{k=0}^{n}{n \choose k}(x+k)^{k-1}(y+n-k)^{n-k-1}=(\frac{1}{x}+\frac{1}{y})(x+y+n)^{n-1}$

Proof:

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

$\sum_{k=0}^{n}{n \choose k}x(x+k)^{k-1}(y+n-k)^{n-k-1}(y+n-k) =$

$= \sum_{k=0}^{n}{n \choose k}x(x+k)^{k-1}y(y+n-k)^{n-k+1}+ \sum_{k=0}^{n}{n \choose k}x(x+k)^{k-1}(y+n-k)^{n-k-1}(n-k)$

Here, the second term is

$\sum_{k=0}^{n-1}{{n-1} \choose k} x (x+k)^{k-1}((y+1)+(n-1)-k)^{(n-1)-k}$

$= n(x+(y+1)+(n-1))^{n-1} = n(x+y+n)^{n-1}$ by 2a. Hence,

$\sum_{k=0}^{n}{n \choose k}x(x+k)^{k-1}y(y+n-k)^{n-k-1} = (x+y+n)^{n}-n(x+y+n)^{n-1} =$

$= (x+y)(x+y+n)^{n-1}$

Dividing by $xy$ identity (b) follows.

(2c) Prove:

$\sum_{n-1}^{k=1}{n \choose k}k^{k-1}(n-k)^{n-k-1}=2(n-1)n^{n-2}$

Proof:

Subtract $\frac{1}{x}(y+n)^{n-1}+\frac{1}{y}(x+n)^{n-1}$ from both sides of $(b)$ then we get,

$\sum_{k=1}^{n-1}{n \choose k}(x+k)^{k-1}(y+n-k)^{n-k-1} =$

$\frac{1}{x}((x+y+n)^{n-1}-(y+n)^{n-1}) + \frac{1}{y}((x+y+n)^{n-1}-(x+n)^{n-1})$

Letting $x, y \rightarrow 0$ , we obtain (c).

Problem 3:

Let $f_{n}(x) = x(x-1) \ldots (x-n+1)$ . Prove that $f_{n}(x+y) = \sum_{k=0}^{n}{n \choose k}f_{k}(x)f_{n-k}(y)$ . Find other examples of such equations of polynomials.

Proof: TBD.

Problem 4:

Proof: TBD.

Problem 5:

The number of non-congruent triangles with circumference $2n$ and integer sides is equal to the number of non-congruent triangles with circumference $2n-3$ 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 $2n-3$ , then $a+1, b+1, c+1$ trivially also satisfy the triangle inequality, and so they are the sides of a triangle with circumference $2n$ . Conversely, if a, b, c are the sides of a triangle with circumference $2n$ , then

$(a-1)+(b-1)-(c-1) = a +b -c - 1 \geq 0$

and since, $a+b-c-1=2n-2c-1$ is odd, we have

$(a-1)+(b-1)-(c-1) >0$

Hence, $a-1$ , $b-1$ , $c-1$ are the sides of a triangle with circumference $2n-3$ .

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

$(x+y)+(x+z)+(y+z) = 2n$

$(x+y)+(x+z) = y+z + 2x>y+z$ , that is, $x+y, y+z,, x+z$ are the sides of a triangle with circumference 2n. Conversely, if integers a, b, c are the sides of such a triangle then, setting $x=n-a, y=n-b. z = n-c$ , we have

$x = \frac{b+c-a}{2}>0$ , $y>0$ , $z>0$ and also

$x+y=c, x+z=b, y+z =a$ .

Thus, we have a one-to-one correspondence between partitions of n and triangles with circumference $2n$ (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

$0$ , when $a < \frac{m}{2}$