Упражнение 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).

Сочетания

Сочетанием элементов множества X называется подмножество конечного множества AÍX. Если |A|=k, |X|=n, то подмножество X называется с очетанием из n по k. Например, сочетания трех цветов семицветной радуги будут описываться подмножествами, состоящими из трех элементов выбранных из множества, состоящего из 7 элементов.

Треугольник Паскаля и бином Ньютона. Для вычисления числа сочетаний построим таблицу, которая называется треугольником Паскаля. Она основана на следующей теореме:

Теорема 1. Число сочетаний удовлетворяет соотношениям:

; (при 0 < k < n).

Доказательство. Число пустых подмножеств равно 1. Стало быть, . Подмножества, состоящие из n элементов, совпадают со всем множеством, отсюда . Число сочетаний, не содержащих n -й элемент, равно , а содержащих – . Следовательно, при 0 < k < n,

Следующая таблица 2.1 строится на основе теоремы 1 и называется треугольником Паскаля.

Таблица 2.1

Треугольник Паскаля

 

n k

Теорема 2. Число сочетаний из n по k равно .

Доказательство. По индукции по n. При n=0 и k=0 получаем . Пусть теорема верна для n. С помощью теоремы 1 получаем

.

Откуда формула верна для n +1 и всех k < n +1.

Другой способ доказательства заключается в сопоставлении каждой инъекции ее образ. В этом случае, учитывая, что число инъекций с одинаковым образом равно k!, получаем Þ .

Теорема 3. (Бином Ньютона).

Доказательство. По индукции по n. Пусть формула верна для n. Тогда

Можно предложить также другое доказательство: Рассмотрим произведение n сомножителей (1 +x) (1 +x) × × × (1 +x). Сомножители будем рассматривать как ящики. Произведение равно сумме степеней x^k, причем при каждом k слагаемые x^k получаются выбором из ящиков k элементов, равных x. Отсюда коэффициент при x^k будет равен количеству содержащих k элементов подмножеств множества, состоящего из n элементов.