Закон исключенного третьего 9 страница

На первом шаге имеется два варианта: выбрать дубль (7 комбинаций) или не дубль (21 комбинация). В первом случае имеется 6 вариантов продолжения, во втором – 12.

Общее число благоприятных комбинаций равно: .

А всего вариантов выбора 2 костей из 28 равно 378; т. е. при большом числе экспериментов в 7 случаях из 9 (294/378 = 7/9) при выборе 2 костей одна кость окажется приложимой к другой.

14.3 Модели комбинаторных конфигураций

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

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

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

Определение. Сочетанием из по называется набор элементов, выбранных из данных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Определение. Композицией числа называется всякое представление в виде упорядоченной суммы целых положительных чисел.

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

14.3.1 Размещения без повторений

Рассмотрим задачу: Сколько разных 5-разрядных чисел можно записать с помощью десяти цифр при условии, что в числах не используются одинаковые цифры?

Перенумеруем разряды:

В первый разряд можно поставить одну из 10 цифр (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). Независимо от того, какая цифра помещена в первый разряд, во втором можно поставить только одну из 9 цифр, в третий – одну из 8 цифр и т. д. Всего существует различных пятиразрядных чисел, в каждом из которых нет двух одинаковых цифр.

В общем случае, если имеется позиций и n разных предметов, причем каждый представлен в единственном экземпляре, то количество разных расстановок равно .

Пример. Из группы в 25 человек требуется выбрать старосту, сенатора и профорга. Сколько вариантов выбора руководящего состава группы? Старосту выбрать можно одним из 25 способов. Поскольку выбранный староста не может быть сенатором, то для выбора сенатора остается 24 варианта. Профорга выбирают одним из 23 способов. Всего вариантов: .

Пример. На дискотеку пришло 12 девушек и 15 юношей. Объявлен “белый” танец. Все девушки выбрали для танцев юношей (и никто из них не отказался). Сколько могло образоваться танцующих пар?

14.3.2 Размещения с повторениями

Рассмотрим задачу: сколько разных 5-разрядных чисел можно составить из 10 цифр?

Перенумеруем разряды:

В первый разряд можно поставить одну из 10 цифр. Независимо от того, какая цифра поставлена, во второй разряд можно также поставить одну из 10 цифр и т. д. Всего получается 105 различных чисел.

Для двоичной системы счисления (используются только две цифры: 0 или 1) получаем 25 различных чисел.

Для системы с основанием и числом разрядов соответственно получаем: , где – число позиций (разрядов); – число элементов в каждой позиции (цифр).

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

Пример. Сколько разных чисел может содержать 10-разрядное слово в троичной системе счисления? В первый разряд можно поставить один из трех символов (0, 1 или 2), во второй разряд – также один из трех символов и т. д. Всего получаем чисел.

14.3.3 Перестановки без повторений

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

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

Пример. К кассе кинотеатра подходит 6 человек. Сколько существует различных вариантов установки их в очередь друг за другом?

Расставим 6 человек произвольным образом и начнем их переставлять всеми возможными способами. Число полученных перестановок в соответствии с формулой (5.3) будет равно 6! = 720.

14.3.4 Перестановки с повторениями

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

Пусть имеется предметов 1-го типа, предмета 2-го, предметов -го типа и при этом . Количество разных перестановок предметов равно .

Для обоснования данной формулы сначала будем переставлять n предметов в предположении, что они все различны. Число таких перестановок равно . Затем заметим, что в любой выбранной расстановке перестановка одинаковых предметов не меняет комбинации, аналогично перестановка одинаковых предметов также не меняет комбинации и т. д. Поэтому получаем выражение .

Пример. Найдем количество перестановок букв слова КОМБИНАТОРИКА. В этом слове 2 буквы к, 2 буквы о, 1 буква м, 1 буква б, 2 буквы и, 1 буква н, 2 буквы а, 1 буква т и 1 буква р.

Таким образом, число перестановок букв этого слова равно:

P(2, 2, 1, 1, 2, 1, 2, 1, 1) = 13!/(2! 2! 2! 2!)= 13!/16.

14.3.5 Сочетания без повторений

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

Эта формула может быть получена следующим образом. Выберем по очереди k предметов из n. Число вариантов будет равно . В этих расстановках выбранных предмета имеют свои определенные позиции. Однако нас не интересуют в данном случае позиции выбранных предметов. От перестановки этих предметов интересующий нас выбор не меняется. Поэтому полученное выражение нужно разделить на

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

