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

Правило умножения (основная формула комбинаторики)

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

Пример 1

Монету подбросили 3 раза. Сколько различных результатов бросаний можно ожидать?

Решение

Первая монета имеет альтернативы – либо орел, либо решка. Для второй монеты также есть альтернативы и т.д., т.е. .

Искомое количество способов:

Правило сложения

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

Пример 2

На полке 30 книг, из них 20 математических, 6 технических и 4 экономических. Сколько существует способов выбора одной математической или одной экономической книги.

Решение

Математическая книга может быть выбрана способами, экономическая - способами.

По правилу суммы существует способа выбора математической или экономической книги.

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

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

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

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

Пример 3

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

Решение

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

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

Пример 4

Сколькими способами можно рассадить 4 человек за одним столом?

Решение

Каждый вариант рассадки отличается только порядком участников, то есть является перестановкой из 4 элементов:

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

Общее число различных способов, которыми можно произвести выбор с возвращением элементов из генеральной совокупности объема , равно

Пример 5

Лифт останавливается на 7 этажах. Сколькими способами могут выйти на этих этажах 6 пассажиров, находящихся в кабине лифта?

Решение

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

Сочетания

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

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

Число сочетаний из элементов по равно:

Пример 6

В ящике 9 яблок. Сколькими способами можно выбрать 3 яблока из ящика?

Решение

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

Количество способов, которыми можно выбрать 3 яблока из 9:

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

Число сочетаний с повторениями из элементов по :

Пример 7

На почте продают открытки 3 видов. Сколькими способами можно купить 6 открыток?

Это задача на отыскание числа сочетаний с повторениями из 3 по 6:

Разбиение множества на группы

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

Число разбиений на групп, когда в первую попадают элементов, во вторую - элементов, в k-ю группу - элементов, равно:

Пример 8

Группу из 16 человек требуется разбить на три подгруппы, в первой из которых должно быть 5 человек, во второй – 7 человек, в третьей – 4 человека. Сколькими способами это можно сделать?

Тип и особенности: урок открытия и изучения новых знаний с помощью решения практико-ориентированных задач .

Цель урока: научить учащихся решать комбинаторные задачи методами: 1) конечного перебора; 2) построения дерева возможных вариантов; 3) с помощью таблицы.

Оборудование: компоненты УМК «Виленкин. 5», проектор, компьютер, интерактивная доска (ИД ) , на каждой парте по 2 листа (формата А4) с 7 решенными классными задачами и по 2 листа (формата А4) с 7 тестовыми задачами . На столе учителя лежат лист (формата А4) с 7 решенными классными задачами и лист (формата А4) с 7 тестовыми задачами их решениями, распечатки проектного задания на дом.

Этапы урока

Задачи этапа

Визуальный ряд

Деятельность учителя

Деятельность учащихся

Формируемые УУД

Организационный

Собрать домашнее задание, настроить на урок

Слайд на доске:

«тяжело в учении легко в бою»

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

Дежурные проходят по классу собирают тетради.

Саморегуляция, прогнозирование и оценка

Актуализации теоретических знаний

Определить цель урока

На доске: дата и название темы: «Комбинаторные задачи»

Ребята, сегодня мы совершим увлекательное путешествие в мир «Комбинаторики»

Мысленно задают вопрос: «а что это такое»

Целеполагание, предметная рефлексия.

Объяснения нового материа

ла

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

методами, способами

решения

комбинаторных задач

Слайд на доске: Слово «комбинаторика» произошло от латинского слова COMBINARE , что означает «соединять», «сочетать»

Учитель задаёт вопрос как вы думаете что означает слово «комбинаторика»?

Учитель делает паузу, слушает ответы потом говорит определение.

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

Дети отвечают, выдвигая гипотезы

Внимательно слушают, читают определение на раздаточных листках

Выдвижение и проверка гипотез.

Слайд на доске

Чтобы запереть чемодан с кодовым замком, состоящий из двух каких-либо цифр. Хозяин чемодана решил использовать только цифры 1, 2 и 3. Сколькими способами он может выбрать код?

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

Внимательно слушают, смотрят слайд, думают, запоминают.

Смысловое чтение.

Слайд на доске:

Решение древом возможных

Вариантов

ДЕРЕВО ВОЗМОЖНЫХ ВАРИАНТОВ Часто процесс перебора удобно осуществлять путем построения специальной схемы - так называемого дерева возможных вариантов

изобразите корень дерева, для этого поставьте знак *.

Чтобы выбрать первую цифру кода, у нас есть три варианта: 1; 2; 3. Поэтому от корня дерева проведите три ветви и на их концах поставите цифры 1; 2; 3.

Для выбора второй цифры есть те же три варианта. Проводим «веточки»

Анализ объекта.

Слайд на доске:

Решение перебором

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

1, 2, 3. Будем выписывать все такие цифры в порядке возрастания. Такой способ перебора позволит нам не пропустить никакой из кодов и в то же время не повторить ни один из них.

С начало запишем в порядке возрастания все коды, начинающиеся с цифры 1: 11, 12, 13. Затем запишем в порядке возрастания коды, начинающиеся с цифры 2: 21, 22, 23.

