CMC2014 | Parker Glynn-Adey

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.

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.)
If there is a bijective function from ${X}$ to ${Y}$ then ${|X| = |Y|}$ .
If ${X}$ and ${Y}$ are disjoint then ${|X \cup Y| = |X| + |Y| - |X \cap Y|}$ .
If ${X}$ and ${Y}$ are disjoint then ${|X \sqcup Y| = |X| + |Y|}$ .
${|X \times Y| = |X| \cdot |Y|}$ .
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.)
The number of functions from an ${n}$ -element set to a ${k}$ element set is ${k^n}$ .
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:

There are ${2^n}$ subset of ${\{1, \dots, n\}}$ .
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! }}$
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?)

Parker Glynn-Adey

Basic Combinatorics.

Pages

Categories

Tags

Blogroll

Meta