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 1 A function
is injective (one to one) if:
implies
. A function is surjective (onto) if: for all
there is
such that
. A function is bijective if: 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