Затем запишем в порядке возрастания коды, начинающиеся с цифры 3: 31, 32, 33

Таким образом, имеется 9 способов выбора

кода: 11, 12, 13, 21, 22, 23, 31, 32, 33.

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Анализ объекта.

Выбор оснований критериев для сравнения, сериации, классификации объектов.

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

Закрепления новых знаний

Показать практическое применение теоретических знаний

через их применение в решении практических задач

Слайд на доске с условием задачи №1

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

Слайд на доске с решением

На слайде изображено дерево возможных вариантов

первый уровень «НАПИТКИ»

два варианта: ЧАЙ, СОК.

второй уровень три варианта: ПИЦЦА, ПЛЮШКА, БУТЕРБРОД.

Итого шесть ВАРИАНТОВ завтрака:

ЧАЙ+ПИЦЦА, ЧАЙ+ПЛЮШКА, ЧАЙ+БУТЕРБРОД, СОК+ПИЦЦА, СОК+ПЛЮШКА, СОК+БУТЕРБРОД.

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Знакомство с профессиями.

Анализ объекта.

Выбор оснований критериев для сравнения, сериации, классификации объектов.

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

Слайд на доске с условием задачи №2

Из страны «Математика» в страну «Литература» ведут три дороги, а из страны «Литература» в страну «Физкультура» - четыре дороги. Сколькими способами можно попасть из страны «Математика» в

Страну «Физкультура» через страну «Литература»?

Слайд на доске с решением

Рисунок поможет нам решить эту задачу.

Переберём все «ПУТИ»

Обозначим дороги идущие из страны «МАТЕМАТИКА» так: М1, М2, М3,

а из «ЛИТЕРАТУРА» Л1, Л2, Л3,Л4.

Переберём М1+Л1, М1+Л2, М1+Л3,М1+Л4, М2+Л1, М2+Л2, М2+Л3,

М2+Л4, М3+Л1, М3+Л2, М3+Л3, М3+Л4

Натолкнуть

Детей на мысль о перемножении Количества дорог

А можно взять и перемножить количество дорог 3*4 =12

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Знакомятся с моделями и схемами для решения задач в зависимости от конкретных условий.

Слайд на доске с условием задачи №3

Шифр сейфа составляют из букв и цифр, причём на первом месте ставится буква (например А7). Сколько различных вариантов шифра можно составить, используя буквы А, В, С и цифры 3, 7, 9?

Слайд на доске с решением

2)Чтобы выбрать букву кода, у нас есть три варианта: А; B ; C . Поэтому от корня дерева проведены три ветви и на их концах поставлены буквы: А; B ; C .

3)Для выбора цифры есть те же три варианта. Проводим «веточки»

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

А3, А7, А9, В3, В7, В9, С3, С7, С9

Или Всего 3*3=9 вариантов

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Знакомятся с моделями и схемами для решения задач в зависимости от конкретных условий.

Слайд на доске с условием задачи №4

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

Слайд на доске с решением

Первый способ: обозначим цвета полосок первыми буквами названий цветов

Б – белый, К – красный, С – синий.

Решим перебором:

БСК, БКС, СБК, СКБ, КБС, КСБ

Всего шесть вариантов.

Второй способ:

Берем карандаши и рисуем флаги

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Знакомятся с моделями и схемами для решения задач в зависимости от конкретных условий.

Слайд на доске с условием задачи №5

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

Слайд на доске с решением

Второй способ решения

Для наглядности раскрасим стулья разными цветами.

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

Эту же операцию проделаем с остальными цветами, получим 6*4=24 различных вариантов.

Второй способ:

На первый стул может сесть любой член семьи, т. е. 4 варианта; на второй – 3 человека так, как один член семьи уже сидит; на третий – 2 человека так, как

двое сидят; на четвёртый только один так, как три члена семьи уже сидят.

Итак, перемножим все варианты

4*3*2*1= 24

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Знакомятся с моделями и схемами для решения задач в зависимости от конкретных условий.

Слайд на доске с условием задачи №6

Вася решил пойти на новогодний

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

Слайд на доске с решением

Обозначим: первую шапку Ш1, вторую – Ш2, третью – Ш3

1) на слайде изображён корень дерева, в виде знака *.

2) первый уровень трое брюк;

3) второй уровень два камзола;

4) третий уровень три шапки;

Всего 18 вариантов

Или просто перемножить «уровни»

3*2*3=18

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Знакомятся с моделями и схемами для решения задач в зависимости от конкретных условий.

Слайд на доске с условием задачи №7

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

Семь гномов решили обменяться фотографиями. Сколько нужно фотографий?

Слайд на доске с решением: а)

Слайд на доске с решением: б)

Эти две задачи очень похожи, но всё-таки они разные

При решении таких задач лучше использовать таблицу.

1)Нарисуем таблицу 8*8, первая строка и первый столбец это гномы.

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

3) Ячейки это кто с кем поздоровался.

4) Нижняя часть таблицы повторяет верхнюю.

