Тема: Примеры комбинаторных задач. Перестановки

Оформить конспект в тетради. Выделенное зеленым записать в тетрадь.

Тема: Примеры комбинаторных задач. Перестановки

Комбинаторика - раздел математики, посвящённый решению задач выбора и расположения элементов в соответствии с данными условиями.

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

Слово «комбинаторика» происходит от латинского слова combinare, которое означает «соединять, сочетать».

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

Виды задач: 1) Задачи, решаемые перебором возможных вариантов;

2) Задачи, решаемые при помощи построения дерева возможных вариантов;

3) Задачи, решаемые при помощи составления таблицы

Примеры:

1) Из группы теннисистов, в которую входят четыре человека – Антонов, Григорьев, Сергеев и Федоров, тренер выделяет двоих для участия в соревнованиях пар. Сколько существует вариантов выбора такой пары?

Решение:

АГ, АС, АФ -пары, в которые входит Антонов (для краткости будем писать первые буквы фамилий).

ГС, ГФ -пары, в которые входит Сергеев, но не входят Антонов и Григорьев.

СФ -пары, в которые входит Сергеев, но не входят Антонов и Григорьев.

Других вариантов составления пар нет, так как все пары, в которые входит Федоров, уже составлены.

Итак, мы получили шесть пар: АГ, АС, АФ, ГС, ГФ, СФ.

Ответ: 6 вариантов.

2):

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

Решение: Обед состоит из первого и второго блюда:

Первые блюда: борщ и рассольник Б Р

Вторые блюда: гуляш, котлеты, сосиски, пельмени Г К С П Г К С П

Итак, мы получили восемь возможных вариантов обедов: БГ, БК, БС, БП, РГ, РК, РС, РП,

Ответ: 8 вариантов.

3):

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

Решение: Решим задачу с помощью таблицы, записав в верхнюю строку варианты хлебобулочных изделий: булочка (Б), ватрушка (В), кекс (К), а в левый столбик варианты напитков – сок (С), чай (Ч), компот (Кт). В остальных строках и столбцах мы их соединяем по парам.

	Б	В	К
С	СБ	СВ	СК
Ч	ЧБ	ЧВ	ЧК
Кт	КтБ	КтВ	КтК

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

Ответ: 9 вариантов.

Решения этих задач основаны на общем правиле умножения

Пусть имеется n элементов и требуется выбрать из них один за другим к элементов. Если первый элемент m₁выбрать n₁ способами, после чего второй элемент m₂ выбрать n₂ способами из оставшихся, затем третий элемент m₃ выбрать n₃ способами из оставшихся и т.д., то число способов могут быть выбраны все к элементов, равно произведению

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

Для 3-х элементов (n =3) мы получили 6 перестановок, т.е.