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.

  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: , , ,