Tag Archives: combinatorics

A nice dose of practice problems for IITJEE Foundation math and PreRMO

July 21, 2017 – 12:19 pm

It is said that “practice makes man perfect”.

Problem 1:

Six boxes are numbered 1 through 6. How many ways are there to put 20 identical balls into  these boxes so that none of them is empty?

Problem 2:

How many ways are there to distribute n identical balls in m numbered boxes so that none of the boxes is empty?

Problem 3:

Six boxes are numbered 1 through 6. How many ways are there to distribute 20 identical balls between the boxes (this time some of the boxes can be empty)?

Finish this triad of problems now!

Nalin Pithwa.

By Nalin Pithwa | Posted in IITJEE Foundation mathematics, Pre-RMO | Comments (0)

The Sieve — elementary combinatorial applications

April 10, 2015 – 9:39 am

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

A natural setting for the sieve is in the language of probability theory. Of course, this only means a division by the cardinality of the underlying set, but it has the advantage that independence of occurring events can be defined. Situations in which events are almost independent are extremely important in number theory and also arise in certain combinatorial applications. Number theorists have developed ingenious methods to estimate the formula when the events (usually divisibility by certain primes) are almost independent. We give here the combinatorial background of some of these methods. Their actual use, however, rests upon complicated number theoretic considerations which are here illustrated only by two problems.

It should be emphasized that the sieve formula has many applications in quite different situations.

A beautiful general theory of inclusion-exclusion, usually referred to as the theory of the Mobius function is due to L. Weisner, P. Hall and G. C. Rota.

Question 1: In a high school class of 30 pupils, 12 pupils like mathematics, 14 like physics and 18 chemistry, 5 pupils like both mathematics and physics, 7 both physics and chemistry, 4 pupils like mathematics and chemistry. There are 3 who like all three subjects. How many pupils do not like any of them?

Question 2: (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}

Question 2: (b) (Inclusion-Exclusion Formula)

Let A_{1}, \ldots, A_{n} \subseteq S, where S is a finite set, and let

A_{I}=\bigcap_{ j \in J}A_{j}, A_{\phi}=S. Then,

|S-(A_{1}\cup \ldots \cup A_{n})|=\sum_{J \subset \{ 1, \ldots n\}}(-1)^{|I|}|A_{I}|

Hints:

1) The number of pupils who like mathematics or physics is not 12+14. By how much is 26 too  large?

2) Determine the contribution of any atom of the Boolean Algebra generated by A_{1},, \ldots A_{n} on each side.

Solutions.

1) Let us subtract from 30 the number of pupils who like mathematics, physics, chemistry, respectively:

30-12-14-13.

This way, however, a student who likes both mathematics and physics is subtracted twice; so we have to add them back, and also for the other pairs of subjects:

30-12-14-13+5+7+4.

There is still trouble with those who like all three subjects. They were subtracted 3 times, but back 3 times, so we have to subtract them once more to get the result:

30-12-14-13+5+7+4-3=4/

2) (a) Let B=A_{1}A_{2}\ldots A_{k}\overline A_{k+1}\ldots \overline A_{n}

be any atom of the Boolean algebra generated by A_{1}, A_{2}, \ldots A_{n} (with an appropriate choice of indices, every atom has such a form.) Every event in the formula is the union of certain (disjoint) atoms; let us express each P(A_{I}) and P(A_{1}+A_{2}+\ldots +A_{n}) as the sum of the probabilities of the corresponding atoms. We show that the probability of any given atom cancels out.

The coefficient of P(B) on the left hand side is

1, if k \neq 0 and 0, if k=0

B occurs in A_{I} if I \subseteq \{ 1, \ldots k\}. so its coefficient on the right hand side is

\sum_{j=1}^{k}\left( \begin{array}{c} k \\ j \end{array} \right) (-1)^{j}=1-(1-1)^{k}=1, k \neq 04, and latex 0 if k =0$.

Thus, P(B) has the same coefficient on both sides, which proves part a.

Solution (b):

Choose an element x of S by a uniform distribution. Then, A_{i} can be identified with the event that

