Category Archives: combinatorics or permutations and combinations

Fun with Zeta !!!

November 17, 2016 – 1:27 am

Mr. and Mrs. Zeta wanted to name their baby Zeta so  that its monogram (first, middle and last initials) will be in alphabetical order with no letters repeated. How many such monograms are possible?

— Nalin Pithwa 

(Ref: Prof Titu Andreescu’s literature).

By nkpithwa | Also posted in Fun with Mathematics | Comments (2)

Inclusion Exclusion Principle theorem and examples

February 13, 2016 – 11:27 am

Reference: Combinatorial Techniques by Sharad Sane, Hindustan Book Agency.

Theorem: 

The inclusion-exclusion principle: Let X be a finite set and let and let P_{i}: i = 1, 2, \ldots n  be a set of n properties satisfied by (s0me of) the elements of X. Let A_{i} denote the set of those elements of X that satisfy the property P_{i} . Then, the size of the set \overline{A_{1}} \bigcup \overline{A_{2}} \bigcup \ldots \bigcup \overline{A_{n}} of all those elements that do not satisfy any one of these properties is given by

\overline{A_{1}} \bigcup \overline{A_{2}} \bigcup \ldots \bigcup \overline{A_{n}} = |X| - \sum_{i=1}^{n}|A_{n}|+ \sum_{1 \leq i <j \leq n}|A_{i} \bigcup A_{j}|- \ldots + \{ (-1)^{k} \sum_{1 \leq i_{1} < i_{2}< \ldots < i_{k} \leq n}|A_{i_{1} \bigcup A_{i_{2}}} \ldots \bigcup A_{i_{k}}|\}+ \ldots+ (-1)^{n}|A_{1} \bigcup A_{2} \ldots \bigcup A_{n}|.

Proof:

The proof will show  that every object in the set X is counted the same number of times on both the sides. Suppose x \in X and assume that x is an element of the set on the left hand side of above equation. Then, x has none of the properties P_{i}. We need to show that in this case, x is counted only once on the right hand side. This is obvious since x is not in any of the A_{i} and x \in X. Thus, X is counted only once in the first summand and is not counted in any other summand since x \notin A_{i} for all i. Now let x have k properties say P_{i_{1}}, P_{i_{2}}, \ldots, P_{i_{k}} (and no  others). Then x is counted once in X. In the next sum, x occurs {k \choose 2} times and so on. Thus, on the right hand side, x is counted precisely,

{k \choose 0}-{k \choose 1}+{k \choose 2}+ \ldots + (-1)^{k}{k \choose k}

times. Using the binomial theorem, this sum is (1-1)^{k} which is 0 and hence, x is not counted on the right hand side. This completes the proof. QED.

More later,

Nalin Pithwa

 

 

 

 

 

 

 

 

 

By nkpithwa | Also posted in Cnennai Math Institute Entrance Exam, IITJEE Advanced Mathematics, RMO | Comments (0)

The inclusion-exclusion principle for RMO and IITJEE Maths

February 8, 2016 – 5:59 pm

Reference: Combinatorial Techniques by Sharad Sane:

The principle and its applications:

The inclusion-exclusion principle, is among the most basic techniques of combinatorics. Suppose we have a set X with subsets A and B. Then, the number of elements that are in A or B (or both), that is, the cardinality of A \cup B is given by |A|+|B|- |A \cap B|. The elements that are in both A and B were counted twice. To get rid of the over-counting, we must subtract. If \overline{A} and \overline{B} denote the complements of A and B respectively, then how many elements does the set \overline{A} \cup \overline{B} have? This number is |X|-|A|-|B|+|A \cap B|. The explanation is as before. From the set of all the elements we get rid of those that are in A or B. In doing so, we subtracted the elements of A \cap B twice. This has to be corrected by adding such elements once. Essentially, this way of over-counting (inclusion) correcting it using under-counting (exclusion) and again correcting (over-correcting) and so on is referred to as the inclusion-exclusion technique. As another example, consider the question of finding how many positive integers up to 100 are not divisible by 2, 3 or 5. We see that there are 50 integers that are multiple of 2, 33 that are multiples of 3 and 20 that are multiples of 5. This certainly amounts to over-counting as there are integers that are divisible by two of the given three numbers 2, 3 and 5. In fact, the number of integers divisible by both 2 and 3 is 16, the number of integers divisible by both 2 and 5, that is divisible by 10 is 10, the number of integers divisible by both 3 and 5 is the number of integers below 100 and divisible by 15 and that number is 6. Finally, the number of integers divisible by all three 2, 3, and 5 is just 3. Hence, the number of integers NOT divisible by any one of 2, 3 or 5 is

100-(50+33+20)+(16+10+6)-3=26

The technique used above is called the sieve method. This technique was known to the Greeks and is in fact, known as the Sieve of Eratosthenes. (Remember: in high school, you have used this method to find primes from 1 to 100).

Also, note that I am reminded of the technique of telescoping series when I think about inclusion-exclusion. There seems to be some similarity in spirit.

More later,

Nalin Pithwa

By nkpithwa | Also posted in Cnennai Math Institute Entrance Exam, IITJEE Mains, ISI Kolkatta Entrance Exam, KVPY | Comments (0)