Методы решения комбинаторных задач. Основные формулы комбинаторики Основные формулы комбинаторики размещение сочетание перестановка
В данной статье речь пойдет об особом разделе математики под названием комбинаторика. Формулы, правила, примеры решения задач - все это вы сможете найти здесь, прочитав статью до самого конца.
Итак, что же это за раздел? Комбинаторика занимается вопросом подсчета каких-либо объектов. Но в данном случае объектами выступают не сливы, груши или яблоки, а нечто иное. Комбинаторика помогает нам находить вероятность какого-либо события. Например, при игре в карты - какова вероятность того, что у противника есть козырная карта? Или такой пример - какова вероятность того, что из мешка с двадцатью шариками вы достанете именно белый? Именно для подобного рода задач нам и нужно знать хотя бы основы данного раздела математики.
Комбинаторные конфигурации
Рассматривая вопрос основных понятий и формул комбинаторики, мы не можем не уделить внимание комбинаторным конфигурациям. Они используются не только для формулировки, но и для решения различных Примерами таких моделей служат:
- размещение;
- перестановка;
- сочетание;
- композиция числа;
- разбиение числа.
О первых трех мы поговорим более подробно далее, а вот композиции и разбиению мы уделим внимание в данном разделе. Когда говорят о композиции некого числа (допустим, а), то подразумевают представление числа а в виде упорядоченной суммы неких положительных чисел. А разбиение - это неупорядоченная сумма.
Разделы
Прежде чем мы перейдем непосредственно к формулам комбинаторики и рассмотрению задач, стоит обратить внимание на то, что комбинаторика, как и другие разделы математики, имеет свои подразделы. К ним относятся:
- перечислительная;
- структурная;
- экстремальная;
- теория Рамсея;
- вероятностная;
- топологическая;
- инфинитарная.
В первом случае речь идет об исчисляющей комбинаторике, задачи рассматривают перечисление или подсчет разных конфигураций, которые образованы элементами множеств. На данные множества, как правило, накладываются какие-либо ограничения (различимость, неразличимость, возможность повтора и так далее). А количество этих конфигураций подсчитывается при помощи правила сложения или умножения, о которых мы поговорим немного позже. К структурной комбинаторике относятся теории графов и матроидов. Пример задачи экстремальной комбинаторики - какова наибольшая размерность графа, который удовлетворяет следующим свойствам… В четвертом пункте мы упомянули теорию Рамсея, которая изучает в случайных конфигурациях наличие регулярных структур. Вероятностная комбинаторика способна нам ответить на вопрос - какова вероятность того, что у заданного множества присутствует определенное свойство. Как нетрудно догадаться, топологическая комбинаторика применяет методы в топологии. И, наконец, седьмой пункт - инфинитарная комбинаторика изучает применение методов комбинаторики к бесконечным множествам.
Правило сложения
Среди формул комбинаторики можно найти и довольно простые, с которыми мы достаточно давно знакомы. Примером является правило суммы. Предположим, что нам даны два действия (С и Е), если они взаимоисключаемы, действие С выполнимо несколькими способами (например а), а действие Е выполнимо b-способами, то выполнить любое из них (С или Е) можно а+b способами.
В теории это понять достаточно трудно, постараемся донести всю суть на простом примере. Возьмем среднюю численность учеников одного класса - допустим, это двадцать пять. Среди них пятнадцать девочек и десять мальчиков. Ежедневно в классе назначается один дежурный. Сколько есть способов назначить дежурного по классу сегодня? Решение задачи достаточно простое, мы прибегнем к правилу сложения. В тексте задачи не сказано, что дежурными могут быть только мальчики или только девочки. Следовательно, им может оказаться любая из пятнадцати девочек или любой из десяти мальчиков. Применяя правило суммы, мы получаем достаточно простой пример, с которым без труда справится школьник начальных классов: 15 + 10. Подсчитав, получаем ответ: двадцать пять. То есть существует всего двадцать пять способов назначить на сегодня дежурного класса.
Правило умножения
К основным формулам комбинаторики относится и правило умножения. Начнем с теории. Допустим, нам необходимо выполнить несколько действий (а): первое действие выполняется с1 способами, второе - с2 способами, третье - с3 способами и так далее до последнего а-действия, выполняемого са способами. Тогда все эти действия (которых всего у нас а) могут быть выполнены N способами. Как высчитать неизвестную N? В этом нам поможет формула: N = с1 * с2 * с3 *…* са.
Опять же, в теории ничего не понятно, переходим к рассмотрению простого примера на применение правила умножения. Возьмем все тот же класс из двадцати пяти человек, в котором учится пятнадцать девочек и десять мальчиков. Только на этот раз нам необходимо выбрать двух дежурных. Ими могут быть как только мальчики или девочки, так и мальчик с девочкой. Переходим к элементарному решению задачи. Выбираем первого дежурного, как мы решили в прошлом пункте, у нас получается двадцать пять возможных вариантов. Вторым дежурным может быть любой из оставшихся человек. У нас было двадцать пять учеников, одного мы выбрали, значит вторым дежурным может быть любой из оставшихся двадцати четырех человек. Наконец, применяем правило умножения и получаем, что двоих дежурных можно избрать шестью сотнями способов. Мы данное число получили умножением двадцати пяти и двадцати четырех.
Перестановка
Сейчас мы рассмотрим еще одну формулу комбинаторики. В данном разделе статьи мы поговорим о перестановках. Рассмотреть проблему предлагаем сразу же на примере. Возьмем бильярдные шары у нас их n-ое количество. Нам нужно подсчитать: сколько есть вариантов расставить их в ряд, то есть составить упорядоченный набор.
Начнем, если у нас нет шаров, то и вариантов расстановки у нас так же ноль. А если у нас шар один, то и расстановка тоже одна (математически это можно записать следующим образом: Р1 = 1). Два шара можно расставить двумя разными способами: 1,2 и 2,1. Следовательно, Р2 = 2. Три шара можно расставить уже шестью способами (Р3=6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. А если таких шаров не три, а десять или пятнадцать? Перечислять все возможные варианты очень долго, тогда нам на помощь приходит комбинаторика. Формула перестановки поможет нам найти ответ на интересующий нас вопрос. Pn = n *P (n-1). Если попытаться упростить формулу, то получаем: Pn = n* (n - 1) *…* 2 * 1. А это и есть произведение первых натуральных чисел. Такое число называется факториалом, а обозначается как n!
Рассмотрим задачу. Вожатый каждое утро выстраивает свой отряд в шеренгу (двадцать человек). В отряде есть три лучших друга - Костя, Саша и Леша. Какова вероятность того, что они будут стоять рядом? Чтобы найти ответ на вопрос, нужно вероятность «хорошего» исхода поделить на общее количество исходов. Общее число перестановок составляет 20! = 2,5 квинтиллиона. Как посчитать количество «хороших» исходов? Предположим, что Костя, Саши и Леша - это один сверхчеловек. Тогда мы имеем всего восемнадцать субъектов. Число перестановок в данном случае равняется 18 = 6,5 квадриллионов. При всем этом, Костя, Саша и Леша могут произвольно перемещаться между собой в своей неделимой тройке, а это еще 3! = 6 вариантов. Значит всего «хороших» расстановок у нас 18! * 3! Нам остается только найти искомую вероятность: (18! * 3!) / 20! Что равняется примерно 0,016. Если перевести в проценты, то это получается всего 1,6%.
Размещение
Сейчас мы рассмотрим еще одну очень важную и необходимую формулу комбинаторики. Размещение - это наш следующий вопрос, который предлагаем вам рассмотреть в данном разделе статьи. Мы идем на усложнение. Предположим, что мы хотим рассмотреть возможные перестановки, только не из всего множества (n), а из меньшего (m). То есть мы рассматриваем перестановки из n предметов по m.
Основные формулы комбинаторики стоит не просто заучивать, а понимать их. Даже несмотря на то, что они усложняются, так как у нас не один параметр, а два. Предположим, что m = 1, то и А = 1, m = 2, то А = n * (n - 1). Если далее упрощать формулу и перейти на запись при помощи факториалов, то получится вполне лаконичная формула: А = n! / (n - m)!
Сочетание
Мы рассмотрели практически все основные формулы комбинаторики с примерами. Теперь перейдем к заключительному этапу рассмотрения базового курса комбинаторики - знакомство с сочетанием. Сейчас мы будем выбирать m предметов из имеющихся у нас n, при этом всем мы будем выбирать всеми возможными способами. Чем же тогда это отличается от размещения? Мы не будем учитывать порядок. Этот неупорядоченный набор и будет являться сочетанием.
Сразу введем обозначение: С. Берем размещения m шариков из n. Мы перестаем обращать внимание на порядок и получаем повторяющиеся сочетания. Чтобы получить число сочетаний нам надо поделить число размещений на m! (m факториал). То есть С = А / m! Таким образом, способов выбрать из n шаров немножко, равняется примерно столько, сколько выбрать почти все. Этому есть логическое выражение: выбрать немножко все равно, что выкинуть почти все. Еще в данном пункте важно упомянуть и то, что максимальное число сочетаний можно достигнуть при попытке выбрать половину предметов.
Как выбрать формулу для решения задачи?
Мы подробно рассмотрели основные формулы комбинаторики: размещение, перестановка и сочетание. Теперь наша задача - облегчить выбор необходимой формулы для решения задачи по комбинаторике. Можно воспользоваться следующей довольно простой схемой:
- Задайте себе вопрос: порядок размещения элементов учитывается в тексте задачи?
- Если ответ нет, то воспользуйтесь формулой сочетания (С = n! / (m! * (n - m)!)).
- Если ответ нет, то необходимо ответить на еще один вопрос: все ли элементы входят в комбинацию?
- Если ответ да, то воспользуйтесь формулой перестановки (Р = n!).
- Если ответ нет, то воспользуйтесь формулой размещения (А = n! / (n - m)!).
Пример
Мы рассмотрели элементы комбинаторики, формулы и некоторые другие вопросы. Теперь перейдем к рассмотрению реальной задачи. Представьте, что перед вами лежат киви, апельсин и банан.
Вопрос первый: сколькими способами их можно переставить? Для этого воспользуемся формулой перестановок: Р = 3! = 6 способов.
Вопрос второй: сколькими способами можно выбрать один фрукт? Это очевидно, у нас всего три варианта - выбрать киви, апельсин или банан, но применим формулу сочетаний: С = 3! / (2! * 1!) = 3.
Вопрос третий: сколькими способами можно выбрать два фрукта? Какие есть у нас вообще варианты? Киви и апельсин; киви и банан; апельсин и банан. То есть три варианта, но это легко проверить при помощи формулы сочетания: С = 3! / (1! * 2!) = 3
Вопрос четвертый: сколькими способами можно выбрать три фрукта? Как видно, выбрать три фрукта можно одним-единственным способом: взять киви, апельсин и банан. С = 3! / (0! * 3!) = 1.
Вопрос пятый: сколькими способами можно выбрать хотя бы один фрукт? Это условие подразумевает, что мы можем взять один, два или все три фрукта. Следовательно, мы складываем С1 + С2 + С3 =3 + 3 + 1 = 7. То есть у нас есть семь способов взять со стола хотя бы один фрукт.
Комбинаторика - это раздел математики, изучающий задачи о расположении или выборе элементов из множеств.
Группы, составленные из каких - либо предметов (любой, но одинаковой природы: буквы, числа, геометрические фигуры, детали и т. д.) называются соединениями (множествами). Сами предметы, их которых составляются соединения, называются элементами .
Различают три основных типа соединений: размещения, перестановки и сочетания.
Размещениями из различных (соединения) отличаются друг от друга либо хотя бы одним элементом, либо порядком их расположения. Число размещений обозначается и вычисляется по формуле:
Такие размещения называются размещениями без повторений .
ПРИМЕР . В группе 25 студентов. Выбирают старосту, физорга и профорга. Каково число всех возможных вариантов выбора «треугольника» группы?
Решение . Получаемые комбинации (т.е. соединения) из 25 - и элементов по 3 в каждом являются размещениями, так как в них важен не только состав элементов «треугольника», но и расположение внутри него. Следовательно
Размещение с повторениями из элементов по элементов в каждом может содержать любой элемент сколько угодно раз от 1 до включительно, либо не содержать его вовсе. Другими словами, каждое размещение с повторениями из элементов по может состоять не только из каких угодно, но и как угодно повторяющихся элементов. Число размещений с повторениями вычисляется по формуле
ПРИМЕР 1 . Известно, что 4 студента сдали экзамен. Сколько возможно различных исходов экзамена (распределений оценок)?
Решение . Число элементов =3 («3», «4», «5»); . Последовательность, т. е. порядок элементов, существенна, повторения неизбежны. Следовательно .
ПРИМЕР 2 . Сколькими способами 10 пассажиров могут распределиться по 13 вагонам, если для каждого существенным является только № вагона, а не занимаемое место в нем?
Решение . Пусть - номер вагона, выбранного первым пассажиром, - номер вагона, выбранного вторым пассажиром, . . . , - номер вагона, выбранного десятым пассажиром. Соединение (комбинация) полностью характеризует распределение пассажиров по вагонам. Здесь каждое из чисел может принимать любое целое значение от 1 до 13. Значит, различных распределений по вагонам будет столько, сколько подобных соединений (длиной 10) можно составить из элементов множества . Следовательно .
Перестановками из различных элементов называются такие соединения, из которых каждое содержит все элементов и которые отличаются друг от друга лишь порядком расположения элементов. Число таких перестановок из различных элементов обозначается и вычисляется по формуле:
Так как число перестановок из элементов - это то же самое, что и число размещений из элементов по в каждом, то можем записать:
ПРИМЕР . Для проведения испытаний выбрано 5 различных моделей автомобилей. Сколькими способами они могут быть распределены между пятью испытателями?
Решение . Число способов, которыми можно распределить 5 автомобилей, равно числу комбинаций из 5 элементов по пять. Причем, сами комбинации отличаются друг от друга только порядком элементов, т.е. применимы перестановки. Следовательно .
Если же среди n элементов имеются одинаковые, то такие перестановки называются перестановками с повторениями . Пусть имеется элементов, среди которых одинаковых , тогда число перестановок с повторениями определяется по формуле
Если из элементов имеется две различные группы, состоящие соответственно из одинаковых элементов:
ПРИМЕР . Каким числом способов можно распределить 9 цитрусовых между 9 студентами, если имеются 4 мандарина, 3 апельсина и 2 лимона?
Решение . Пусть - мандарины, - апельсины и - лимоны. Тогда
Следовательно .
Сочетаниями из различных элементов по () в каждом называются такие соединения, из которых каждое содержит элементов, взятых из числа данных элементов, и которые отличаются друг от друга, по крайней мере, одним элементом . Число сочетаний из различных элементов по в каждом обозначают символом и вычисляют по формуле:
Уверены, вы отлично понимаете, что это определение является определением числа сочетаний без повторений.
Число сочетаний обладает следующими свойствами :
Этим свойством удобно пользоваться в случаях, когда . Например: .
3. (см. первое свойство).
ПРИМЕР . На строительство общежития из 25 студентов требуется выбрать 3 человек. Каково число всех возможных вариантов выбора этой тройки?
Решение . Число возможных вариантов равно числу комбинаций (соединений) из 25 элементов по 3 в каждом. Причем комбинации отличаются друг от друга только составляющими их элементами, а порядок их расположения не имеет значения. Следовательно .
Сочетание с повторениями из элементов по в каждом может содержать любой элемент сколько угодно раз от 1 до включительно, либо не содержать его вовсе. Другими словами, каждое сочетание с повторениями из данных элементов по элементов в каждом может состоять не только из различных элементов, но из каких угодно и как угодно повторяющихся элементов.
Два сочетания по элементов не считаются различными сочетаниями, если они отличаются друг от друга только порядком расположения элементов.
Число сочетаний с повторениями вычисляется по формуле:
ПРИМЕР . Каким числом способов можно составить расписание занятий из 3-х пар на один день, если изучается 10 предметов, которые могут повторяться в расписании. Расписания считаются различными, если отличаются друг от друга, хотя бы одним предметом (т.е. порядок предметов в расписании роли не играет)?
Решение . .
Замечания.
1. Сформулируем правило произведения для соединений множеств: пусть элемент может быть выбран способами. При каждом выбранном , элемент
Рассмотрим задачу подсчета числа выборок из данного множества в общем виде. Пусть имеется некоторое множество N , состоящее из n элементов. Любое подмножество, состоящее из m элементов можно рассматривать без учета их порядка, так и с его учетом, т.е. при изменении порядка переходим к другой m – выборке.
Сформулируем следующие определения:
Размещения без повторения
Размещением без повторения из n элементов по m N , содержащее m различных элементов .
Из определения следует, что два размещения отличаются друг от друга, как элементами, так и их порядком, даже если элементы одинаковы.
Теорема 3 . Число размещений без повторения равно произведению m сомножителей, наибольшим из которых является число n . Записывают:
Перестановки без повторений
Перестановками из n элементов называются различные упорядочения множества N .
Из этого определения следует, что две перестановки отличаются только порядком элементов и их можно рассматривать как частный случай размещений.
Теорема 4 . Число различных перестановок без повторений вычисляется по формуле
Сочетания без повторений
Сочетанием без повторения из n элементов по m называется любое неупорядоченное подмножество множества N , содержащее m различных элементов.
Из определения следует, что два сочетания различаются только элементами, порядок не важен.
Теорема 5 . Число сочетаний без повторений вычисляют по одной из следующих формул:
Пример 1 . В комнате 5 стульев. Сколькими способами можно разместить на них
а) 7 человек; б) 5 человек; в) 3 человека?
Решение:
а) Прежде всего надо выбрать 5 человек
из 7 для посадки на стулья. Это можно
сделать
способом. С каждым выбором конкретной
пятерки можно произвести
перестановок местами. Согласно теореме
умножения искомое число способов посадки
равно.
Замечание: Задачу можно решать, используя только теорему произведения, рассуждая следующим образом: для посадки на 1-й стул имеется 7 вариантов, на 2-й стул-6 вариантов, на 3-й -5, на 4-й -4 и на 5-й -3. Тогда число способов посадки 7 человек на 5 стульев равно . Решения обоими способами согласуются, так как
б) Решение очевидно
-
в)
- число выборов занимаемых стульев.
- число размещений
трех человек на трех выбранных стульях.
Общее число выборов равно .
Не трудно проверить
формулы
;
;
Число всех подмножеств множества, состоящего из n элементов.
Размещения с повторением
Размещением с повторением из n элементов по m называется всякое упорядоченное подмножество множества N , состоящее из m элементов так, что любой элемент ожжет входить в это подмножество от 1 до m раз, либо вообще в нем отсутствовать .
Число
размещений с повторением обозначают
и вычисляют по формуле, представляющей
собой следствие из теоремы умножения:
Пример 2
.
Пусть дано множество из трех букв N
= {a,
b,
c}.
Назовем словом любой набор из букв,
входящих в это множество. Найдем
количество слов длиной 2, которые можно
составить из этих букв:
.
Замечание:
Очевидно, размещения с повторением
можно рассматривать и при
.
Пример 3 . Требуется из букв {a, b}, составить всевозможные слова длиной 3. Сколькими способами это можно сделать?
Ответ
:
Конспект урока по теме «Элементы комбинаторики»
Цели:
О бучающие:
Формирование основных понятий комбинаторики: размещения из mэлементов по n, сочетания из m элементов по n, перестановки из nэлементов;
Формирование умений и навыков вычисления значений комбинаторных выражений по формулам, решения простейших комбинаторных задач;
Развивающие:
Развитие умения анализировать, обобщать изучаемые факты, выделять и сравнивать существенные признаки, выбирать наиболее эффективные способы решения задач в зависимости от конкретных условий; рефлексия способов и условий действия; контроль и оценка процесса и результатов деятельности;
Воспитательные:
Воспитание интереса к дисциплине, честности, аккуратности, эстетического отношения к оформлению математических решений, воспитание умения слушать и вступать в диалог, участвовать в коллективном обсуждении проблем, интегрироваться в группу сверстников и строить продуктивное взаимодействие, настойчивости в достижении цели и заинтересованности в конечном результате труда; прививать чувство патриотизма.
Обучающийся должен:
знать:
Определения трех важнейших понятий комбинаторики:
Размещения из n элементов по m;
Сочетания из n элементов по m;
Перестановки из n элементов, а также, формулы вычисления их количества.
уметь:
Отличать задачи на «перестановки», «сочетания», «размещения» друг от друга;
Применять основные комбинаторные формулы при решении простейших комбинаторных задач.
ХОД УРОКА
1. Организационный момент.
Ребята, каждая группа в течении года дежурит по техникуму.
Являются ли бригады дежурных в группах постоянными? Скажите, а сколько всего существует способов назначить из n студентов группы mдежурных. В математике есть раздел, который занимается решением подобных задач. Этот раздел называется комбинаторикой.
2. Сообщение темы, целей урока.
Тема сегодняшнего урока «Основные понятия комбинаторики». Давайте вместе попробуем сформулировать цели урока
Ознакомиться с основными понятиями комбинаторики (размещения, сочетания, перестановки)
Научиться решать простейшие комбинаторные задачи
3. Актуализация опорных знаний.
Прежде чем перейти к изучению нового материала, повторим то, что имеет к нему непосредственное отношение. Это уже известное вам понятие «факториал». Итак, кто помнит, что называют «n-факториалом»? Запишите формулу.
Чему, к примеру, равны 2!, 3!, 4!, 5!, 6! ? А кто сможет показать вычисления на доске? А чему равен 1! ? 0! ? Какие значения в данном случае может принимать n?
4. Изложение нового материала.
4.1. Введение общих понятий
Комбинаторикой называют область математики, которая изучает вопросы о числе различных комбинаций (удовлетворяющих тем или иным условиям), которые можно составить из данных элементов.
Комбинаторика – раздел математики, в котором исследуются и решаются задачи выбора элементов из исходного множества и расположения их в некоторой комбинации, составляемой по заданным правилам.
Группы, составленные из каких-либо элементов, называются соединениями .
Различают три вида соединений: размещения , перестановки и сочетания .
Задачи, в которых производится подсчет возможных различных соединений, составленных из конечного числа элементов по некоторому правилу, называются комбинаторными , а раздел математики, занимающийся их решением, - комбинаторикой . Рассмотрим три основных вида соединений и формулы вычисления их количества. Для этого сначала рассмотрим 2 задачи, которые помогут нам сосредоточиться на сути новых понятий.
4.2. Создание проблемной ситуации.
Тексты двух задач на слайде:
Задача 1. В некотором учреждении имеются две различные вакантные должности, на каждую из которых претендуют три сотрудника: A, B, C. Сколькими способами из этих трех кандидатов можно выбрать два лица на эти должности?
Задача 2. Для участия в соревнованиях требуется выбрать двоих спортсменов из трех кандидатов: A, B, C. Сколькими способами можно осуществить этот выбор?
Студентам предлагается два проблемных задания: 1) установить различие между этими двумя внешне схожими задачами и 2) предположить, в какой задаче результат будет больше, и почему. После этого предлагается решить эти задачи методом перебора всевозможных вариантов.
Р ешение задачи 1. AB, BA, BC, CB, AC, CA (всего шесть способов).
Решение задачи 2. AB, BC, AC (всего три способа).
Преподаватель обращает внимание студентов на то, что эти задачи оказались похожими только внешне, из-за того, что в обеих присутствуют два числа: m=3 – общее количество элементов и n=2 – количество выбранных элементов. Но в первой задаче составляются упорядоченные соединения, тогда как во второй задаче порядок следования элементов в соединении не имеет значения.
А если вместо чисел 3 и 2 будут например числа 8 и 3. Подойдет ли этот метод для решения этих задач? Поэтому существуют комбинаторные выражения (формулы) для этих соединений
5.3. Лекция «Основные комбинаторные понятия и формулы».
1) Размещения.
Определение. Размещениями из m элементов по n элементов (n ≤ m) называются такие соединения, каждое из которых содержит n элементов, взятых из m данных разных элементов, и которые отличаются одно от другого либо самими элементами, либо порядком их расположения.
Число размещений из m элементов по n обозначают (от французского «arrangement» - «размещение») и вычисляют по формуле:
Пример 1. Решим задачу 1 с помощью этой формулы:
2) Перестановки.
Определение. Перестановкой из n элементов называют размещение из n элементов по n.
Число перестановок из n элементов обозначается
и вычисляется по формуле:
Задача. Сколькими способами можно расположить в столбик три детали конструктора, различающиеся по цвету?
Ответ:6.
3) Сочетания.
Определение.
Сочетаниями из m элементов по n элементов (n ≤ m) называются такие соединения, каждое из которых содержит n элементов, взятых из m данных элементов, и которые отличаются друг от друга по крайней мере одним элементом.
Число сочетаний из n элементов по m обозначают
(от французского «combination» - «сочетание») и вычисляют по формуле:
Пример 2. Решим задачу 2 с помощью этой формулы:
А теперь решим ту же задачу для случая m=8, n=3:
Снова, как и ожидалось, результат в первой задаче оказался больше, чем во второй.
Мы рассмотрели теоретические основы комбинаторики. Теперь перейдем к этапу закрепления новых знаний при решении задач.
6. Закрепление материала
6.1. Игра «Математическое лото»
Студентам раздаются наборы раздаточных материалов «Математического лото» (по одному на парту). Каждый комплект состоит из 16 математических заданий по основам комбинаторики, картонного листа в виде матрицы размерности 4 на 4 с написанными в ячейках числами-ответами и цветной фотографии, разрезанной на 16 равных прямоугольника. Все части фотографии пронумерованы в соответствии с порядком заданий и перемешаны. Задача студентов – решить 16 заданий, соответствующие частям разрезанной фотографии, и в соответствии с полученными числовыми ответами отыскать их место на картонной матрице, сложив в итоге фото. Задание выполняется как соревнование между малыми группами По 3-4 человека. Определяются три пары, которые не только сложат картинку раньше всех, но и представят в письменном виде все подробные решения.
Перед началом игры преподаватель мотивирует студентов на активное участие в ней, сообщая, что это упражнение позволит наилучшим образом сформировать навыки комбинаторных вычислений, что значительно упростит выполнение домашнего задания. Кроме того, выполняя это упражнение, можно совместить полезное с приятным, так как результат вызовет эстетические чувства.
Задания.
Вычислите.
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
.
Решения:
В завершении игры объявляются и поощряются победители.
6.2. Решение комбинаторных задач.
При решении комбинаторных задач важно научиться различать виды соединений.
Чтобы отличать задачи на подсчёт числа размещений от задач на подсчёт числа сочетаний, определим, важен или нет порядок в следующих выборках:
а) судья хоккейного матча и его помощник;
б) три ноты в аккорде;
в) «Шесть человек останутся убирать класс!»
г) две серии для просмотра из многосерийного фильма.
Ответ: а)да; б)нет; в)нет; г)да.
Задача 1. Сколькими способами могут занять I, II, III места 8 участниц финального забега на дистанции 100 м?
Ответ: 366.
Задача 2. Из 30 обучающихся группы надо выбрать старосту и помощника старосты. Сколькими способами это можно сделать?
Ответ: 870.
Задача 3. Сколькими способами можно составить букет из трёх цветков, выбирая цветы из девяти имеющихся?
Ответ: 84.
Задача 4. В группе 7 человек успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде?
Ответ:21
6.3 Самостоятельная работа
Проверь себя
1 .Определите вид соединений:
а) Соединения из n элементов, отличающиеся друг от друга только порядком расположения в них элементов, называются __________ перестановки
б) Соединения из m элементов по n , отличающихся друг от друга только составом элементов, называются _______________ сочетания
в) Соединения из m элементов по n , отличающихся друг от друга составом элементом и порядком их расположения, называются _________ размещения
2 .Восстановите соответствие типов соединений и формул для их подсчёта
А.сочетания Ответ:
Подведение итогов самостоятельной работы
7. Подведение итогов урока
Обобщаются новые знания, делаются выводы о достигнутых целях урока. Поощряются активные студенты, выставляются обоснованные преподавателем оценки.
8. Домашнее задание
Подготовка сообщений по темам: «Истории комбинаторики», «Комбинаторика и ее применение в реальной жизни».
Элементы комбинаторики
Комбинаторика – это наука о расположении элементов в определенном порядке и о подсчете числа способов такого расположения.
Комбинаторный принцип умножения если одну часть действия можно выполнить способами, а другую - способами, то все действие можно выполнить числом способов.
Пример. Пусть требуется составить набор из ручки, карандаша и линейки. Имеется:
5 различных ручек,
7 различных карандашей,
10 различных линеек.
Сколькими способами можно составить требуемыйнабор?
Решение. Действием в данном случае является составление набора из ручки, карандаша и линейки; действие распадается на три этапа (части): выбрать ручку, выбрать линейку и выбрать карандаш. Первую часть действия – выбрать ручку – можно выполнить пятью способами, вторую часть действия – выбрать карандаш – можно выполнить семью способами, третью часть действия – выбрать линейку – можно выполнить десятью способами. Тогда все действие можно выполнить
Число способов. Т.е. возможно 350 вариантов такого набора.
Пример. Сколько существуетнаборов длиныиз нулей и единиц?
Решение. Действием в данном случае является составление набора длины из нулей и единиц.
Набор будет составлен, если все позиций (мест) будут заполнены нулями и единицами. Действие распадается на частей: заполнить первую позицию, вторую и т.д., заполнить - ю позицию. Первую часть действия – написать первую компоненту - можно двумя способами: можно написать 0, а можно написать 1, написать вторую компоненту тоже можно двумя способами, и так все мест в наборе: на каждом месте можно написать либо 0 либо 1:
Тогда все действие согласно комбинаторному принципу умножения можно выполнить числом способов:
Комбинаторный принцип сложения. Если два действия взаимно исключают друг друга, и одно из них можно выполнить способами, а другое - способами, то оба действия можно выполнить числом способов.
Пример.
Выборкой
объема из множества 
называется всякая
последовательность из элементов множества .
Если элементы в выборке не повторяются, то выборка называется бесповторной , иначе – выборкой с повторениями
При бесповторной выборке все равно, каким образом осуществляется выбор: берутся все элементы сразу,или же поочередно (по одному).
Расположение элементоввыборки в определенном порядке называется упорядочением , при этом выборка называется упорядоченной , в противном случае – неупорядоченной .
Рассмотрим бесповторную выборку
Расположение различных элементов в определенном порядке называется перестановкой без повторений из элементов.
Например, на множестве из трех элементов возможны следующие перестановки: .
Число различных перестановок без повторений из элементов обозначается и равно , т.е.
Сочетанием без повторений из элементов по называется неупорядоченное - элементное подмножество -элементного множества. Число сочетаний без повторений из элементов по равно :
Например, требуется подсчитать, сколькими способами можно составить бригаду из трех человек для дежурства вгруппе из 30 человек. Поскольку порядок расположения людей в бригаде не фиксируется и люди не повторяются , то мы имеем случай сочетаний из 30 элементов по 3 без повторений:
Таким образом, бригаду дежурных из трех человек в группе из 30 человек можно выбрать 4060 различными способами.
Размещением без повторений из элементов по называется упорядоченное - элементное подмножество -элементного множества.
Теорема.
Число размещений без повторений из элементов по равно:
Доказательство . Чтобы получить упорядоченное - элементное подмножество -элементного множества, нужно выполнить два этапа: выбрать элементов из (это можно выполнить числом способов) и затем упорядочить выбранные элементы (это можно сделать числом способов). Согласно комбинаторному принципу умножения, все действие -получить упорядоченное - элементное подмножество -элементного множества – можно числом способов.
Свойства сочетаний без повторений :
Доказательство.
Поскольку 
и
, то
утверждаемое очевидно.
2)
(без доказательства).
Значения могут быть найдены не расчетом по формуле количества сочетаний, а с помощью так называемого треугольника Паскаля. (Блез Паскаль (1623 – 1662) – французский математик).
Этот треугольник имеет вид:
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
Закономерность его построения такова: складывая две рядом стоящие числа, получаем число, стоящее ниже между ними. Первая строчка – значения числа сочетаний из 1 (), вторая – из 2 ( - слева направо), и т.д.
Рассмотрим выборку с повторениями
Пусть имеется выборка из элементов, причем элементов из них - одинаковые.
1. Число различных перестановок на элементах такой выборки равно:
- число перестановок с повторениями на множестве из элементов
2. Сочетание с повторениями из элементов по - неупорядоченная выборка элементов с возвращением из множества, содержащегоэлементов:
- число различных сочетанийс повторениями из элементов по
3. Размещения с повторениями из элементов по - расположение различных шаров по различным ячейкам
- число различных размещений с повторениями
Пример . Сколько различных 4-буквенных слов можно составить из символов ?
Решение. Другими словами, требуется найти число перестановок с повторениями на4 элементах выборки, в которойдва элемента одинаковы:
Пример . Сколько различных перестановок можно составить избукв словаАБАКАН?
Решение. Требуется найти число перестановок на множестве из 6 элементов, среди которых три элемента одинаковы:
.
Верно обобщение рассматриваемой формулы: число различных перестановок на множестве из элементов, среди которых имеется
Элементов первого вида,
Элементов второго вида,
Элементов - го вида
равно:
Пример. Сколько перестановок можно получить из букв слова КОЛОКОЛА?
Решение. Требуется найти число перестановок с повторениями на множестве из 8 букв, среди которых:
буква К повторяется 2 раза;
буква О повторяется 3 раза;
буква Л повторяется 2 раза
буква А повторяется 1 раз.
Таким образом, .
Пример. Сколькими способами можно составить набор из 5 шоколадок, если имеются шоколадки трех сортов в количестве по 10 штук каждого вида?
Решение. Поскольку при составлении шоколадного набора порядок расположения шоколадок не важен, то используем для подсчета формулу сочетаний с повторениями:
Пример. Сколькими способами можно рассадить 7 человек по 9 вагонам?
Решение. Поскольку по условию задачи в один вагон могут сесть несколько человек, и поскольку рассадка зависит от того кто в каком вагоне находится, то используем формулу размещения с повторениями:
Пример. Сколькими способами можно рассадить 7 человек по 9 вагонам по одному в вагон?
Решение. Поскольку по условию задачи в один вагон могут сесть только один человек, и поскольку рассадка зависит от того кто в каком вагоне находится, то используем формулу размещений без повторений:
Эту же задачу можно решить, применяя комбинаторный принцип умножения: действие – рассадить 7 человек распадается на 7 этапов: разместить первого пассажира, разместить второго пассажира, …, разместить седьмого пассажира. Первый этап – размещение первого пассажира можно выполнить 9 способами, второго пассажира тоже можно разместить9 способами, и т.д. :
Пример. Сколько различных сигналов можно составить из четырех флажков различных цветов, если каждый сигнал должен состоять не менее чем из двух флажков?
Решение. Составить сигнал можно из двух флажков, из трех или из четырех. Перечисленные ситуации взаимно исключают друг друга (два флажка – это не три и не четыре),поэтому вычислим, сколькими способами можно составить сигнал в каждой из перечисленных ситуаций,и сложим полученные результаты.
Действие – составить сигнал – означает выбрать флажки из четырех и расположить их в определенном порядке. Таким образом, в каждом случае нужно выполнить два этапа: первый - выбрать флажки, второй – расположить выбранные флажки в определенном порядке.
Составляем сигналы из двух флажков: выбрать два
флажка из четырех можно 
различными способами,
и расположить выбранные два флажка в определенном порядке можно числом способов. Таким
образом, согласно комбинаторному принципу умножения, можно составить различных сигналов из двух флажков.
способами. Значит,
можно составить различных сигнала из
четырех флажков.
Применим теперь комбинаторный принцип сложения:
всего существует 
сигналов из не менее,
чем двух флажков.
Пример. Номер автомобиля состоит из трех букв и трех цифр. Сколько различных номеров можно составить, используя 10 цифр и алфавит в 30 букв.
Очевидно, что количество всех возможных комбинаций из 10 цифр по 4 равно 10.000.
Число всех возможных комбинаций из 30 букв по две равно
.
Если учесть возможность того, что буквы могут повторяться, то число повторяющихся комбинаций равно 30 (одна возможность повтора для каждой буквы). Итого, полное количество комбинаций по две буквы равно 900.
Если к номеру добавляется еще одна буква из алфавита в 30 букв, то количество комбинаций увеличивается в 30 раз, т.е. достигает 27.000 комбинаций.
Окончательно, т.к. каждой буквенной комбинации можно поставить в соответствие числовую комбинацию, то полное количество автомобильных номеров равно 270.000.000.
Е.Г. Hикифорова