Урны и шарики

Есть урна (ящик), содержащая пронумерованных объектов (шаров). Мы выбираем из этой урны шаров; результатом выбора является набор из k шаров. Нас интересует, сколькими способами можно выбрать k шаров из n, или сколько различных результатов может получиться. На этот вопрос нельзя дать однозначный ответ, пока мы не определимся: а) с тем, как организован выбор (можно ли шары возвращать в урну), и б) с тем, что понимается под различными результатами выбора.

Рассмотрим следующие возможные способы выбора.

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

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

Условимся, какие результаты выбора (наборы из номеров шаров) мы будем считать различными. Есть ровно две возможности.

1. Выбор с учётом порядка: два набора номеров шаров считаются различными, если они отличаются составом или порядком номеров. Так, при выборе трёх шаров из урны, содержащей 5 шаров, наборы (1, 5, 2), (2, 5, 1) и (4, 4, 5) различны, если порядок учитывается.

2. Выбор без учёта порядка: два набора номеров шаров считаются различными, если они отличаются составом. Наборы, отличающиеся лишь порядком следования номеров, считаются одинаковыми.

Так, наборы (1, 5, 2) и (2, 5, 1) не различаются и образуют один и тот же результат выбора, если порядок не учитывается.

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

Упражнение 2. Перечислить все возможные результаты в каждой из четырёх схем при выборе двух шаров из четырёх. Например, при выборе с возвращением и без учёта порядка: (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4).

Выбор без возвращения, с учётом порядка

Теорема 2. Общее количество различных наборов при выборе элементов из без возвращения и с учётом порядка равняется

и называется числом размещений из элементов по элементов.

Следствие 1. Если в множестве элементов, то существует ровно перестановок этих элементов.

Доказательство. Перестановка — результат выбора без возвращения и с учётом порядка элементов из . Поэтому общее число перестановок равно

Упражнение 3. Найти, сколько всего возможно различных результатов в следующих экспериментах:

а) из колоды в 36 карт без возвращения, с учётом порядка вынимают три карты;

б) Вася, Петя, Оля и Лена занимают какие-то четыре из десяти мест в классе;

в) из русского алфавита выбирают четыре разные буквы и составляют слово;

г) из различных цифр, не равных нулю, составляется трёхзначное число.

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

Теорема 3. Общее количество различных наборов при выборе элементов из без возвращения и без учёта порядка равняется

и называется числом сочетаний из элементов по элементов.

Упражнение 4. Найти, сколько всего возможно различных результатов в следующих экспериментах:

а) из колоды в 36 карт без возвращения, без учёта порядка вынимают три карты;

б) из русского алфавита выбрасывают четыре буквы.

Выбор с возвращением и с учётом порядка

Теорема 4. Общее количество различных наборов при выборе элементов из с возвращением и с учётом порядка равняется .

Упражнение 5. Найти, сколько всего возможно различных результатов в следующих экспериментах:

а) из колоды в 36 карт тянут три раза карту с учётом порядка и с возвращением;

б) пятизначное число составляется из одних нечётных цифр;

в) обезьяна напечатала на машинке слово из десяти букв.

Выбор с возвращением и без учёта порядка

Рассмотрим урну с двумя пронумерованными шарами и перечислим результаты выбора двух шариков из этой урны при выборе с возвращением.

с учётом порядка	без учёта порядка
(1,1)	(1,1)
(2,2)	(2,2)
(1,2) (2,1)	}…. (1,2)...

Видим, что в схеме «без учёта порядка» получилось три различных результата, в отличие от четырёх результатов в схеме «с учётом порядка». Заметим также, что никаким делением на «число каких-нибудь перестановок», которое помогло избавиться от учёта порядка при выборе без возвращения, число 3 из числа 4 получить не удастся.

Теорема 5. Общее количество различных наборов при выборе элементов из с возвращением и без учёта порядка равняется

Упражнение 6. Проверить, что при и получается ровно 3.

Доказательство. Рассмотрим подробно, чем отличаются друг от друга два разных результата такой схемы выбора. Нам не важен порядок номеров, т.е. мы учитываем только, сколько раз в нашем наборе из номеров шаров появился каждый номер. Поэтому результат выбора можно представить набором чисел , в котором — число появлений шара номер в наборе, и . Числа принимают значения из . Два результата выбора в схеме выбора с возвращением и без учёта порядка различаются, если соответствующие им наборы не совпадают (порядок следования элементов учитывается).

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

А теперь изобразим результат такого размещения в виде схемы, в которой вертикальные линии обозначают перегородки между ящиками, а точки — находящиеся в ящиках шары:

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

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

Осталось заметить, что способов расставить шаров на местах существует

Именно столько есть способов выбрать из номеров мест номеров мест для шаров.

Дата добавления: 2015-07-26