Первый гном поздоровался со вторым = второй гном поздоровался с первым.

Всего 21 рукопожатие.

Задача б) отличается от а) тем, что нужно

учитывать нижнюю часть таблицы так, как

первый гном подарил фото второму, НЕРАВНО второй гном подарил фото первому.

Всего 42 фото.

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Знакомятся с моделями и схемами для решения задач в зависимости от конкретных условий.

Систематизации знаний

Систематизировать методы решений комбинаторных задач.

Слайды на доске

И следующий слайд,

Слайды решений задачи №7

Мы познакомились с тремя методами решения 1) древо вариантов; 2) перебор;

3) табличное представление данных

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Систематизация знаний по трём

методам.

Усвоения новых знаний

Дать определе-

ние комбинаторных задачач.

Слайд на доске

Попросить детей своими словами определить понятие «Комбинаторные задачи»

Отвечают на вопрос

Установление аналогий.

Умение классифициро

вать.

Определить три метода решения задач этого типа.

Следующий слайд;

Слайд решения задачи №7

Попросить детей своими словами рассказать о трёх методах решения

комбинаторных задач

Отвечают на вопрос

Умение классифициро

вать.

Выбор наиболее эффективных способов решения задач в зависимости от конкретных решений

Сделать вывод о многовариантном решении комбинаторных задач

Слайд

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

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

Отвечают на вопрос

Создавать модели и схемы для решения задач в зависимости от конкретных условий

Рефлек

сии

Провести самостоятельную работу в группах, в малых группах, индиви- дуально.

диагонали

пополам

равны

под прямым углом

да

Да

да

На парте у каждого лист (формата А4) с семью задачами (приложение№1)

Слайд с ответами

Таблица на доске (ответы команд)

Коман-

да №1

Коман-

да №2

7 а

7 б

Из класса выбираются две команды по 8 -12 человек. Даётся им задание:

1. Распределиться по задачам: на одну задачу по одному или по двое учеников.

2. На решение отводится не более 7 минут

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

1. за каждую правильно решенную

задачу команда получит 1 балл

1. проверяет класс: на доске выписываются ответы команд. Дети решавшие свою задачу говорят ответ дежурный записывает его

2. правильные ответы на слайде

Ученики, которые не задействованы в командах, решают по своему выбору и любое количество задач из семи

Выполняют самостоятельную работу в коллективе, в парах, индивидуально.

Сочетание индивидуальной самостоятельной работы и сотрудничество в коллективе

Объяснения домашнего задания

Обеспече

ние понимания детьми цели, содержания и способов выполне

ния домашнего задания.

У каждого ученика на парте лежит текст этого домашнего

задания.

Проектное домашнее задание

Придумать каждому по три

любые комбинаторные задачи.

Группа не более 5 человек

Эти задачи мы (Учитель и ученики) будем использовать в дальнейшем в конкурсах викторинах, и не только внутри класса, но и школы.

То есть создадим банк «Задач для викторин»

Продумывают условия выполнения д/з:

1)индивидуально или в группе;

2) что использовать при составлении задач, какие ресурсы.

Саморегуля

ция, развитие самосознания, ответствен

ного отношения

Приложение №1

Задача №1

В столовой на завтрак можно выбрать булочку, пирожок с капустой, пирожок с картошкой, бутерброд, а запить их можно чаем, компотом. Из скольких вариантов завтрака можно выбирать?

Задача №2

Из страны «Математика» в страну «Литература» ведут четыре дороги, а из страны «Литература» в страну «Физкультура» - пять дорог. Сколькими способами можно попасть из страны «Математика» в

страну «Физкультура» через страну «Литература»?

Задача №3

Шифр сейфа составляют из букв и цифр, причём на первом месте ставится буква (например А7). Сколько различных вариантов шифра можно составить, используя буквы А, M , F и цифры 1, 4, 6, 9?

Задача №4

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

Задача №5

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

Задача №6

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

Задача №7

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

Пять гномов решили обменяться фотографиями. Сколько нужно фотографий?

Приложение №2

Домашнее задание (Проектная деятельность)

Проектное домашнее задание

Придумать каждому по три

любые комбинаторные задачи.

При придумывании задач можно использовать: Учебник «Виленкин. Математика 5; другие книги; ресурсы интернета.

Можно объединяться в группы, но условие,

каждый ученик по три задачи остаётся.

Группа не более 5 человек

3) УМК « Дорофеев Математика 5»;

4) Ресурсы Интернета (gif1000)

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

Чем будем заниматься? В узком смысле комбинаторика – это подсчёт различных комбинаций, которые можно составить из некоторого множества дискретных объектов. Под объектами понимаются какие-либо обособленные предметы или живые существа – люди, звери, грибы, растения, насекомые и т.д. При этом комбинаторику совершенно не волнует, что множество состоит из тарелки манной каши, паяльника и болотной лягушки. Принципиально важно, что эти объекты поддаются перечислению – их три (дискретность) и существенно то, что среди них нет одинаковых.

С множеством разобрались, теперь о комбинациях. Самыми распространёнными видами комбинаций являются перестановки объектов, их выборка из множества (сочетание) и распределение (размещение). Давайте прямо сейчас посмотрим, как это происходит:

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

Не пугайтесь малопонятных терминов, тем более, некоторые из них действительно не очень удачны. Начнём с хвоста заголовка – что значит «без повторений »? Это значит, что в данном параграфе будут рассматриваться множества, которые состоят из различных объектов. Например, … нет, кашу с паяльником и лягушкой предлагать не буду, лучше что-нибудь повкуснее =) Представьте, что перед вами на столе материализовалось яблоко, груша и банан (при наличии таковых ситуацию можно смоделировать и реально). Выкладываем фрукты слева направо в следующем порядке:

яблоко / груша / банан

Вопрос первый : сколькими способами их можно переставить?

Одна комбинация уже записана выше и с остальными проблем не возникает:

яблоко / банан / груша
груша / яблоко / банан
груша / банан / яблоко
банан / яблоко / груша
банан / груша / яблоко

Итого : 6 комбинаций или 6 перестановок .

Хорошо, здесь не составило особого труда перечислить все возможные случаи, но как быть, если предметов больше? Уже с четырьмя различными фруктами количество комбинаций значительно возрастёт!

Пожалуйста, откройте справочный материал (методичку удобно распечатать) и в пункте № 2 найдите формулу количества перестановок.

Никаких мучений – 3 объекта можно переставить способами.

Вопрос второй : сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт?

Зачем выбирать? Так нагуляли же аппетит в предыдущем пункте – для того, чтобы съесть! =)

а) Один фрукт можно выбрать, очевидно, тремя способами – взять либо яблоко, либо грушу, либо банан. Формальный подсчёт проводится по формуле количества сочетаний :

Запись в данном случае следует понимать так: «сколькими способами можно выбрать 1 фрукт из трёх?»

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

яблоко и груша;
яблоко и банан;
груша и банан.

Количество комбинаций легко проверить по той же формуле:

Запись понимается аналогично: «сколькими способами можно выбрать 2 фрукта из трёх?».

в) И, наконец, три фрукта можно выбрать единственным способом:

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

г) Сколькими способами можно взять хотя бы один фрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта или все 3 фрукта:
способами можно выбрать хотя бы один фрукт.

Читатели, внимательно изучившие вводный урок по теории вероятностей , уже кое о чём догадались. Но о смысле знака «плюс» позже.

Для ответа на следующий вопрос мне требуется два добровольца… …Ну что же, раз никто не хочет, тогда буду вызывать к доске =)

Вопрос третий : сколькими способами можно раздать по одному фрукту Даше и Наташе?

Для того чтобы раздать два фрукта, сначала нужно их выбрать. Согласно пункту «бэ» предыдущего вопроса, сделать это можно способами, перепишу их заново:

яблоко и груша;
яблоко и банан;
груша и банан.

Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов:
яблоком можно угостить Дашу, а грушей – Наташу;
либо наоборот – груша достанется Даше, а яблоко – Наташе.

И такая перестановка возможна для каждой пары фруктов.

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

Способами можно выбрать 1 юношу;
способами можно выбрать 1 девушку.

Таким образом, одного юношу и одну девушку можно выбрать: способами.

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

То есть, Олег может пригласить на танец любую из 13 девушек, Евгений – тоже любую из тринадцати, и аналогичный выбор есть у остальных молодых людей. Итого: возможных пар.

Следует отметить, что в данном примере не имеет значения «история» образования пары; однако если принять во внимание инициативу, то количество комбинаций нужно удвоить, поскольку каждая из 13 девушек тоже может пригласить на танец любого юношу. Всё зависит от условия той или иной задачи!

Похожий принцип справедлив и для более сложных комбинаций, например: сколькими способами можно выбрать двух юношей и двух девушек для участия в сценке КВН?

Союз И недвусмысленно намекает, что комбинации необходимо перемножить:

Возможных групп артистов.

Иными словами, каждая пара юношей (45 уникальных пар) может выступать с любой парой девушек (78 уникальных пар). А если рассмотреть распределение ролей между участниками, то комбинаций будет ещё больше. …Очень хочется, но всё-таки воздержусь от продолжения, чтобы не привить вам отвращение к студенческой жизни =).

Правило умножения комбинаций распространяется и на бОльшее количество множителей:

Задача 8

Сколько существует трёхзначных чисел, которые делятся на 5?

Решение : для наглядности обозначим данное число тремя звёздочками: ***

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

А вот в разряд десятков («посерединке») можно выбрать любую из 10 цифр: .

По условию, число должно делиться на 5. Число делится на 5, если оно заканчивается на 5 либо на 0. Таким образом, в младшем разряде нас устраивают 2 цифры.

Итого, существует : трёхзначных чисел, которые делятся на 5.

При этом произведение расшифровывается так: «9 способами можно выбрать цифру в разряд сотен и 10 способами выбрать цифру в разряд десятков и 2 способами в разряд единиц »

Или ещё проще: «каждая из 9 цифр в разряде сотен комбинируется с каждой из 10 цифр разряда десятков и с каждой из двух цифр в разряде единиц ».

