Question

Waht is inclusion-exclusion Principle?

Answer 1

The Principle of Inclusion and Exclusion (PIE) is a counting technique that computes the number of elements that satisfy at least one of several properties while guaranteeing that elements satisfying more than one property are not counted twice.

An underlying idea behind PIE is that summing the number of elements that satisfy at least one of two categories and subtracting the overlap prevents double counting. For instance, the number of people that have at least one cat or at least one dog can be found by taking the number of people who own a cat, adding the number of people that have a dog, then subtracting the number of people who have both.

PIE is particularly useful in combinatorics and probability problem solving when it is necessary to devise a counting method that ensures an object is not counted twice.

Answer 2

A well-known application of theinclusion–exclusion principle is to the combinatorial problem of counting all derangements of a finite set. A derangement of a set A is a bijection from A into itself that has no fixed points. ... The number of derangements is also known as the subfactorial of n, written !n.