Перестановки без повторений

КОМБИНАТОРИКА

Факториал

Произведение всех натуральных чисел от 1 до n включительно называется факториалом числа n и записывается n! (читается как «эн факториал»).

n!=1⋅2⋅3⋅...⋅(n−2)⋅(n−1)⋅n.

Принято, что 0!=1.

1!=1;

2!=2⋅1=2;

3!=3⋅2⋅1=6;

4!=4⋅3⋅2⋅1=24;

5!=5⋅4⋅3⋅2⋅1=120;

6!=6⋅5⋅4⋅3⋅2⋅1=720.

Следующие два очень похожих свойства:

Доказываются они элементарно.

Эти две формулы позволяют, во-первых, легко считать факториал текущего натурального числа через факториал предыдущего числа, (или следующего через текущий.) Такие формулы в математике называются рекуррентными.

Во-вторых, с помощью этих формул можно упрощать и считать некоторые выражения с факториалами.

Вычислить:

Как действовать будем? Последовательно перемножать все натуральные числа от 1 до 1999 и от 1 до 2000? А вот по свойствам пример решается буквально в одну строчку:

Или так:

Упростить:

Снова работаем по свойствам:

Каждый больший факториал можно выразить меньшим факториалом, т. е.
n!=n(n−1)!=n(n−1)(n−2)!=n(n−1)(n−2)(n−3)! и т. д.

При увеличении значения n значение n! стремительно возрастает. Знак факториала удобно использовать, если нужно записывать большие числа.

Сочетания без повторений.

Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов?

Пример

Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?

Решение

Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:

Размещения без повторений.

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?

Пример

В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?

Решение.

В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:

Перестановки без повторений.

Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?