2.1. Размещения

Постановка задачи. Дано m предметов и n ящиков, в которые размещаются предметы. Сколько существует размещений, удовлетворяющих некоторым заданным условиям?

Определение 1. Размещением с повторениями называется функция

f: {x₁, x₂,, x_m }{y₁,y₂,,y_n }.

Элементы x_iназываютсяпредметами, аy_j ящиками.

Полагая a_i=f(x_i ) , легко убедиться в том, что число всех размещений с повторениями равно количеству последовательностей {a₁,a₂,, a_m} чисел 1a_inи значит оно равноn^m.

Определение 2. Рассмотрим некоторое конечное множество равновероятных элементарных событий, которые мы будем иногда назвать исходами. Событием называется подмножество множества всех исходов. Его элементы называются благоприятными исходами. Вероятность события определяется как отношение количества благоприятных исходов к количеству всех исходов.

Например, если мы бросаем монету, то возможны два исхода. Число исходов выпадения «орла» равно 1. Значит, вероятность выпадения орла равно 0.5.

Упражнение 1. Бросают две игральные кости. Найти вероятность выпадения 10 очков.

Решение.Напомним, что игральная кость – это кубик, каждой грани которого соответствует одно число от 1 до 6. В данном случае число всех исходов равно 6². Благоприятные исходы: (4,6), (5,5), (6,4). Отсюда вероятность равнаp=3/36=1/12.

Определение 3. Размещением называется произвольная инъекция

f: {x₁, x₂,, x_m}{y₁,y₂,,y_n }.

(В каждый ящик размещают не более одного предмета.)

Теорема 1. Число размещений равно.

Доказательство.Первый предмет можно разместитьnспособами, второй –n-1, , m-й – n-m+1. Получаем.

Упражение 2. В группе m студентов. Найти вероятность того, что найдется два студента, родившиеся в один день года.

Решение.Полагаем, что год не високосный. Число всех вариантов 365^m. Число неблагоприятных вариантов равно, гдеn=365. Получаем. Ниже приводится результаты вычислений значений вероятности при различныхm:

Например, если число студентов равно 23, то вероятность равна примерно 0.5.

Определение 4. Пусть заданыmящиков.Упорядоченным размещенииемпредметовa₁, a₂, , a_nназывается указание последовательности предметов для каждого ящика, при котором каждый предмет участвует ровно один раз.

Пример 1. На рисунке 2.1 показаны упорядоченные размещения предметов a, b по трем ящикам.

ba ab a b a b b a ba

ab a b b a b a ba ab

Рис. 2.1. Упорядоченные размещения

Сначала размещается буква aв первый ящик и одним из четырех способов размещаетсяb. Потом букваaразмещается во второй ящик, в этом случае сноваbразмещается одним из четырех способов. Затем букваaразмещается в третий ящик, букваbразмещается одним из четырех способов. Всего получаем 12 упорядоченных размещений.

Теорема 2. Число [m]ⁿ упорядоченных размещений n предметов в m ящиков равно m(m+1) ∙ ∙ ∙ (m+n1).

Доказательство.После размещения первого предмета в ящик одним изmспособов

a1

∙ ∙ ∙

второй предмет может быть размещен одним из m+1способов. Предположим, что уже размещеноi1предметов, и пусть приk=1, 2, …, mвk-м ящике находитсяr_kобъектов. Тогдаi-й объект может быть добавлен одним из

(r₁+1) + (r₂+1) + ∙ ∙ ∙ + ( r_m+1) =i1+m

способов. Отсюда число всех упорядоченных размещений будет равно

m(m+1) ∙ ∙ ∙ (n1+ m).