Изучение основ комбинаторики и теории вероятностей (стр. 4 из 17)

из не угаданных (

). Итого: человек из 14 миллионов

угадают 5 номеров. А сколько угадают 4 номера? Выберем из 6 угаданных два и затем из 43 не угаданных тоже два и перемножим число вариантов выбора. Тогда получим:

человек.

Аналогично найдем, что 3 номера угадают 246820 человек, т. е. примерно 1,77% от всех играющих.

1.3.7. Сочетания с повторениями

Пример. Требуется купить 7 пирожных. В магазине имеются пирожные следующих видов: эклеры, песочные, слоеные и наполеоны. Сколько вариантов выбора? Решение: выбранные пирожные заменяем единицами, и добавляем три нуля (разделителя). Каждой перестановке однозначно соответствует некоторый выбор. Например, одному из вариантов покупки будет соответствовать такой код: 1101110101. Пирожные покупаются следующим образом. Количество единиц слева до первого нуля соответствует покупке эклеров, между первым и вторым нулем - покупке песочных, между вторым и третьим - покупке слоеных, единицы после третьего нуля соответствуют числу покупаемых наполеонов. В случае приведенного кода покупается 2 эклера, 3 песочных, 1 слоеное и 1 наполеон. Количество вариантов покупки пирожных равно числу перестановок из 7 объектов одного типа (единиц) и 3 объектов второго типа (нулей).

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

(7)

1.3.8. Свойства чисел сочетаний

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

1.

.

2.

.

3.

.

Первое свойство совершенно очевидно. Давайте проверим:

.

Второе легко доказывается, если оба члена правой части представить по формуле (6).

Третье свойство можно доказать методом математической индукции. Для примера, при п = 2 имеем:

.

Для п = 3 получаем:

.

Подчеркнем, что числа размещений, перестановок и сочетаний связаны равенством

.

1.4. Основные комбинаторные задачи

1.4.1. Главная теорема комбинаторики (Теорема о включениях и исключениях)

Пример. На предприятии работает 67 человек. Из них 48 знают английский, 35 - немецкий и 27 - оба языка. Сколько человек не знают ни английского, ни немецкого?

Результат можно получить следующим образом. Построим диаграмму, на которой изобразим прямоугольник, соответствующий общему числу работающих (67) и две пересекающиеся области А и В по 48 и 35 человек (знающих английский и немецкий языки). На диаграмме общая часть этих двух областей соответствует 27 - количеству работающих, которые знают оба языка. Требуется найти область прямоугольника, не входящую ни в область А, ни в область В.

67

A=48 A

B=27 B=35

Очевидно, что N = 67 - 48 - 35 + 27 = 11.

Главная теорема комбинаторики (Теорема о включениях и исключениях)

Пусть имеется множество из N объектов произвольной природы. На этом множестве пусть задано п свойств. Каждый объект может обладать либо не обладать некоторыми из этих свойств. Сами свойства обозначим:

. Будем обозначать N( ) - количество объектов точно обладающих свойством и может быть какими-то другими, а N ( ) - число объектов не обладающих ни свойством , ни свойством . Тогда число объектов, не обладающих ни одним из перечисленных свойств:

(8)

Продолжение примера. Пусть теперь 20 человек знают французский, 12 - английский и французский, 11 - английский и немецкий и 5 - все три языка.

Тогда в соответствии с теоремой количество человек, не знающих ни одного из трех перечисленных языков (но может быть знающих китайский язык), равно N= 67 - 48 - 35 - 20 + 27 +12+11-5 = 9.

Решето Эратосфена

Выпишем все числа от 1 до N. Сколько чисел делится на k?Очевидно, [N/k],где [х] обозначает целую часть числа х. Тогда, легко подсчитать количество чисел, не делящихся в данном диапазоне на k₁k₂, k₃...

Пример. Сколько чисел от 1до 100 не делятся ни на 5, ни на 7?

Воспользуемся теоремой о включениях и исключениях. Под первым свойством чисел будем понимать делимость на 5, под вторым – делимость на 7. На 5 делятся 20 чисел. На 7 делятся 14 чисел. На 35 делятся 2 числа. Следовательно, не делятся на 5 и 7: 100 - 20 - 14 + 2 = 68 чисел.

1.4.2. Частный случай теоремы о включениях и исключениях

В некоторых случаях количество объектов, обладающих определенным набором свойств, зависит только от числа этих свойств. Тогда формула для подсчета числа объектов, не обладающих ни одним из выделенных свойств, упрощается.

При произвольном п имеем:

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

(9)

Полученное значение D_nиногда называют формулой полного беспорядка или субфакториалом. Субфакториал D_nможно представить и так:

.

где выражение в [...] стремится к е ^-1 при неограниченном возрастании.

Субфакториал имеет свойства, похожие на свойства обычного факториала. Например,

- для обычного факториала,

- для субфакториала.

Субфакториалы легко вычисляются по формуле

. Приведем некоторые начальные значения субфакториалов:

п	1	2	3	4	5	6	7	8	9
Dn п	0	1	2	9	44	255	1784	14273	128456

1.4.3. Комбинаторные задачи с ограничениями

Рассмотрим несколько типов задач, в которых на комбинации накладываются определенные ограничения.

а) Задача о львах и тиграх. Имеется 5 львов и 4 тигра. Необходимо их расставить в ряд, но при этом известно, что тигр не может идти спокойно за тигром. Тогда расставляем львов с промежутками ( их будет 6) и в них вставляем тигров. Таким образом, если тигры и львы обезличенные, то

= 15. В общем случае при п львах и к тиграх имеем:

б)Задача о книжной полке. Из nкниг, стоящих на полке, нужно
выбрать к таких, которые не стояли рядом на книжной полке. Отберем
сразу к книг, останется п-к. Их расставим с промежутками (п-к+1 промежуток). На эти места вставим к книг. Общее решение:

(10)

в)Рыцари короля Артура. 12 рыцарей сидят за круглым столом.
Нужно выбрать 5 из них, но таких, которые не сидели рядом за столом.
Множество всех решений разбиваем на два подмножества в зависимости от того, входит ли в команду избранных конкретный рыцарь или
нет? Ответ: 15+21=36. Если за круглым столом сидит п рыцарей, а
нужно выбрать к, которые не сидели рядом, то задача решается аналогично и имеет смысл при п > 2к.