x \in A_{I}, and we have

P(A_{i})=\frac{|A_{i}|}{|S|}

So, we have, by the above,

P(A_{1}+A_{2}+\ldots + A_{n})=\sum_{j=1}^{n}(-1)^{j-1}\sum_{|I|=j}\frac{|A_{I}|}{|S|}, where

\sum_{\phi \neq I \subseteq \{ 1, \ldots n\} }(-1)^{|I|-1}\frac{A_{I}}{|S|}, or equivalently

P(\overline{A_{1}}\ldots \overline{A_{n}})=1-P(A_{1}+\ldots + A_{n}), which in turn equals,

1- \sum_{\phi \neq I \subseteq \{ 1, \ldots , n\}}(-1)^{|I|-1}\frac{|A|}{|S|}

The assertion (b) follows on multiplying by |S|.

More later,

Nalin Pithwa

By Nalin Pithwa | Posted in IITJEE Advanced, IITJEE Advanced Mathematics, IITJEE Foundation Math IITJEE Main and Advanced Math and RMO/INMO of (TIFR and Homibhabha), INMO, pure mathematics, RMO | Also tagged , , , , , , | Comments (0)

Basic enumeration — continued

March 12, 2015 – 11:58 pm

(a) How many possibilities are there to distribute k forints (Hungarian currency) among n people so that each receive at least one?

(b) Suppose that we do and insist that each person receives something. What will be the number of distributions in this case?

Hint (a)

Imagine k 1-forint coins in a row and suppose that the people come one by one and pick up forints as long as you allow them.

Hint (b)

Reduce to the previous case by borrowing 1 forint from each person.

Solution (a):

If we distribute the forints by the procedure described in the hint, we have to say “Next please” n-1 times. If we determine at which points (after which coins) we say this we uniquely determine the distribution. There are

k-1 possible points to switch and we have to choose n-1 out of these. Hence, the result is

{{k-1} \choose {n-1}}.

Solution (b):

Borrow one forint from each person. If we distribute the n+k forints, we then have in such a way that each person gets at least one, we should then have done the same as if we had distributed the k forints without this requirement. More precisely, distributions of n+k forints among persons so that each one gets at least one are in one to one correspondence with all distributions of n forints among k persons. Hence, the answer is

{{n+k-1} \choose {n-1}}.

More later,

Nalin Pithwa

By Nalin Pithwa | Posted in IITJEE Foundation Math IITJEE Main and Advanced Math and RMO/INMO of (TIFR and Homibhabha), IITJEE Foundation mathematics, pure mathematics | Also tagged , , | Comments (0)

Basic combinatorics — basic enumeration

March 12, 2015 – 10:15 am

I. Basic Enumeration:

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

1) In a shop there are k kinds of postcards. We want to send postcards to n friends. How many different ways can this be done? What happens if we want to send them different cards? What happens if we want to send two different cards to each of them(but different persons may get the same card)?

Hint:

Decide about the persons one by one.

Solution:

I. i.

The first person may be sent any of the k kinds of postcards. No matter which one he is sent, we may still send the second one any of the k kinds, so there are k \times k = k^{2} ways to send cards to the first two friends. Again, whatever they are sent, the third friend can still be sent k kinds, etc. So there are k^{n} ways to send out the cards.

I.ii

If they have to be sent different cards, the first person can still be sent any of the k cards. But for any choice of this card, there are only k-1 kinds of cards left for the second person, whatever the first and second friends receive the third one can get one of k-2 postcards, etc…Thus, the number of ways to send them postcards is

k(k-1)\ldots(k-n+1) (which is, of course, 0 if n > k).

I. iii.

This is the same as the first question but we have {k \choose 2} pairs of postcards instead of k postcards. Thus the result is ({k \choose 2})^{2}.

More later,

Nalin Pithwa

By Nalin Pithwa | Posted in Fun with Mathematics, IITJEE Foundation Math IITJEE Main and Advanced Math and RMO/INMO of (TIFR and Homibhabha), IITJEE Foundation mathematics, pure mathematics | Also tagged | Comments (0)