## Basic Combinatorics.

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: , . We also use set constructor notation where is some statement about that can be true or false. For example: , . We write: , for the set of natural numbers, for the set of rational numbers, for the set of integers.

We write to mean that is in the set . We write . We write . We write for if . If then we say that and are disjoint sets.

We write for the set of ordered pairs of elements.

Definition 1A function isinjective (one to one)if: implies . A function issurjective (onto)if: for all there is such that . A function isbijectiveif: for all there is such that . The number of elements in a set is written .

** 1.2. Basic formulae **

The basic facts of combinatorics are very simple.

- If then there is no injective function from a set with elements to a set with elements. (This is called pigeon hole principle.)
- If there is a bijective function from to then .
- If and are disjoint then .
- If and are disjoint then .
- .
- The number of element subsets of a set with elements is: . (Why is this an integer? Prove it.)
- The number of functions from an -element set to a element set is .
- If then the number of bijective functions from to (permutations of ) is .

There are a couple formulae that are handy to remember:

- There are subset of .
- Suppose you have objects of types 1, 2, , respectively. The number of ways of arranging all the objects is:
- Suppose you have identical objects that you want to distribute among containers. The number of ways to do this is: . (Why?)

leave a comment