Схема урн

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

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

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

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

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

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

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

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

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

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

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

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

Пример: сколькими способами мы сможем случайно выбрать 4 человек для первого «захода» на экзамен по теории вероятностей и математической статистике из 10 студентов, находящихся в коридоре?

Почему данная задача сводится именно с схеме выбора без повтора и без учёта порядка? Во-первых, мы не можем выбрать дважды одного и того же студента, значит это схема без повтора. Во-вторых, порядок наших студентов при отборе не важен. Набор студентов, состоящий из Иванова, Петрова, Смирнова и Ковалёва — это в точности тот же набор, что и набор Петров, Ковалёв, Смирнов и Иванов.

Важным частным случаем размещения является перестановка. Перестановка — это число размещений из элементов по элеметов. Перестановки обозначаются (от англ. permutation — перестановка, читается пэ из эн). Переставновка по определению:

Пусть, в продолжении нашего примера, в аудитории, где проходит экзамен, находится всего четыре парты (или только четыре парты специально выделены для экзаменуемых). Сколькими способами мы можем рассадить четырёх студентов за эти четыре парты?

Из тех же соображений, что и были описаны выше, наше решение — это число размещение из 4 по 4. Таким образом ответ на наш вопрос — каково число перестановок из 4 студентов:

За первую парту мы можем посадить любого из четырёх студентов, за вторую — любого из трёх оставшихся, за третью — одного из двух, а последняя парта достанется последнему оставшемуся студенту. Это так же схема без повтора (одного студента мы можем посадить исключительно на одно место) и без учёта порядка (нам не важно, сначала сажать на первую парту или на любую другую из оставшихся).