Tutorialspoint.dev

Inclusion-Exclusion and its various Applications

In the field of Combinatorics, it is a counting method used to compute the cardinality of the union set. According to basic Inclusion-Exclusion principle:

  • For 2 finite sets A_1 and A_2, which are subsets of Universal set, then (A_1-A_2), (A_2-A_1) and (A_1igcap A_2) are disjoint sets.

    Hence it can be said that,
    left|(A_1-A_2)igcup(A_2-A_1)igcup(A_1igcap A_2)
ight| = left|A_1
ight| - left|A_1igcap A_2
ight| + left|A_2
ight| - left|A_1igcap A_2
ight| + left|A_1igcap A_2
ight|



    left|A_1 igcup A_2
ight| = left|A_1
ight| + left|A_2
ight| -left|A_1 igcap A_2
ight|.

  • Similarily for 3 finite sets A_1, A_2 and A_3,
    left|A_1 igcup A_2 igcup A_3
ight| = left|A_1
ight| + left|A_2
ight| + left|A_3
ight| - left|A_1 igcap A_2
ight|  - left|A_2 igcap A_3
ight| - left|A_1 igcap A_3
ight|+ left|A_1 igcap A_2 igcap A_3
ight|

Principle :

Inclusion-Exclusion principle says that for any number of finite sets A_1, A_2, A_3... A_i, Union of the sets is given by = Sum of sizes of all single sets – Sum of all 2-set intersections + Sum of all the 3-set intersections – Sum of all 4-set intersections .. + (-1)^{i+1} Sum of all the i-set intersections.

In general it can be said that,

left|A_1 igcup A_2 igcup A_3 .. igcup A_i
ight| = sumlimits_{1 leq k leq i} left|A_k
ight| + (-1)sumlimits_{1 leq k_1 	extless k_2 leq i} left|A_{k_1} igcap A_{k_2}
ight| + (-1)^2sumlimits_{1 leq k_1 	extless k_2 	extless k_3 leq i} left|A_{k_1} igcap A_{k_2} igcap A_{k_3}
ight| .. + (-1)^{i+1}sumlimits_{1 leq k_1 	extless k_2 	extless k_3 	extless .. k_ileq i} left|A_{k_1} igcap A_{k_2} igcap A_{k_3} ..igcap A_{k_i}
ight|

Properties :



  1. Computes the total number of elements that satisfy at least one of several properties.
  2. It prevents the problem of double counting.

Example 1:
As shown in the diagram, 3 finite sets A, B and C with their corresponding values are given. Compute left|A igcup B igcup C
ight|.

Solution :
The values of the corresponding regions, as can be noted from the diagram are –
left|A
ight| = 2, left|B
ight| = 2, left|C
ight| = 2, left|A igcap B
ight| = 3, left|B igcap C
ight| = 3,
left|A igcap C
ight| = 3, left|A igcap B igcap C
ight| = 4

By applying Inclusion-Exclusion principle,
left|A_1 igcup A_2 igcup A_3
ight| = left|A_1
ight| + left|A_2
ight| + left|A_3
ight| - left|A_1 igcap A_2
ight|  - left|A_2 igcap A_3
ight| - left|A_1 igcap A_3
ight|+ left|A_1 igcap A_2 igcap A_3
ight|
left|A_1 igcup A_2 igcup A_3
ight| = 2 + 2 + 2 - 3 - 3 - 3 + 4 = 1

Applications :

  • Derangements
    To determine the number of derangements( or permutations) of n objects such that no object is in its original position (like Hat-check problem).
    As an example we can consider the derangements of the number in the following cases:
    For i = 1, the total number of derangements is 0.
    For i = 2, the total number of derangements is 1. This is 2 1.
    For i = 3, the total number of derangements is 2. These are 2 3 1 and 3 2 1.
  • Applying the Inclusion-Exclusion principle to i general events A_1, A_2, A_3... A_i and rearranging we get the formula,

    P(left|igcuplimits_{k=0}^i A_i
ight|) = P(sumlimits_{k=0}^i left|A_k
ight|) + (-1)P(sumlimits_{1 leq k_1 	extless k_2 leq i} left|A_{k_1} igcap A_{k_2}
ight|) + (-1)^2P(sumlimits_{1 leq k_1 	extless k_2 	extless k_3 leq i} left|A_{k_1} igcap A_{k_2} igcap A_{k_3}
ight|) .. + (-1)^{i+1}P(sumlimits_{1 leq k_1 	extless k_2 	extless k_3 	extless .. k_ileq i} left|A_{k_1} igcap A_{k_2} igcap A_{k_3} ..igcap A_{k_i}
ight|)

    Read next – Inclusion Exclusion principle and programming applications



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter