Combinatorial analysis and enumerating formulas

All the formulas that follow will always have two cases:

without repetition
with repetition: in this case there will be a bar above to mean "with repetition"

For example, if we note the arrangements without repetition $A_n$, we will note $\overline{A_n}$ those with possible repetition.

Permutations

The number of permutations of the elements of a set (without repetition)

For any set $E$ of $n$ elements, the number of possible permutations without repetition is:

$$ \forall n \in \mathbb{N}, $$

$$ P_n = n !$$

The number of permutations of the elements of a set (with repetition)

For any set $E = \{e_1, e_2, e_3, \ ..., \ e_n \}$ with $k_1, k_2, k_3, ...,k_{n}$ the number of occurrences of each element, the number of possible permutations is:

$$ \forall n \in \mathbb{N}, \ \forall (k_1, k_2, k_3, ...,k_n),$$

$$ \overline{P_n} = \frac{ \left( \sum\limits_{i=1}^{n} k_i \right) ! }{\prod\limits_{i=1}^{n} k_i ! } = \frac{\bigl(k_1 + k_2 \hspace{0.05em} + \hspace{0.05em} ... \hspace{0.05em} + k_n \hspace{0.05em}\bigr) !}{k_1 ! \times k_2 ! \hspace{0.05em} \times \hspace{0.05em} ... \hspace{0.05em} \times k_n ! } $$

Arrangements (with a certain order)

The number of arrangements of the elements of a set (without repetition)

The number of arrangements without repetition of $p$ elements taken from a set of $n$ are worth:

$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n, $$

$$ A_n^p = \frac{n !}{(n-p) !}$$

The number of arrangements of the elements of a set (with repetition)

The number of arrangements with repetition of $p$ elements taken from a set of $n$ are worth:

$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n, $$

$$ \overline{A_n^p} = n^p$$

Combinations (without any order)

The number of ways to take distinct elements from a set (without repetition)

The number of ways to take $p$ elements (distinct and without repetition) in a set of $n$ elements are worth:

$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n, $$

$$ \binom{n}{p} = \frac{n !}{p ! (n-p) !}$$

($\Longrightarrow$ voir les propriétés du binôme)

The number of ways to take distinct elements from a set (with repetition)

The number of ways to take $p$ elements (distinct and with repetition) in a set of $n$ elements are worth:

$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \ n \geqslant 1, $$

$$ \left(\binom{n}{p}\right) = \binom{n + p - 1}{p} = \frac{(n + p -1) !}{p ! (n-1) !}$$

The number of possible parts of a set

The number of possible parts of a set $E = \{e_1, e_2, e_3, \ ..., e_n\}$, that's to say :

$$ \Bigl \{ \{ \emptyset \}, \{e_1\}, \{e_2\}, \{e_3\}, \ ..., \ \{e_1, e_2\}, \ \{e_1, e_3\}, \ \{e_2, e_3\}, \ ..., \ \{e_1, e_2, e_3\}, \ \{e_1, e_3, e_4\}, \ \{e_1, e_2, e_4\}, \ ..., \ \{e_1, e_2, e_3, \ ..., e_n\} \Bigr \}$$

is worth :

$$ \forall n \in \mathbb{N}, $$

$$ \sum_{p = 0}^n \binom{n}{p} = \hspace{0.2em} 2^n $$

Summary of combinatorics and enumeration formulas

Demonstrations

Let $E$ be a set composed of $n$ éléments :

$$E = \{e_1, e_2, e_3, \ ..., e_n\}$$

Permutations

The number of permutations of the elements of a set (without repetition)

For the first choice, we do have $n$ possibilities. For the second, we do have $(n-1)$ since a first element has already been chosen. In the same way, for the third, we will have $(n-2)$...etc., up to the last element $(n-(n-1))$.

$$ P_n = n \times (n-1) \times (n-2) \hspace{0.02em} \times \hspace{0.02em} ... \hspace{0.02em} \times \hspace{0.02em} (n-(n-2)) \times (n-(n-1))$$

$$ P_n = n \times (n-1) \times (n-2) \hspace{0.02em} \times \hspace{0.02em} ... \hspace{0.02em} \times 2 \times 1$$

So finally, for any set $E$ of $n$ elements:

$$ \forall n \in \mathbb{N}, $$

$$ P_n = n !$$

The number of permutations of the elements of a set (with repetition)

Let $A$ be an alphabet composed of $n$ letters:

$$A = \{a, b, c, \ ..., \ \omega \}$$

And the numbers $k_a, k_b, k_c, \ ..., \ k_{\omega} $ the number of repetitions associated with each of these letters.

As above, the number of words of $n$ letters that can be composed with the letters of the alphabet $A$ without repetition is: $n !$.

Now, taking into account the respective repetitions of each letter, we have the following alphabet:

$$A' = \{ \underbrace{a, a, a, ...} _\text{$k_a$}, \ \underbrace{b, b, b, ...} _\text{$k_b$}, \ \underbrace{c, c, c, ...} _\text{$k_c$}, \ ..., \ \ \underbrace{\omega, \omega, \omega, ...} _\text{$k_{\omega}$} \}$$