Ответ : 180

А теперь…

Да, чуть не забыл об обещанном комментарии к задаче № 5, в которой Боре, Диме и Володе можно сдать по одной карте способами. Умножение здесь имеет тот же смысл: способами можно извлечь 3 карты из колоды И в каждой выборке переставить их способами.

А теперь задача для самостоятельного решения… сейчас придумаю что-нибудь поинтереснее, …пусть будет про ту же русскую версию блэкджека:

Задача 9

Сколько существует выигрышных комбинаций из 2 карт при игре в «очко»?

Для тех, кто не знает: выигрывает комбинация 10 + ТУЗ (11 очков) = 21 очко и, давайте будем считать выигрышной комбинацию из двух тузов.

(порядок карт в любой паре не имеет значения)

Краткое решение и ответ в конце урока.

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

Пришло время закрепить пройденный материал парой солидных задач:

Задача 10

У Васи дома живут 4 кота.

а) сколькими способами можно рассадить котов по углам комнаты?
б) сколькими способами можно отпустить гулять котов?
в) сколькими способами Вася может взять на руки двух котов (одного на левую, другого – на правую)?

Решаем : во-первых, вновь следует обратить внимание на то, что в задаче речь идёт о разных объектах (даже если коты – однояйцовые близнецы). Это очень важное условие!

а) Молчание котов. Данной экзекуции подвергаются сразу все коты
+ важно их расположение, поэтому здесь имеют место перестановки:
способами можно рассадить котов по углам комнаты.

Повторюсь, что при перестановках имеет значение лишь количество различных объектов и их взаимное расположение. В зависимости от настроения Вася может рассаживать животных полукругом на диване, в ряд на подоконнике и т.д. – перестановок во всех случаях будет 24. Желающие могут для удобства представить, что коты разноцветные (например, белый, чёрный, рыжий и полосатый) и перечислить все возможные комбинации.

б) Сколькими способами можно отпустить гулять котов?

Предполагается, что коты ходят гулять только через дверь, при этом вопрос подразумевает безразличие по поводу количества животных – на прогулку могут выйти 1, 2, 3 или все 4 кота.

Считаем все возможные комбинации:

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

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

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

в) Сколькими способами Вася может взять на руки двух котов?

Ситуация предполагает не только выбор 2 животных, но и их размещение по рукам:
способами можно взять на руки 2 котов.

Второй вариант решения: способами можно выбрать двух котов и способами посадить каждую пару на руки:

Ответ : а) 24, б) 15, в) 12

Ну и для очистки совести что-нибудь поконкретнее на умножение комбинаций…. Пусть у Васи дополнительно живёт 5 кошек =) Сколькими способами можно отпустить гулять 2 котов и 1 кошку?

То есть, с каждой парой котов можно выпустить каждую кошку.

Ещё один баян для самостоятельного решения:

Задача 11

В лифт 12-этажного дома сели 3 пассажира. Каждый независимо от других с одинаковой вероятностью может выйти на любом (начиная со 2-го) этаже. Сколькими способами:

1) пассажиры могут выйти на одном и том же этаже (порядок выхода не имеет значения) ;
2) два человека могут выйти на одном этаже, а третий – на другом;
3) люди могут выйти на разных этажах;
4) пассажиры могут выйти из лифта?

И тут часто переспрашивают, уточняю: если 2 или 3 человека выходят на одном этаже, то очерёдность выхода не имеет значения. ДУМАЙТЕ, используйте формулы и правила сложения/умножения комбинаций. В случае затруднений пассажирам полезно дать имена и порассуждать, в каких комбинациях они могут выйти из лифта. Не нужно огорчаться, если что-то не получится, так, например, пункт № 2 достаточно коварен, впрочем, один из читателей отыскал простое решение, и я в очередной раз выражаю благодарность за ваши письма!

Полное решение с подробными комментариями в конце урока.

Заключительный параграф посвящён комбинациям, которые тоже встречаются достаточно часто – по моей субъективной оценке, примерно в 20-30% комбинаторных задач:

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

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

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

В перестановках с повторениями, как и в «обычных» перестановках, участвует сразу всё множество объектов , но есть одно но: в данном множестве один или бОльшее количество элементов (объектов) повторяются. Встречайте очередной стандарт:

Задача 12

Сколько различных буквосочетаний можно получить перестановкой карточек со следующими буквами: К, О, Л, О, К, О, Л, Ь, Ч, И, К?

Решение : в том случае, если бы все буквы были различны, то следовало бы применить тривиальную формулу , однако совершенно понятно, что для предложенного набора карточек некоторые манипуляции будут срабатывать «вхолостую», так, например, если поменять местами любые две карточки с буквами «К» в любом слове, то получится то же самое слово. Причём, физически карточки могут сильно отличаться: одна быть круглой с напечатанной буквой «К», другая – квадратной с нарисованной буквой «К». Но по смыслу задачи даже такие карточки считаются одинаковыми , поскольку в условии спрашивается о буквосочетаниях.

