JEE main and advanced : Principal of Inclusion & Exclusion

JEE main and advanced : Combination is the study of the possible distribution of objects. It is an important part of discreet mathematics, as old as the 17th century. In those time the first combination problems were considered, principally those regarding chance games.

One of the main parts of combination mathematics is the counting of objects. We start this subject formalizing the notion of a number of elements of a group. When counting the elements of a finite group A what one is really doing is enumerating the elements in A and assigning a different natural number to each one, in an orderly fashion, starting with 1.

The number of elements of A will be the natural number in which this process ends. This means, the cardinal of a set will be the minor natural number in the way that exist an injective application of A in the set {1, 2, . . . , n}.

Principle of inclusion-exclusion

The principle of inclusion-exclusion is a method of counting used to calculate the cardinal of the union of several sets. We know that, in the case of two disjoint sets A & B, the Principle of Addition says that the cardinal of the union of A y B is

JEE main and advanced

But, in the case that A y B are not disjoint sets, the equation would have two times an intersection element, once in A and other in B. That is why, in the equation used before we will have to exclude the elements of the AB intersection once, like so,

This, put simple, is the Principle of Inclusion-exclision for the case of two sets. As you can easily visualize, this equation is very intuitive. But, it tends to get more complex as you continue to add sets to the principle, for example, three or more sets. In this matter, having three sets named A, B y C, we will have an union cardinal given by

JEE main and advanced : Brief Analysis Of JEE Mains 2019

We will now study this formula and see that it is perfectly valid. Let us take any element, x for example, of the ABC union. We have these possibilities:

1. The element x is only in one set, let us say A, so we count it once in the right side of the formula.

2. The element x is only in the intersection of two sets, let us say A and B, so we count it once in A and once again in B, that is why we subtract it once.

3. The element x is in the intersection of the three sets (A, B and C). We count it once in each set, then subtract it three times (for AB, AC and BC) and finally we add it in ABC.

For more than three sets, like A1, A2,…An, we use:

Which is the exact same thing as saying:

 (1)

In the probability calculus we have a formula that is completely analogous to (1). The probability of occurrence of one between n events or successions A1, A2,…,An is given by:

(2)

The formula (2), which is the inclusion-exclusion principle, is valid in general for any size space (E, M,m),you only need to replace the probability function P with the size m.

JEE main and advanced : 7 Habits to Prepare Like Soldier

A special case of formula (1) is when two sets have regular intersections, which means that the cardinal of the intersection set:

Is independent of the subset of subindices I, the only depend on k= 1,2, …, n. In this case,we will note that |AI| =ak for every k=1,2,…,n and now formula (1) is express like so:

The inclusion-exclusion principle can be demonstrated with a mathematical induction or demonstrating the identity (*) for indicative functions (the indicative function 1Aof the set A it is so that it takes the value of 1A(x) = 1 if x belongs to A and, in the contrary, is zero).

First, if A and Bare two sets then the indicative function of the intersection AB is 1AB=1A·1B, which means that the product of both functions (in particular 1A·1A= 1A). Also, if B is a subset of A then 1A·1B= 1B. Then we can easily verify the identity:

If we name A the union of the sets A1, A2,…, An, then we will have the functional identity given by:

JEE main and advanced

Being x any element, if x does not belong to A, the element in the right equals zero and if x belongs to A then, by definition of A, it must be included in some subset of Am, which is why we end up with:

JEE main and advanced

Also Read JEE main and advanced : JEE Main Sample Paper

And in this way the product in the right side in the (**) formula also becomes zero. Developing the product (**) we directly obtain the identity (*). To demonstrate formula (1) we will simply have to add applying the (*) identity to each element x of the set A like so:

JEE main and advanced

Applying the integral on the measure m, in a given space size, to the expresion (*) we obtain the principle of inclusion-exclusion to the measure m. For example, this is the case of the probability space and formula (2). If we consider the function of a given area measure over the euclidian plain we will obtain the principle of inclusion-exclusion applied to the calculation of areas.

Example 1.

Calculate the amount of every prime number that is less that 100.

First, we will count the composed numbers. Because 10 is the square root of 100, a composed number that is less that 100 must have prime numbers that are less than 10 as dividends, and those are 2, 3, 5 y 7. Let us calculate the cardinal of the set made by the multiples of these numbers. We now have:

JEE main and advanced

Let us consider next the intersections of two and two, three and three, and so on, of these sets. For instance, the intersection of A2 and A3 it is made of the multiples of 6 including the number 6, like so:

JEE main and advanced

In this way we can calculate:

JEE main and advanced

And the three and three intersections will look like this:

JEE main and advanced

Finally,

JEE main and advanced

Then, applying the formula of the principle of inclusion-exclusion we will have as a result that the set of composed numbers that are less that 100 has a cardinal of:

(49 + 32 + 19 + 13) – (16 + 10 + 7 + 6 + 4 + 2) + (3 + 2 + 1 + 0) – 0 = 74

Meaning that the total of prime numbers that is less that 100 is 25, given that 1 is neither a prime nor a composed number.

Also Read JEE main and advanced : JEE Main Sample Paper

For more questions on Principal Of Inclusion And Exclusion you can solve A. Das Gupta.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.