# Science Lives: Laslo Lovasz: Discrete Maths, Combinatorics and Computer Science

Thanks to Simon Foundation : a youtube video.

# Count twice — now is the time to churn!

Here is one more problem for those of you love to think combinatorially 🙂

Consider a finite sequence of real numbers for which the sum of any seven consecutive terms is negative and the sum of any 11 consecutive terms is positive. Find the greatest number of terms of such a sequence.

Hint: Construct some concrete example and play with it!

More later,

Nalin Pithwa

# Arrays of numbers

Problem :

Prove that among any 10 entries of the table: $\begin{tabular}{cccccccccc} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 9 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 8 & 9 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 7 & 8 & 9 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 7 & 8 & 9 & 0 & 1 & 2 & 3 & 4 & 5 \\ 5 & 6 & 7 & 8 & 9 & 0 & 1 & 2 & 3 & 4 \\ 4 & 5 & 6 & 7 & 8 & 9 & 0 & 1 & 2 & 3 \\ 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & 1 & 2 \\ 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & 1 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0 \end{tabular}$

situated in different rows and different columns, at least two are equal.

more later,

Nalin Pithwa

# Sequences of integers

Sequences of integers are a favourite of olympiad problem writers since such sequences involve several different mathematical concepts, including for example, algebraic techniques, recursive relations, divisibility and primality.

Problem:

Consider the sequence $(a_{n})_{n \geq 1}$ defined by $a_{1}=a_{2}=1$ $a_{3}=199$ and $a_{n+1}=\frac{1989+a_{n}a_{n-1}}{a_{n-2}}$ for all $n \geq 3$. Prove that all the terms of the sequence are positive integers.

Solution:

There is no magic or sure shot or short cut formula to such problems. All I say is the more you read, the more rich your imagination, the more you try to solve on your own.

We have $a_{n+1}a_{n-2}=1989+a_{n}a_{n-1}$

Replacing n by $n-1$ yields, $a_{n}a_{n-3}=1989+a_{n-1}a_{n-2}$ and we obtain $a_{n+1}a_{n-2} - a_{n}a_{n-1}=a_{n}a_{n-3}-a_{n-1}a_{n-2}$

This is equivalent to $a_{n-2}(a_{n+1}+a_{n-1})=a_{n}(a_{n-1}+a_{n-3})$

or $\frac{a_{n+1}+a_{n-1}}{a_{n}}=\frac{a_{n-1}+a_{n-3}}{a_{n-2}}$ for all $n \geq 4$. If n is even, we obtain $\frac{a_{n+1}+a_{n-1}}{a_{n}}=\frac{a_{n-1}+a_{n-3}}{a_{n-2}}= \ldots = \frac{a_{3}+a_{1}}{a_{2}}=200$

while if n is odd, $\frac{a_{n+1}+a_{n-1}}{a_{n}}=\frac{a_{n-1}+a_{n-3}}{a_{n-2}}=\ldots=\frac{a_{4}+a_{2}}{a_{3}}=11$

It follows that $a_{n+1} = 200a_{n}-a_{n-1}$, if n is even,

and $a_{n+1}=11a_{n}-a_{n-1}$, if n is odd.

An inductive argument shows that all $a_{n}$ are positive integers.

More later,

Nalin Pithwa

# Basic Enumeration once again

Prove the following identity (a): $\sum_{k=0}^{n}\left\{ \begin{array}{c} n \\ k \end{array} \right\}x(x-1)\ldots(x-k+1)=x^{n}$

Prove the following identity (b): $\sum_{k=0}^{n}\left [ \begin{array}{c} n \\ k \end{array} \right] = x(x+1)\ldots(x+n-1)$

Prove the following identity (c); $\sum_{k=0}^{n}(-1)^{k}\left\{ \begin{array}{c} n \\ k \end{array} \right\}\left[ \begin{array}{c} k \\ j \end{array} \right]= 1$, if $j=n$ and is 0, otherwise.

General Hint for all three problems: Please see Wikipedia for Stirling numbers!

Hint (a):

If x is an integer, both sides of the first identity  count mappings of an n element set into an x-element set.

Hint (b):

Both sides count pairs $(\pi, \alpha)$ where $\pi$ is a permutation of an n-element set S, and $\alpha$ is a coloration of S with x colors invariant under $\pi$.

Hint (c):

Combine the identities in (a) and (b).

Solution (a):

Suppose first that x is a positive integer. Let $|X|=x$ and $|N|=n$. The number of mappings of N into X is $x^{n}$. On the other hand, let k denote the cardinality of the range of a mapping of N into X. For k fixed, we can specify in $\left\{ \begin{array}{c} n \\ k \end{array} \right\}$ ways which elements of N are mapped onto the same element of X. Once this partition of N is specified, we have to find an image for each class of it, distinct images for distinct classes. This can be done is $x(x-1)\ldots(x-k+1)$ ways. Thus, $\left\{ \begin{array}{c} n \\ k \end{array}\right\}x(x-1)\ldots(x-k+1)$

is the number of mappings of N  into X with range of cardinality k. This proves the identity when x is a positive integer. But this means that if we consider x as a variable the polynomials on the two sides have infinitely many values in common. Therefore, they must be identical.

Solution (b):

Again, we may assume that x is a positive integer. If a permutation $\pi$ of a set S has exactly k cycles, then $x^{k}$, then $x^{k}$ is the number of x-colorations of S invariant under $\pi$. The left hand side of the identity sums these numbers for all permutations $\pi$ of $S=\{ 1 \ldots n \}$. A given x-coloration of S is counted $k_{1}!\ldots k_{x}!$ times, where $k_{i}$ is the number of elements with color i. The number of occurrences of a given sequence $k_{1},\ldots, k_{x}$ is $\frac{n!}{k_{1}!\ldots k_{x}!}$ and so, (fill this missing gap in proof) this sum is $\sum_{(k_{1},\ldots,k_{x}>0) (k_{1}+\ldots+k_{x}=n)}\frac{n!}{k_{1}!\ldots k_{x}!}k_{1}!\ldots k_{x}!$

which equals $n! {{x+n-1}\choose n}=x(x+1)\ldots (x+n-1)$

Solution (c):

Homework and do send comments, suggestions, questions…

More later,

Nalin Pithwa

# Basic enumeration

Question.

We have k distinct postcards and want to send them all to our friends ( a friend can get any number of postcards, including 0). How many ways can this be done? What happens if we want to send at least one card to each friend?

Hint:

Decide now about the postcards. The answer to this question is $n! {k \choose n}$.

Solution:

I. We have to decide about the postcards independently. Any postcard can be sent to any of the n friends. Hence, the result if $n^{k}$.

II. Let $C_{1},C_{2}\ldots C_{k}$ be the cards. The set $S=\{ C_{1},C_{2},\ldots C_{k}\}$ must be split into n disjoint non-empty sets $S_{1},\ldots, S_{n}$. Thus, $\{ S_{1},S_{2}\ldots S_{n}\}$ is a partition of S. From any partition of S into n (non-empty) classes we get $n!$ possibilities to send out the postcards. Hence, the answer is $n! {k \choose n}$.

More later,

Nalin Pithwa