Элементы комбинаторики

Пусть дано множество , состоящее из элементов. Существуют два принципиально различных способа выбора элементов из множества : выбор элементов без возвращения и выбор элементов с возвращением.

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

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

.

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

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

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

Число сочетаний вычисляется по формуле

.

Свойства сочетаний:

Пример 8. Пусть имеется множество из трёх элементов. Тогда все размещения двух элементов из трёх таковы: Все перестановки множества имеют вид: и Все сочетания двух элементов из множества таковы:

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

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

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

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

При решении комбинаторных задач могут быть полезны следующие два правила:

Правило суммы: если объект может быть выбран способами, а объект может быть выбран способами, то выбор «либо , либо » может быть осуществлен способами.

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

Пример 9. Пусть имеется групп элементов, причем -я группа состоит из – элементов. Выберем по одному элементу из каждой группы, тогда общее число способов, которыми можно произвести такой выбор по правилу произведения

. (1)

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

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

Решение. Вначале посчитаем общее количество исходов. Первый из студентов выбирает одно из 10 чисел, Второй и третий делают то же самое, Согласно формуле (1), общее число способов будет равно Подсчитаем число благоприятных исходов. Для этого сначала найдем общее число комбинаций задуманных чисел, в которых нет совпадений. Первый студент может выбрать любое из 10 чисел, второй любое из 9 чисел, а третий студент – любое из оставшихся 8 чисел. Поэтому общее число комбинаций задуманных чисел, в которых нет совпадений, по формуле (1) равно Остальные случаи (1000 – 720 =280) характеризуются наличием хотя бы одного совпадения. Следовательно, искомая вероятность равна

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

Решение. Русский алфавит содержит 33 буквы. Так как по линии связи передаются все буквы, то число равновозможных исходов опыта . Из этих исходов благоприятными появлению события {появится последовательность букв, которая начинается словом «мир»} будут все исходы, в которых на первых трех позициях будет стоять слово «мир» (такому выбору соответствует один исход), а остальные позиции будут заполнены любым образом (число таких вариантов ). По правилу произведения число благоприятных исходов .

Следовательно,

.

Пример 12. Из урны, содержащей 3 шара, три раза наудачу вынимается по одному шару с возвращением каждый раз обратно. Найти вероятность того, что в руке перебывают все шары.

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

Число всех возможных исходов данного опыта – это число размещений из трех элементов по три с повторениями, то есть

.

Благоприятными событию A ={ } будут те исходы, в которых элементы (шары) не будут повторяться. Число таких исходов – это число размещений из трех элементов по три, или число перестановок из трех элементов, то есть . Так как все исходы опыта равновозможные, то

.

Пример 13. Технический контроль проверяет из партии в 500 деталей 20 деталей, взятых наудачу. Партия содержит 15 нестандартных деталей. Какова вероятность того, что среди проверяемых деталей будет ровно две нестандартные?

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

Порядок следования стандартных и нестандартных деталей в извлекаемых 20 не играет роли. Важно только количество стандартных и нестандартных деталей. Следовательно, количество всех возможных способов, которыми это можно сделать, равно , то есть .

Событию ={среди проверяемых деталей будет ровно две нестандартные} (следовательно, остальные 18 должны быть стандартными), будет соответствовать (правило произведения) исходов, то есть . Таким образом,

.

Пример 14. Трехзначное число составляется следующим образом: бросаются три игральные кости: белая, синяя и красная; число выпавших очков на белой кости – это число сотен, число выпавших очков на синей кости – это число десятков, а число выпавших очков на красной кости – это число единиц трехзначного числа. Какова вероятность того, что полученное таким образом число будет больше 456?

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

Посчитаем количество исходов опыта, благоприятных появлению события А. Числа, большие 456, будут получаться, если число сотен будет больше 4, то есть 5 или 6 или число сотен будет равно 4, а число десятков будет больше чем 5, то есть 6. Пусть число сотен будет равно 5. Таких опытов будет так как число десятков и единиц может произвольно меняться от 1 до 6. Такие же рассуждения справедливы, если число сотен равно 6. Опытов, у которых первые две цифры 45 будет 6. Используя правила произведения и суммы, найдем количество таких чисел . Так как все исходы опыта равновозможные, то искомая вероятность .

Пример 15. Трем радиостанциям разрешена работа на шести различных частотах. Определить вероятность того, что, по крайней мере, две радиостанции будут работать на одинаковых частотах, если выбор частот производится наугад.

Решение. Число всех равновозможных исходов опыта – это число размещений из шести элементов (частот) по три с повторениями, то есть . Благоприятными событию A ={по крайней мере, две радиостанции будут работать на одинаковых частотах} будут те исходы, в которых элементы (частоты) будут повторяться. Число таких исходов – представляет собой сумму исходов, в которых две радиостанции работают на одной частоте – и три радиостанции работают на одной частоте – . Число исходов, в которых две из трех радиостанций могут работать на одной из шести частот, – это . Число различных частот – 6. Третья радиостанция может работать на одной из пяти «незанятых» частот. По правилу произведения . Очевидно, что число исходов (три радиостанции будут работать на одной частоте) равно 6 .

Таким образом, .

Следовательно, .