Всё предельно просто – всего: 11 карточек, среди которых буква:

К – повторяется 3 раза;
О – повторяется 3 раза;
Л – повторяется 2 раза;
Ь – повторяется 1 раз;
Ч – повторяется 1 раз;
И – повторяется 1 раз.

Проверка: 3 + 3 + 2 + 1 + 1 + 1 = 11, что и требовалось проверить.

По формуле количества перестановок с повторениями :
различных буквосочетаний можно получить. Больше полумиллиона!

Для быстрого расчёта большого факториального значения удобно использовать стандартную функцию Экселя: забиваем в любую ячейку =ФАКТР(11) и жмём Enter .

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

Но предварительные комментарии о повторяющихся буквах обязательны!

Ответ : 554400

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

Задача 13

Алексей занимается спортом, причём 4 дня в неделю – лёгкой атлетикой, 2 дня – силовыми упражнениями и 1 день отдыхает. Сколькими способами он может составить себе расписание занятий на неделю?

Формула здесь не годится, поскольку учитывает совпадающие перестановки (например, когда меняются местами силовые упражнения в среду с силовыми упражнениями в четверг). И опять – по факту те же 2 силовые тренировки могут сильно отличаться друг от друга, но по контексту задачи (с точки зрения расписания) они считаются одинаковыми элементами.

Двухстрочное решение и ответ в конце урока.

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

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

Сегодня все хорошо потрудились, поэтому настало время подкрепиться:

Задача 14

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

Решение : сразу обратите внимание на типичный критерий сочетаний с повторениями – по условию на выбор предложено не множество объектов как таковое, а различные виды объектов; при этом предполагается, что в продаже есть не менее пяти хот-догов, 5 ватрушек и 5 пончиков. Пирожки в каждой группе, разумеется, отличаются – ибо абсолютно идентичные пончики можно смоделировать разве что на компьютере =) Однако физические характеристики пирожков по смыслу задачи не существенны, и хот-доги / ватрушки / пончики в своих группах считаются одинаковыми.

Что может быть в выборке? Прежде всего, следует отметить, что в выборке обязательно будут одинаковые пирожки (т.к. выбираем 5 штук, а на выбор предложено 3 вида). Варианты тут на любой вкус: 5 хот-догов, 5 ватрушек, 5 пончиков, 3 хот-дога + 2 ватрушки, 1 хот-дог + 2 + ватрушки + 2 пончика и т.д.

Как и при «обычных» сочетаниях, порядок выбора и размещение пирожков в выборке не имеет значения – просто выбрали 5 штук и всё.

Используем формулу количества сочетаний с повторениями:
способом можно приобрести 5 пирожков.

Приятного аппетита!

Ответ : 21

Какой вывод можно сделать из многих комбинаторных задач?

Порой, самое трудное – это разобраться в условии.

Аналогичный пример для самостоятельного решения:

Задача 15

В кошельке находится достаточно большое количество 1-, 2-, 5- и 10-рублёвых монет. Сколькими способами можно извлечь три монеты из кошелька?

В целях самоконтроля ответьте на пару простых вопросов:

1) Могут ли в выборке все монеты быть разными?
2) Назовите самую «дешевую» и самую «дорогую» комбинацию монет.

Решение и ответы в конце урока.

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

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

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

Когда так бывает? Типовым примером является кодовый замок с несколькими дисками, но по причине развития технологий актуальнее рассмотреть его цифрового потомка:

Задача 16

Сколько существует четырёхзначных пин-кодов?

Решение : на самом деле для разруливания задачи достаточно знаний правил комбинаторики: способами можно выбрать первую цифру пин-кода и способами – вторую цифру пин-кода и столькими же способами – третью и столькими же – четвёртую. Таким образом, по правилу умножения комбинаций, четырёхзначный пин-код можно составить: способами.

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

Ответ : 10000

Что тут приходит на ум… …если банкомат «съедает» карточку после третьей неудачной попытки ввода пин-кода, то шансы подобрать его наугад весьма призрачны.

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

Задача 17

Согласно государственному стандарту, автомобильный номерной знак состоит из 3 цифр и 3 букв. При этом недопустим номер с тремя нулями, а буквы выбираются из набора А, В, Е, К, М, Н, О, Р, С, Т, У, Х (используются только те буквы кириллицы, написание которых совпадает с латинскими буквами) .

Сколько различных номерных знаков можно составить для региона?

Не так их, кстати, и много. В крупных регионах такого количества не хватает, и поэтому для них существуют по несколько кодов к надписи RUS.

Решение и ответ в конце урока. Не забываем использовать правила комбинаторики;-) …Хотел похвастаться эксклюзивом, да оказалось не эксклюзивом =) Заглянул в Википедию – там есть расчёты, правда, без комментариев. Хотя в учебных целях, наверное, мало кто прорешивал.

Наше увлекательное занятие подошло к концу, и напоследок я хочу сказать, что вы не зря потратили время – по той причине, что формулы комбинаторики находят ещё одно насущное практическое применение: они встречаются в различных задачах по теории вероятностей ,
и в задачах на классическое определение вероятности – особенно часто =)

