Схема урн

Схема урн — основная математическая модель, используемая в перечислительной комбинаторике.

Представим себе непрозрачную урну, в которой находятся пронумерованных шаров.

Мы хотим ответить на вопрос: сколько различных наборов из шаров мы можем составить из шаров, находящихся в урне?

Для того, чтобы ответить на поставленный вопрос, необходимо ответить на два вспомогательных вопроса:

1. Как мы будем составлять эти наборы?
2. Что мы считаем различными наборами?

На первый вопрос мы может быть два ответа: мы не будем возвращать шары в урну (выбор без повтора) или мы будем возвращать шары в урну (выбор с повтором).

На второй вопросы мы также можем дать два ответа: порядок шаров нам не важен (выбор без учёта порядка) и порядок шаров нам важен (выбор с учётом порядка). В первом случае наборы и — это один и тот же набор (отличается, как можно заметить, исключительно порядком шаров), во втором — это разные наборы.

Рассмотрим по порядку все возможные схемы выбора.

Выбор без повтора без учёта порядка.

Число наборов шаров из называется размещением из по и обозначается (от англ. allocation — размещение).

Попробуем сконструировать формулу. Первый элемент нашего набора мы можем выбрать способами (выбрать любой из шаров, находящихся в урне). Поскольку в нашей схеме мы не возвращаем шары в урну, второй элемент мы сможем выбрать уже только способами, т. к. в урне на этот момент останется именно шаров. Аналогично, третий элемент мы сможем выбрать способами, и так далее до –ого элемента, который мы сможем выбрать способами.

Всего, таким образом число способов, которыми мы можем выбрать шаров из без повтора и без учёта порядка будет равно: