Discrete. 1. Combinatorics

В общем, я решил начать с комбинаторики. Если возникнут какие-то проблемы, всегда можно перенести, где-то это всё должно возникнуть, и почему бы и не здесь?

По поводу обозначений: обычно в фигурные скобки $\{\}$ берутся неупорядоченные множества, а в круглые $()$ -- упорядоченные. Для первых порядок не важен, и подразумевается, что $\{1,2\} = \{2,1\}$. Для вторых важен: $(1,2)\ne (2,1)$.

Перестановки

Рассмотрим такое множество: $$\{1,\,2,\,3\}$$ Сколько есть способов переставить поставить элементы в разном порядке? $$\{1,2,3\};\;\{1,3,2\};\;\{3,1,2\};\;\{3,2,1\};\;\{2,3,1\};\;\{2,1,3\}$$ Шесть.

Скажем неформально. Каждый из таких способов называется перестановкой.

Вопрос. Сколько существует перестановок у множества из $n$ элементов?

Давайте рассмотрим такое множество: $\{a_1,\,a_2,\,a_3,\,\color{gray}{\dots},\,a_n\}$. И будем создавать перестановку.

1. Итак, на 1 место мы можем поставить любой из $n$ элементов, т.е. у нас $n$ вариантов. Поставим какой-нибудь элемент $a_i$. $$(a_i)$$
2. На 2 место мы можем поставить любой элемент кроме $a_i$. Иными словами, $n-1$ вариантов 2-го элемента. Поставим $a_j$. $$(a_i,\,a_j)$$
3. На 3 место можем поставить любой кроме $a_i$ и $a_j$. То есть, $n-2$ вариантов. Поставим $a_k$. $$(a_i, a_j, a_k)$$
4. ...
5. PROFIT!

Продолжаем так, пока все элементы не кончатся, а в перестановке их не станет $n$.
Поздравляшки!
Теперь очевидно, что количество перестановок у множества из $n$ элементов равно: $$n \cdot (n-1) \cdot (n-2)\; \color{gray}{ \cdots } \; 3 \cdot 2 \cdot 1$$ Это число называется факториалом. И обозначается вот так: $n!$. $$n! = n \cdot (n-1) \cdot (n-2)\; \color{gray}{ \cdots } \; 3 \cdot 2 \cdot 1$$ Считается, что $0! = 1! = 1$ (и в самом деле, ведь у множеств из 0 элементов и из 1 элемента существует лишь одна перестановка). Вот несколько первых: $$0! = 1 \\ 1! = 1 \\ 2! = 2 \cdot 1 = 2 \\ 3! = 3 \cdot 2 \cdot 1 = 6 \\ 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24 \\ 5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120 \\ 6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720$$ Очевидное свойство: $n! = n \cdot (n-1)!$, например, $6! = 6 \cdot 5!$.

Задание. Попробуйте догадаться, сколько нулей в конце у $100!$, не заглядывая в ответ ниже.

Факториал растёт очень-очень быстро, например: $$100! = 93326215443944152681699238856266700490715968264381621 \\ 46859296389521759999322991560894146397615651828625369 \\ 7920827223758251185210916864000000000000000000000000$$ Так, вроде, нигде не ошибся. 158 знаков).