Let us call $N$ the sum of the respective different repetitions:

$$N = k_a + k_b + k_c + \ ... \ + k_{\omega} $$

In the same way, we can then compose $N !$ words of $N$ letters. However, since some letters will be repeated, it will be necessary to remove words that are present several times and thus keep only one version of each word.

That is, for each word $m$ created, with a defined place for each letter:

$$ m_1 = \{ \underbrace{aaa ...} _\text{$k_a$} \ \underbrace{b b b ...} _\text{$k_b$} \ \underbrace{c c c ...} _\text{$k_c$} \ \ \underbrace{\omega \omega \omega ...} _\text{$k_{\omega}$} \}$$

$$ m_2 = \{ a a b ... \ a b b ... \ c c \omega \ ... \ c \omega \omega ... \}$$

$$ ...etc.$$

There are some $k_a !$ versions with the letter $a$ at these precise places, then $k_b !$ versions for the letter $b$...etc.

So for each word, there is $(k_a ! \times k_b ! \times \ k_c ! \times \hspace{0.05em} ... \hspace{0.05em} \times k_{\omega} !) $ identical versions of the same word.

So, for any set $E = \{e_1, e_2, e_3, \ ..., \ e_n \}$ with $k_1, k_2, k_3, ...,k_{n}$ the number of occurrences of each element, the number of possible permutations is:

$$ \forall n \in \mathbb{N}, \ \forall (k_1, k_2, k_3, ...,k_n),$$

Implicitly, for all $i$ if the element $e_i$ is present once then $k_i = 1$ by default.

Arrangements (avec ordre)

The number of arrangements of the elements of a set (without repetition)

If we want to classify a number of $p$ éléments selon un ordre bien précis,elements in a very precise order, a bit like permutations we will $n$ choices for the first, ((n-1)\) choices for the second ... etc., but on $p$ elements only, unlike a permutation:

$$A_n^p = \hspace{0.05em} \underbrace{ n \times (n-1) \times (n-2) \hspace{0.02em} \times \hspace{0.02em} ... \hspace{0.02em} \times \hspace{0.02em} (n-(p-2)) \times (n-(p-1)) } _\text{ $p$ elements} $$

Now, we notice that this almost corresponds to a a factorial:

$$n ! = n \times (n-1) \times (n-2) \hspace{0.02em} \times \hspace{0.02em} ... \hspace{0.02em} \times \hspace{0.02em} 2 \times 1 $$

Indeed,

$$n ! = n \times (n-1) \times (n-2) \hspace{0.02em} \times \hspace{0.02em} ... \hspace{0.02em} \times \hspace{0.02em} (n-(p-2)) \times (n-(p-1)) \times (n-p) \times (n-(p + 1)) \times \hspace{0.02em} ... \hspace{0.02em} \times \hspace{0.02em} 2 \times 1 $$

$$n ! =A_n^p \times (n-p) ! $$

So, the number of arrangements without repetition of $p$ elements taken from a set of $n$ elements are worth:

$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n, $$

$$ A_n^p = \frac{n !}{(n-p) !}$$

The number of arrangements of the elements of a set (with repetition)

When we make arrangements in a group, but this time with repetition, we will then have $n$ choices every time:

$$A_n^p = \hspace{0.05em} \underbrace{ n \times n \hspace{0.02em} \times \hspace{0.02em} ... \hspace{0.02em} \times \hspace{0.02em} n \times n } _\text{ $p$ elements} $$

So, the number of arrangements with repetition of $p$ elements taken from a set of $n$ elements are worth:

$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n, $$

$$ \overline{A_n^p} = n^p$$

Combinations (without any order)

The number of ways to take distinct elements from a set (without repetition)

By calculating the number of possible (non-repeating) arrangements of $p$ elements taken from this set, we obtain a number of possible elements with a notion of classification, or order.

If we want to keep only one version of this number of elements, all distinct, we must then remove their order, that is to say their permutations. We will note this number $\binom{n}{p}$, so:

$$ \binom{n}{p} = \frac{A_n^p}{p !} $$

So the number of ways to take $p$ elements (distinct and without repetition) in a set of $n$ elements are worth:

$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n, $$

$$ \binom{n}{p} = \frac{n !}{p ! (n-p) !} $$

($\Longrightarrow$ voir les propriétés du binôme)

We read it ("$ p $ among $ n $").

The number of ways to take distinct elements from a set (with repetition)

These elements are considered to be in abundance, and one can, each turn, draw again from the elements of this set.

We want to know the number of ways there are to take a basket of $p$ elements among a total of $n$.

In this case, consider a new final set $F$, which will be the starting set, to which we will add in turn the elements already chosen in the previous round.

In the first round, we choose an element, which we add at the end:

$$F = \{ \cancel{e_1}, e_2, e_3, e_4, \ ..., e_p, \ ..., e_n, e_1\}$$
In the second round, we choose a second element, which we add at the end:

$$F = \{ \cancel{e_1}, \cancel{e_2}, e_3, e_4, \ ..., e_p, \ ..., e_n, e_1, e_2\}$$
..etc.
At $(p-1)$-nth round, we put back $(p-1)$ times the items chosen each round:

