Combinatorics

Let n and p be two non-zero natural numbers. The number of sequences of p elements belonging to a set of n elements is .

Let E and F be two non-empty sets. If $Card E=p$ and $Card F=n$, then the number of functions defined on E with values in the set F is .

Factorials

(by definition).

1!=1

2!==2

3!==6

4!==24

......

n!=

Properties: ;

Permutations

Definition: A set together with a fixed order of its elements is an ordered set, written .

Definition: The permutations of a set $A$ with $n$ elements are all the ordered sets that can be formed from the $n$ elements of $n$. The number of permutations of $n$ elements, , is ;

the recurrence formula

Arrangements

Definition: The arrangements of n elements taken m at a time $\left(m\le n\right)$ of a set $A$ are all the ordered subsets of $m$ elements that can be formed from the $n$ elements of the set $A$, taken $n$ at a time. They are written .

The number of arrangements of $n$ elements taken k at a time is:

; $p,n\in \mathbb{N}$.

Properties: or ;

;.

Combinations

Definition: The combinations of n elements taken k at a time of a set $A$ with $n$ elements are all the subsets of k elements that can be formed from the $n$ elements of the set $A$. They are written .

Properties:

1) ;

2)

3) The formula for complementary combinations:

4) The decomposition formula for combinations:

5) The number of subsets of a set with $n$ elements is ;

6)

e.g.:

7) where .

The binomial theorem

,

where $n\in N$.

Properties:

1) The term of rank $k+1$ is

2)

3) or

4) The number of terms in the expansion is $n+1$

5) The coefficients of terms equally distant from the ends are equal.

6) are called binomial coefficients.

Important relations:

We arrange numbers in the table below, placing at the intersection of row $n$ with column $k$. Since $k\le n$, the table is filled in only below the main diagonal, so its shape is triangular. This array is called "Pascal's triangle" or the "arithmetic triangle".

Each number at the intersection of row $n$ with column $k$ is obtained by adding the number directly above it, at the intersection of row $n-1$ with column $k$, to the one to its left at the intersection of row $n-1$ with column $k-1$.

Pascal's triangle (1665):

|

n

Common particular expansions:

1)

2)

3)

4)

5)

6)

The sum of like powers of the first n natural numbers

If , then we have:

.

A relation that allows to be computed once are known is Pascal's formula: