Pascal’s identity, first derived by Blaise Pascal in 17th century, states that the number of ways to choose k elements from n elements is equal to the summation of number of ways to choose (k-1) elements from (n-1) elements and the number of ways to choose elements from n-1 elements.
Mathematically, for any positive integers k and n: nCk=n−1Ck−1+n−1CknCk=n−1Ck−1+n−1Ck
Proof −
Pigeonhole Principle
In 1834, German mathematician, Peter Gustav Lejeune Dirichlet, stated a principle which he called the drawer principle. Now, it is known as the pigeonhole principle.
Pigeonhole Principle states that if there are fewer pigeon holes than total number of pigeons and each pigeon is put in a pigeon hole, then there must be at least one pigeon hole with more than one pigeon. If n pigeons are put into m pigeonholes where n > m, there’s a hole with more than one pigeon.
Examples
· Ten men are in a room and they are taking part in handshakes. If each person shakes hands at least once and no man shakes the same man’s hand more than once then two men took part in the same number of handshakes.
· There must be at least two people in a class of 30 whose names start with the same alphabet.
The Inclusion-Exclusion principle
The Inclusion-exclusion principle computes the cardinal number of the union of multiple non-disjoint sets. For two sets A and B, the principle states −
