
Pages

Categories
 algebra
 applications of maths
 Basic Set Theory and Logic
 calculus
 careers in mathematics
 Cnennai Math Institute Entrance Exam
 coordinate geometry
 combinatorics or permutations and combinations
 Complex Numbers
 Fun with Mathematics
 geometry
 IITJEE Advanced
 IITJEE Advanced Mathematics
 IITJEE Foundation Math IITJEE Main and Advanced Math and RMO/INMO of (TIFR and Homibhabha)
 IITJEE Foundation mathematics
 IITJEE Mains
 Inequalities
 Information about IITJEE Examinations
 INMO
 ISI Kolkatta Entrance Exam
 KVPY
 mathematicians
 memory power concentration retention
 motivational stuff
 physicisrs
 PreRMO
 probability theory
 pure mathematics
 RMO
 RMO Number Theory
 Statistics
 time management
 Trigonometry

Archives
 March 2018
 February 2018
 January 2018
 December 2017
 November 2017
 October 2017
 September 2017
 August 2017
 July 2017
 June 2017
 May 2017
 April 2017
 March 2017
 February 2017
 January 2017
 November 2016
 October 2016
 September 2016
 August 2016
 July 2016
 June 2016
 May 2016
 April 2016
 March 2016
 February 2016
 January 2016
 December 2015
 November 2015
 October 2015
 September 2015
 August 2015
 July 2015
 June 2015
 May 2015
 April 2015
 March 2015
 February 2015
 January 2015
 December 2014
 November 2014
 October 2014
 September 2014
 August 2014
 July 2014
 June 2014
Category Archives: combinatorics or permutations and combinations
We owe a lot to the Indians who taught us counting — Albert Einstein
Motivation for Combinatorics: “Lilavathi”
Say mathematician, how many are the combinations in one composition with ingredients of six different tastes — sweet, pungent, astringent, sour, salt and bitter — taking them by ones, twos, or threes, etc.?
— From Lilavathi of Bhaskara (the great twelfth century mathematician of India).
— Nalin Pithwa.
PS: Almost all countries/nations have some culture of math just as they do of music and poetry and singing and dancing 🙂 🙂 🙂
Permutations and Combinations: IITJEE Mains problem solving practice
Problem 1:
Find all natural numbers n such that ends with exactly 26 zeros.
Problem 2:
Find the largest two digit prime that divides .
Problem 3:
Find all natural numbers such that is divisible by 25.
Problem 4:
When is computed, it ends in 7 zeros. Find the digit that immediately precedes these zeros.
Problem 5:
Prove that is a natural number for all .
Cheers,
Nalin Pihwa.
Fun with Zeta !!!
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).
Inclusion Exclusion Principle theorem and examples
Reference: Combinatorial Techniques by Sharad Sane, Hindustan Book Agency.
Theorem:
The inclusionexclusion principle: Let X be a finite set and let and let be a set of n properties satisfied by (s0me of) the elements of X. Let denote the set of those elements of X that satisfy the property . Then, the size of the set of all those elements that do not satisfy any one of these properties is given by
.
Proof:
The proof will show that every object in the set X is counted the same number of times on both the sides. Suppose 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 . 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 and . Thus, X is counted only once in the first summand and is not counted in any other summand since for all i. Now let x have k properties say , , , (and no others). Then x is counted once in X. In the next sum, x occurs times and so on. Thus, on the right hand side, x is counted precisely,
times. Using the binomial theorem, this sum is which is 0 and hence, x is not counted on the right hand side. This completes the proof. QED.
More later,
Nalin Pithwa
The inclusionexclusion principle for RMO and IITJEE Maths
Reference: Combinatorial Techniques by Sharad Sane:
The principle and its applications:
The inclusionexclusion 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 is given by . The elements that are in both A and B were counted twice. To get rid of the overcounting, we must subtract. If and denote the complements of A and B respectively, then how many elements does the set have? This number is . 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 twice. This has to be corrected by adding such elements once. Essentially, this way of overcounting (inclusion) correcting it using undercounting (exclusion) and again correcting (overcorrecting) and so on is referred to as the inclusionexclusion 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 overcounting 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
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 inclusionexclusion. There seems to be some similarity in spirit.
More later,
Nalin Pithwa