Всем спасибо за активное участие и до скорых встреч!

Решения и ответы :

Задача 2: Решение : найдём количество всех возможных перестановок 4 карточек:

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

Примечание : т.к. карточек немного, то здесь несложно перечислить все такие варианты:
0579
0597
0759
0795
0957
0975

Таким образом, из предложенного набора можно составить:
24 – 6 = 18 четырёхзначных чисел
Ответ : 18

Задача 4: Решение : способами можно выбрать 3 карты из 36. и
2) Самый «дешёвый» набор содержит 3 рублёвые монеты, а самый «дорогой» – 3 десятирублёвые.

Задача 17: Решение : способами можно составить цифровую комбинацию автомобильного номера, при этом одну из них (000) следует исключить: .
способами можно составить буквенную комбинацию автомобильного номера.
По правилу умножения комбинаций, всего можно составить:
автомобильных номера
(каждая цифровая комбинация сочетается с каждой буквенной комбинацией).
Ответ : 1726272

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

1. Сколько анаграмм имеет слово КЛАСС?

Трудность в том, что в этом слове две одинаковые буквы С. Будем временно считать их разными и обозначим С 1 и С 2 . Тогда число анаграмм окажется равным 5! = 120. Но те слова, которые отличаются друг из друга лишь перестановкой букв С 1 и С 2 , на самом-то деле являются одной и той же анаграммой! Поэтому 120 анаграмм разбиваются на пары одинаковых, т.е. искомое число анаграмм равно 120/2 = 60.

2. Сколько анаграмм имеет слово ШАРАДА?

Считая три буквы А различными буквами А 1 , А 2 , А 3 , получим 6! анаграмм. Но слова, которые получаются друг из друга только перестановкой букв А 1 , А 2 , А 3 , на самом деле являются одной и той же анаграммой. Поскольку имеется 3! перестановок букв А 1 , А 2 , А 3 , полученные изначально 6! анаграмм разбиваются на группы по 3! одинаковых, и число различных анаграмм оказывается равным 6!/3! = 120.

3. Сколько существует четырехзначных чисел, в записи которых есть хотя бы одна четная цифра?

Найдем количество «ненужных» четырехзначных чисел, в записи которых присутствуют только нечетные цифры. Таких чисел 5 4 = 625. Но всего четырехзначных чисел 9000, поэтому искомое количество «нужных» чисел равно 9000 – 625 = 8375.

1. Найти число анаграмм у слов ВЕРЕСК, БАЛАГАН, ГОРОДОВОЙ.
2. Найти число анаграмм у слов БАОБАБ, БАЛЛАДА, ПЕРЕПОЛОХ, АНАГРАММА, МАТЕМАТИКА, КОМБИНАТОРИКА, ОБОРОНОСПОСОБНОСТЬ.
3. Сколькими способами можно поселить 7 приезжих в три гостиничных номера: одноместный, двухместный и четырехместный?
4. В холодильнике лежат два яблока, три груши и четыре апельсина. Каждый день в течение девяти дней подряд Пете дают один какой-то фрукт. Сколькими способами это может быть сделано?
5. Из семи лучших лыжников школы нужно отобрать команду из трех человек для участия в городских соревнованиях. Сколькими способами это можно сделать?
6. Перед экзаменом профессор пообещал поставить двойки половине экзаменуемых. На экзамен пришло 20 студентов. Сколькими способами он может выполнить обещание?
7. Сколько слов можно составить из пяти букв А и не более чем из трех букв Б?
8. В продаже есть шоколадное, клубничное и молочное мороженое. Сколькими способами можно купить три мороженых?
9. При приготовлении пиццы к сыру добавляются разные компоненты, обеспечивающие тот или иной вкус. В распоряжении Билла имеются лук, грибы, помидоры, перец и анчоусы, причем все это, по его мнению, можно добавлять к сыру. Сколько видов пиццы может приготовить Билл?
10. Свидетель криминальной разборки запомнил, что преступники скрылись на «мерседесе», номер которого содержал буквы Т, З, У и цифры 3 и 7 (номером является строка, в которой сначала идут три буквы, а затем - три цифры). Сколько существует таких номеров?
11. Сколько диагоналей в выпуклом n -угольнике?
12. Сколько всего существует n -значных чисел?
13. Сколько существует десятизначных чисел, в записи которых есть хотя бы две одинаковые цифры?
14. Кубик бросают трижды. Среди всевозможных последовательностей результатов есть такие, в которых хотя бы один раз выпала шестерка. Сколько их?
15. Сколько пятизначных чисел имеют в своей записи цифру 1?
16. Сколькими способами можно расставить на шахматной доске белого и черного короля так, чтобы они не били друг друга?
17. Сколько делителей у числа 10800?

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

Определение 1: Порядок во множестве изэлементов – это нумерация его элементов натуральными числами, т.е. отображение множества
на множество
.

Определение 2: Множество с заданным на нем порядком называется упорядоченным множеством.

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

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

и
.

Три буквы ,иможно расположить в виде последовательности шестью способами:

,
,
,
,
,
.

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

Упорядоченные последовательности элементов некоторого множества можно рассматривать как распределения или расстановки этих элементов в последовательности.

Определение 3: Пусть дано конечное множество
изэлементов. Всякий набор изэлементов данного множества (при этом элементы в наборе могут и повторяться) будем называть-расстановками .

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

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

Определение 4: Пусть
- конечное множество изэлементов.Перестановками из различных элементов множества
называются все расположенияэлементов в определенном порядке. Обозначается:(от французского словаpermutation - перестановка).

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

Определение 5: Различные упорядоченные множества, которые отличаются лишь порядком элементов, называются перестановками этого множества.

Последнее определение сформулировано с позиции теории множеств.

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

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

Теорема 1: Число перестановок из различных элементов вычисляется по формуле:

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

Теорема доказана.

Пример 1: Сколькими способами трое друзей могут занять в кинотеатре места с номерами 1, 2 и 3.

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

Перестановки букв некоторого слова называют анаграммами . Открытые еще в ІІІ веке до нашей эры греческим грамматиком Ликофроном анаграммы до сих пор привлекают внимание языковедов, поэтов и любителей словесности. Мастера словесных игр помимо эрудиции и большого запаса слов знают много секретов, связанных с комбинаторными навыками, один из которых – анаграммы. Часто требуется среди всех перестановок выбрать те, которые обладают определенным свойством. Например, среди анаграмм слова «крот» , которых всего
, только одна, не считая самого слова«крот» , имеет смысл в русском языке – «корт».

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

Теорема 2: Число круговых перестановок из различных элементов равно

Пример 2: Сколькими способами 7 детей могут стать в хоровод?

Решение. Число линейных перестановок 7 детей будет равно
. Если хоровод уже сформирован, тогда для него существует 7 круговых перестановок, переходящих друг в друга при повороте. Эти перестановки не должны быть засчитаны, поэтому круговых перестановок из 7 элементов будет.

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

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

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

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

Определение 8: Конечные упорядоченные множества называются размещениями.

Теорема 3: Количество всех размещений из элементов поэлементов без повторений вычисляется по формуле:

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

Выбор элементов осуществляется поэтапно. Первый элемент расстановки можно выбрать различными способами. Тогда из оставшихся элементов множества
второй элемент расстановки выбирается
способом. Для выбора третьего элемента возможно
способа и т.д. Тогда для выбора- го элемента имеем
способ. Следовательно, согласно правилу умножения, количество таких расстановок будет равно:

По определению, такие расстановки являются размещениями. Что и требовалось доказать.

Пример 3: Собрание из 25 человек выбирает президиум из 3 человек: 1) председатель, 2) заместитель, 3) секретарь. Сколько возможно вариантов выбора президиума?

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

Замечание: Число размещений без повторений можно также находить по формуле:

. (3)

Если в знаменателе дроби из формулы (3)
, то принято считать
.

Замечание: Формула (3) отличается компактностью, но при решении задач удобнее использовать формулу (2). Дробь, стоящая в правой части формулы (3), может быть сокращена до целого числа. Это число равно числу из правой части формулы (2).

Пример 4: Сколько можно составить двухбуквенных слов (буквы не повторяются) из 33 букв русского алфавита?

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

Тогда количество различных комбинаций из 2 букв, выбранных из 33 букв алфавита, будет равно:

.

В данном случае важен порядок букв. Если поменять 2 буквы в слове, то получим новое слово.

Замечание: Перестановка без повторений – это частный случай размещений без повторений при
. Можно сказать, что перестановка изэлементов – это размещение изэлементов поэлементов:

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

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

Определение 9: Сочетания без повторений из элементов некоторого множества поэлементов (
) – это расстановки, отличающиеся друг от другасоставом , но не порядком элементов. Обозначают: (от французского словаcombinaison – сочетание).

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

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

Определение 10: Конечные неупорядоченные множества называются сочетаниями.

Таким образом, сочетания – это такая выборка элементов, при которой их порядок совершенно не важен.

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

Теорема 4: Число сочетаний находится по следующей формуле:

. (4)

Доказательство. Если из произвольного -элементного множества выбраныэлементов, то их можно пронумеровать номерами
числом способов, равным. Оставшиеся
элементов можно занумеровать номерами
,
, …,всего
способами. Кроме того, сам отборэлементов изэлементов можно осуществитьспособами. Таким образом, мы получили
вариантов нумерации полного множества из элементов, которых всего. Поэтому имеем
, откуда получаем:

.

Теорема доказана.

Замечание: Дробь, стоящая в правой части (4), может быть сокращена до целого числа.

Из формулы числа сочетаний следует:

,
,
.

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

Пример 5: Сколькими способами можно выбрать 3 различные краски из имеющихся пяти.

Решение. Порядок выбора красок не важен. Важно только какие краски выбраны. Поэтому количество вариантов равно:
.

Пример 6: Сколькими способами можно пошить трехцветные полосатые флаги, если имеется материал пяти различных цветов.

Решение. Порядок выбора полос важен, поэтому количество таких флагов равно:
.