## Basic Combinatorics.

Posted in Uncategorized by pgadey on 2014/07/27

First we recall a little bit of terminology:

1.1. Sets and functions

A set is a collection of elements . We write a set by surrounding its list elements with curly braces. For example: ${X = \{1,2,3\}}$, ${Y = \{\heartsuit, \clubsuit, \star\}}$. We also use set constructor notation ${Y = \{x : P(x)\}}$ where ${P(x)}$ is some statement about ${x}$ that can be true or false. For example: ${X = \{n : n\text{ is even}\}}$, ${Z = \{n : n\text{ is prime}\}}$. We write: ${\{\} = \emptyset}$, ${{\mathbb N}}$ for the set of natural numbers, ${{\mathbb Q}}$ for the set of rational numbers, ${{\mathbb Z}}$ for the set of integers.

We write ${x \in X}$ to mean that ${x}$ is in the set ${X}$. We write ${X \cup Y = \{x : x \in X \text{ or } x \in Y\}}$. We write ${X \cap Y = \{x : x \in X \text{ and } x \in Y\}}$. We write ${X \sqcup Y}$ for ${X \cup Y}$ if ${X \cap Y = \emptyset}$. If ${X \cap Y = \emptyset}$ then we say that ${X}$ and ${Y}$ are disjoint sets.

We write ${X \times Y = \{(x,y) : x \in X,\ y \in Y\}}$ for the set of ordered pairs of elements.

Definition 1 A function ${f : X \rightarrow Y}$ is injective (one to one) if: ${x \neq y}$ implies ${f(x) \neq f(y)}$. A function is surjective (onto) if: for all ${y \in Y}$ there is ${x \in X}$ such that ${f(x) = y}$. A function is bijective if: for all ${y \in Y}$ there is ${x \in X}$ such that ${f(x) = y}$. The number of elements in a set ${X}$ is written ${|X|}$.

1.2. Basic formulae

The basic facts of combinatorics are very simple.

1. If ${k < n}$ then there is no injective function from a set with ${n}$ elements to a set with ${k}$ elements. (This is called pigeon hole principle.)
2. If there is a bijective function from ${X}$ to ${Y}$ then ${|X| = |Y|}$.
3. If ${X}$ and ${Y}$ are disjoint then ${|X \cup Y| = |X| + |Y| - |X \cap Y|}$.
4. If ${X}$ and ${Y}$ are disjoint then ${|X \sqcup Y| = |X| + |Y|}$.
5. ${|X \times Y| = |X| \cdot |Y|}$.
6. The number of ${k}$ element subsets of a set with ${n}$ elements is: ${\binom{n}{k} = \frac{ n! }{ (n-k)! k! }}$. (Why is this an integer? Prove it.)
7. The number of functions from an ${n}$-element set to a ${k}$ element set is ${k^n}$.
8. If ${|X| = n}$ then the number of bijective functions from ${X}$ to ${X}$ (permutations of ${X}$) is ${n!}$.

There are a couple formulae that are handy to remember:

1. There are ${2^n}$ subset of ${\{1, \dots, n\}}$.
2. Suppose you have ${n_1, \dots, n_k}$ objects of types 1, 2, ${\dots}$, ${k}$ respectively. The number of ways of arranging all the objects is: ${{ (n_1 + \dots + n_k)! }/{ n_1! n_2! \dots n_k! }}$
3. Suppose you have ${n}$ identical objects that you want to distribute among ${k}$ containers. The number of ways to do this is: ${\binom{n+k-1}{k-1}}$. (Why?)

Tagged with: , , ,