Пример. В середине 60-х годов в России появились две лотереи, которые по недоразумению были названы “Спортлото”: лотерея 5/36 и 6/49. Рассмотрим 6/49. Играющий покупает билет, на котором имеется 49 клеточек. Каждая клеточка соответствует какому-либо виду спорта. Нужно выделить (зачеркнуть) 6 из этих клеточек и отправить организаторам лотереи. После розыгрыша лотереи объявляются шесть выигравших номеров. Награждается угадавший все шесть номеров, пять номеров, четыре номера и даже угадавший три номера. Соответственно, чем меньше угадано номеров (видов спорта), тем меньше выигрыш.

Подсчитаем, сколько существует разных способов заполнения карточек “Спортлото” при условии, что используется лотерея 6/49. Казалось бы, заполняя последовательно номер за номером, получим: 49 48 47 46 45 44.

Но ведь порядок заполнения не имеет значения, тогда получаем:

.

Эту же задачу можно решить и другим способом. Выпишем все номера подряд и под выбираемыми номерами поставим 1, а под остальными – 0. Тогда различные варианты заполнения карточек будут отличаться перестановками. При этом переставляются 6 предметов одного вида (единицы) и 49 – 6 = 43 предмета другого вида (нули), т. е. опять .

Если все участники заполняют карточки по-разному, то в среднем один из примерно 14 миллионов угадает все 6 номеров. А сколько человек в среднем угадают 5 номеров?

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

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

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

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

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

14.4 Контрольные вопросы и задания

1. Дайте определение r-выборки.

2. Перечислите основные задачи комбинаторного анализа.

3. Перечислите основные комбинаторные конфигурации (модели комбинаторных конфигураций).

4. Приведите примеры комбинаторных конфигураций.

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

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

7. Поясните правило произведения и приведите пример задачи, для решения которой используется данное правило.

8. Дайте определение понятия «перестановка». Приведите формулу расчета количества перестановок без повторения элементов в них.

9. Дайте определение понятия «перестановка». Приведите формулу расчета количества перестановок с повторением элементов в них.

10. Дайте определение понятия «размещение». Приведите формулу расчета количества размещений без повторения элементов в них.

11. Дайте определение понятия «сочетание». Приведите формулу расчета количества сочетаний без повторения элементов в них.

12 Дайте определение понятия «размещение». Приведите формулу расчета количества размещений с повторением элементов в них.

13. Дайте определение понятия «сочетание». Приведите формулу расчета количества сочетаний с повторением элементов в них.

Лекция 15. Принцип включения и исключения

15.1 Теорема и формула включений и исключений

Главная теорема комбинаторики (Теорема о включениях и исключениях). Пусть имеется множество из объектов произвольной природы. На этом множестве пусть задано свойств. Каждый объект может обладать либо не обладать некоторыми из этих свойств. Сами свойства обозначим: . Будем обозначать – количество объектов точно обладающих свойством и может быть какими-то другими, а – число объектов, не обладающих ни свойством , ни свойством . Тогда число объектов, не обладающих ни одним из перечисленных свойств:

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

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

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

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

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

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

Выпишем все числа от 1 до . Сколько чисел делится на ? Очевидно, , где обозначает целую часть числа x. Тогда, легко подсчитать количество чисел, не делящихся в данном диапазоне на

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

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

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

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

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

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

.

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

,

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

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

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

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

15.3 Контрольные вопросы и задания

1. Дайте определение главной теоремы комбинаторики (Теорема о включениях и исключениях).

2. Приведите общую постановку задачи включений и исключений

3. Приведите общую формулу включений и исключений.

4. В каких задачах применяется теорема о включениях и исключениях.

5. Что представляет собой решето Эратосфена?

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

Лекция 16. Задачи о распределении предметов по урнам (урновые схемы решения комбинаторных задач)

16.1 Задачи о размещении предметов

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

Если невозможно однозначно что-либо определить, то необходимо сделать предположение.

16.2 Распределение n разных предметов по k урнам

Количество размещений по k урнам n разных предметов при условии, что в первую урну попало предметов, во вторую – в последнюю – предметов, равно , .

16.3 Распределение n одинаковых предметов по k урнам

Установим, что n одинаковых предметов между k урнами можно разделить способами.

Количество искомых распределений n одинаковых предметов между урнами равняется количеству перестановок из предметов с повторениями предметов первого типа и предметов второго типа, т.е. равно .

Если делить справедливо, с уровнем справедливости , то каждый участок распределения должен получать минимум предметов. Тогда сначала раздадим каждому по предметов. После чего остается предметов, которые и распределим по усмотрению. Это можно сделать

способами.

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

Нужно разделить n разных предметов по урнам, емкость которых не ограничена. Первый предмет можно положить в любую из урн, второй(независимо от первого), тоже в урн и т.д. По правилу произведения предметы можно разделить способами.

16.5 Распределение разных предметов с учетом их порядка в урнах

Если не ограничивать количество предметов в урнах и если предметы не разнятся между собой, то количество таких распределений равно

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