$$F = \{ \cancel{e_1}, \cancel{e_2}, \cancel{e_3}, \cancel{e_4}, \ ..., \cancel{e_{p-1}}, e_{p} \ ... , e_n , \ e_1, e_2, e_3, e_4, \ ... , e_{p-1} \}$$
At $p$-th round, we choose a last one without putting it back in the final set, because we have reached the number of $p$ desired terms.

$$F = \{ \underbrace{ \cancel{e_1}, \cancel{e_2}, \cancel{e_3}, \cancel{e_4}, \ ..., \cancel{e_{p-1}}, \cancel{e_{p}}, \ ... , e_n } _\text{$n$ starting elements }, \ \underbrace{ e_1, e_2, e_3, e_4, \ ... , e_{p-1} } _\text{$(p-1)$ added elements} \}$$

Ultimately, it comes down to taking $p$ distinct elements in a set of $(n + p - 1)$ elements.

We will note this number $\bigl(\binom{n}{p}\bigr)$ as opposed to elements taken without any repetition $\binom{n}{p}$.

So the number of ways to take $p$ elements (distinct and with repetition) in a set of $n$ elements are worth:

$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \ n \geqslant 1, $$

$$ \left(\binom{n}{p}\right) = \binom{n + p - 1}{p} = \frac{(n + p -1) !}{p ! (n-1) !}$$

Note that unlike elements taken without any repetition $\binom{n}{p}$, in this case it is possible to have $(p > n)$.

The number of possible parts of a set

If we want to obtain the number of possible parts of this set, that is to say:

For any $p $ elements from $0$ to $n$, we do have to add $ p $ elements among $ n $ $\binom{n}{p}$ :

$$ \sum_{p = 0}^n \binom{n}{p} = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} \hspace{0.05em} + \hspace{0.05em} ... \hspace{0.05em} + \hspace{0.05em} \binom{n}{n-1} + \binom{n}{n} $$

And this sum is worth:

$$\forall n \in \mathbb{N}, $$

$$ \sum_{p = 0}^n \binom{n}{p} = \hspace{0.2em} 2^n $$

($\Longrightarrow$ see the demonstration)

Summary of combinatorics and enumeration formulas

Examples

Permutations

The number of permutations of the elements of a set (without repetition)

If we have an alphabet with $3$ different letters:

$$A = \bigl \{a, b, c \}$$

If we want to know the number of possible words, without repetition of letters, we have $3!$ possible words.

$$ P_{abc} = 3 !$$

The number of permutations of the elements of a set (with repetition)

Now, with this alphabet of $3$ letters:

$$A = \bigl \{m, a, n \}$$

If you want to know the number of anagrams of the word $"maman"$, we do have:

$$ \overline{P_{maman}} = \frac{(2 + 2 + 1) !}{2 ! \times 2 ! } $$

$$ \overline{P_{maman}} =30$$

Arrangements

The number of arrangements of the elements of a set (without repetition)

We have an urn with $8$ numbered balls from $1$ to $8$. We want to calculate the number of possibilities to draw $3$ balls.

$$ A_8^3 = \frac{8 !}{(8-3) !}$$

$$ A_8^3 = \frac{8 !}{5 !}$$

$$ A_8^3 = 8 \times 7 \times 6$$

$$ A_8^3 = 336$$

The number of arrangements of the elements of a set (with repetition)

We now want to draw $3$ balls, but with return to the urn each time. We will therefore have for the three times, $8$ possibilities of drawings.

$$ \overline{A_8^3} = 8^3$$

$$ \overline{A_8^3} = 512$$

Combinations

The number of possible combinations of the elements of a set (without repetition)

If we want to know how many matches there will be in a chess championship between $10$ competitors, who will all play each other once.

We must then take $2$ players among the $10$ competitors.

$$ \binom{10}{2} = \frac{10 !}{2 ! (10-2) !} $$

$$ \binom{10}{2} = \frac{9 \times 10}{2} $$

$$ \binom{10}{2} = 45 $$

The number of possible combinations of the elements of a set (with repetition)

We want to create a basket of $(p = 4)$ fruits from a possible choice of $(n = 6)$ fruits, knowing that the available fruits are in abundance. We then have:

$$ \left(\binom{6}{4}\right) = \binom{6 + 4 - 1}{4} $$

$$ \left(\binom{6}{4}\right) = \binom{9}{4} $$

$$ \left(\binom{6}{4}\right) = \frac{9 !}{4 ! (9-4) !} $$

$$ \left(\binom{6}{4}\right) = \frac{9 \times 8 \times 7 \times 6 }{4 \times 3 \times 2} $$

$$ \left(\binom{6}{4}\right) = 126 $$

Combinatorial analysis and enumerating formulas

Demonstrations

Examples

Permutations

The number of permutations of the elements of a set (without repetition)

The number of permutations of the elements of a set (with repetition)

Arrangements

The number of arrangements of the elements of a set (without repetition)

The number of arrangements of the elements of a set (with repetition)

Combinations

The number of possible combinations of the elements of a set (without repetition)

The number of possible combinations of the elements of a set (with repetition)