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

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

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

Правило произведения. Если объект может быть выбран способами из имеющихся элементов, объект - способами из оставшихся элементов, объект - способами и т.д., то существует способов выбора совокупности объектов .

Пример. В группе 25 студентов. Сколькими способами можно выбрать в этой группе старосту, профорга и физорга?

Решение.

1. Старостой может быть каждый студент, тогда имеется 25 возможностей выбора старосты.

2. После выбора старосты осталось 24 студента, любой из них может быть профоргом. Следовательно, имеется 24 возможности выбора профорга.

3. Аналогично рассуждая, получаем 23 возможности выбора физорга.

Выбор старосты сочетается с выбором профорга и с выбором физорга.

Таким образом, всего возможностей выбора трёх должностей будет .

Ответ: 13800.

Правило суммы. Если множество состоит из элементов, - из элементов, …, причём эти множества не имеют общих элементов, то выбор элемента либо из , либо из , … можно осуществить способами.

Пример. На книжной полке стоит 20 книг по алгебре, 12 – по теории вероятностей, 7 – по истории, 25 – по литературе и 6 – по геометрии. Сколькими способами можно выбрать книгу по математике?

Решение.

Всего книг по математике 20+12+6=38. Значит, имеется 38 способов выбора книги по математике.

Ответ:38.

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

Определение 11. Перестановки из элементов – комбинации, состоящие из всех элементов и отличающиеся друг от друга лишь порядком следования элементов.

Обозначаются перестановки из элементов - , при этом вычисляется число таких комбинаций по формуле

Полагаем, что 0!=1!=1.

Примеры.

1) Сколько пятизначных чисел можно составить из цифр 0,2,4,6,8, если числа в цифрах не повторяются.

Решение.

- число способов перестановки пяти цифр.

- число «пятизначных» чисел, начинающихся с «0». Тогда - число пятизначных чисел.

Ответ:96.

2) На трёх карточках написаны буквы У, К, Ж. После тщательного перемешивания берут по одной карточке и кладут последовательно рядом. Какова вероятность, что получится слово «ЖУК»?

Решение.

Пусть - событие «получится слово «ЖУК».

- число способов получения слова «ЖУК» из букв У, К, Ж;

- число слов, которые можно получить из букв У, К, Ж.

Значит, .

Ответ: .

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

Решение.

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

- общее число способов рассаживания 7 учеников,

- число способов рассаживания 7 учеников, когда 3 определённых ученика окажутся рядом (3 ученика рассматриваются как один, тогда 1+4=5 учеников можно рассадить 5! способами, при этом внутри «тройки» ученики могут пересаживаться 3! способами; так как одни способы рассаживания нужно рассматривать в совокупности с другими, то по правилу произведения получим способов рассаживания учеников).

Значит, .

Ответ: .

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

Обозначение размещений из элементов по - . Вычисляется число таких комбинаций по формуле

, где

Примеры.

1) Сколько различных натуральных чисел можно записать с помощью цифр 0, 1, 2, 3, 4, если цифры в числах не повторяются?

Решение.

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

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

Количество однозначных чисел - (это числа 1, 2, 3, 4).

Количество двузначных чисел - (так как - число упорядоченных пар цифр, составленных из 0,1,2,3,4, то среди них могут быть числа вида 01, 02, 03, 04, которые не являются двузначными; количество таких чисел равно числу размещений ).

Количество трёхзначных чисел - ( - число «трёхзначных» чисел, начинающихся с «0»).

Количество четырехзначных чисел - .

Количество пятизначных чисел - .

Итак, общее число натуральных чисел, записанных с помощью цифр 0,1, 2, 3, 4, равно: 4+16+48+96+96=260.

Ответ:260.

2) Из букв слова «событие», составленного с помощью разрезной азбуки, извлекаются наудачу и складываются друг за другом в порядке их извлечения 3 карточки (буквы). Какова вероятность получить при этом слово «быт»?

Решение.

Пусть - событие, состоящее в том, что получено слово «быт».

- число способов получения слова «быт» (это слово получится только при условии: если из трёх извлечённых карточек первой будет буква «б», второй – «ы», третьей – «т»).

- общее число способов извлечения трёх карточек из семи.

Тогда .

Ответ: .

3) Числа 1,2,3,4,5 написаны на 5 карточках. Наудачу последовательно вынимаются 3 карточки, и вынутые таким образом цифры ставятся слева направо. Чему равна вероятность того, что полученное таким образом трёхзначное число окажется чётным?

Решение.

Виды трёхзначных чётных чисел, составленных из указанных цифр: и .

- событие «получено чётное трёхзначное число».

- общее число полученных трёхзначных чисел;

- число чётных трёхзначных чисел указанного выше вида, где число способов заполнения ** в одной модели чётного числа (т.к. одна цифра уже задействована, то две цифры из четырёх с учётом порядка можно взять числом способов, равным ).

.

Ответ: .

Определение 13. Сочетания из элементов по - комбинации, каждая из которых содержит элементов из данных , при этом одна комбинация отличается от другой лишь составом элементов, но не порядком расположения элементов.

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

Примеры.

1) Сколькими различными способами можно назначить в патруль трёх солдат и одного офицера, если имеется 15 солдат и 4 офицера?

Решение.

Трёх солдат из 15 можно выбрать: способами (порядок следования солдат в каждой выборке неважен).

Одного офицера из четырёх можно выбрать: способами.

Выбор офицера сочетается с выбором солдата, поэтому всего способов: .

Ответ: 1820 способов.

2) В экзаменационный билет входят 4 вопроса программы, насчитывающей 45 вопросов. Абитуриент не знает 15 вопросов программы. Какова вероятность того, что он вытянет билет, где все вопросы ему известны?

Решение.

1 способ.

Пусть - событие, состоящее в том, что студент вытянет билет, где все вопросы ему известны.

- общее число способов формирования билетов для экзамена;

- число удачных для студента способов формирования билетов.

.

2 способ.

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

- «студент знает 1-ый вопрос билета»,

- «студент знает 2-ой вопрос билета»,

- «студент знает 3-ий вопрос билета»,

- «студент знает 4-ый вопрос билета».

Таким образом, , где , , , - зависимые события. Тогда Ответ: 0,2.

3) В коробке 4 красных и 6 зелёных карандашей. Случайно выпало 3 карандаша. Какова вероятность того, что 2 из них – красные?

Решение.

Пусть - событие, состоящее в том, что из трёх выпавших карандашей 2 – красные.

- число способов выбора 3 карандашей из 10;

- число способов выбора 2 красных и 3-2=1 зелёного карандаша (каждый способ выбора 2-ух красных карандашей нужно рассматривать в совокупности с каждым способом выбора 1 зелёного карандаша).

.

Ответ: 0,3.

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