Visions of Mathematics: Glossary

1. Two laws of enumeration

• Law of addition: If A, B are two sets, then |A∪B| = |A| + |B| - |A∩B|
• Law of multiplication: If A, B are two sets, then |A✖B| = |A| |B|. Here, A ✖ B is the Cartesian product of sets A, B

2. Properties of binomial coefficients

$\binom{n}{m}$ is the number of ways of choosing m objects from a collection of n distinct object without regard to order

$\\*\binom{n}{0} = \binom{n}{n} = 1$

$\\*\binom{n}{r} = \binom{n}{n-r}$

$\\*\binom{n}{r} + \binom{n}{r-1} = \binom{n+1}{r}$

3. Combinations
• From a set containing n distinct elements, a subset with k elements can be chosen in $\binom {n}{k}$ distinct ways
• Number of points of intersection between n non-concurrent and non-parallel lines is $\binom {n}{2}$

• Number of diagonals that can be drawn in a 'n' sided polygon is $\binom {n}{2} -n$

• The number of subsets of n is 2ⁿ; the number of non-empty subsets is 2ⁿ-1

• The number of ways to select r objects from n distinct objects where p particular objects should always be included in the selection = $\binom {n-p}{r-p}$

4. Pigeon hole principle:
If more than 'n' objects are distributed in 'n' boxes, then, at least, one box has more than one object in it

5. Recursion
Sometimes a sequence is defined recursively. This means that we compute each element in terms of the elements preceding it, using some fixed rule. This applies to all elements except for a few initial terms which are fixed independently

• Powers of 2: $\textup{Let }\: \: a_n = 2^n \: \: n \: \: \epsilon \: \: \mathbb{N}. \: \: \textup{Then} \: a_1=2, \: \: a_n = 2 a_{n-1}$
• Squares: $\textup{Let }\: \: a_n = n^2 \: \: n \: \: \epsilon \: \: \mathbb{N}. \: \: \textup{Then} \: a_1=1, \: \: a_n = a_{n-1} + 2n-1$
• Factorials: $\textup{Let }\: \: a_n = n! \: for \: \: n \: \: \epsilon \: \: \mathbb{N}. \: \: \textup{Then} \: a_1=1, \: \: a_n = na_{n-1}$

Glossary - Combinatorics