Сочетание без повторений формула. Формулы комбинаторики
В этом разделе будут рассмотрены три вида соединений без повторений: размещения, перестановки и сочетания. Ради краткости добавку «без повторений» будем опускать.
1. Размещения. Размещения из n элементов по – это упорядоченные наборы из попарно различных элементов -множества . Таким образом, два размещения из элементов по различаются либо порядком, либо составом входящих в них элементов. Например, размещения из 3-множества по 2 исчерпываются следующими упорядоченными парами:
, , , , , .
Нас будет интересовать задача нахождения числа всех размещений из элементов по
. В качестве первого элемента можно выбрать любой из элементов множества . После того как выбран первый элемент, второй элемент можно выбрать лишь способами (можно взять любой элемент, исключая выбранный). После выбора первых двух элементов остаются лишь возможности выбрать третий элемент и т. д. Последний -й элемент можно выбрать способами – ведь до него уже выбраны элемент, а потому осталось лишь элементов. По правилу произведения получаем, что число всевозможных упорядоченных наборов 
равно произведению чисел , , , …, , т.е. справедлива следующая
Т е о р е м а 1. Число размещений из элементов по находится по формуле
Напомним, что произведение первых n
натуральных чисел, т.е. , называют n-факториалом
и обозначают . Произведение можно записать в виде дроби 
= и поэтому формулу (1) можно переписать следующим образом
В частности, при из формулы (2) получаем
Это означает, что существует единственный упорядоченный набор длины 0 – пустой кортеж, не имеющий ни одной компоненты.
Пример 1. Найти число пятизначных чисел в десятичной системе счисления, в записи которых цифры не повторяются.
□ Рассуждая по аналогии с тем, как это делалось при рассмотрении примера 1 (2-й способ) из § 2, приходим к выводу, что искомое число есть .
2. Перестановки.
Рассмотримтеперь различные линейные упорядочения данного -множества . Получаемые при этом упорядоченные наборы 
отличаются друг от друга лишь порядком входящих в них элементов. Их называют перестановками
(без повторений) из n элементов,
а их число обозначают через . Например, если , то = 6, так как из трех элементов можно составить шесть перестановок:
, , , , , .
Общая формула для получается из формулы (1), поскольку перестановка из элементов – это то же самое, что размещение без повторений из элементов по . Полагая в (1) получим = = = = . Итак, справедлива
Т е о р е м а 2. Число перестановок из элементов равно -факториал, т.е.
Полагая в формуле (2) , получаем
Сравнивая (3) и (4), приходим к выводу, что 0! = 1. На первый взгляд это равенство кажется парадоксальным. Но для всех справедливо равенство = . Если потребовать, чтобы это равенство было справедливо и при , то получим . Отсюда вновь следует, что естественно положить0! = 1 .
Пример 2. Сколькимиспособамиможно расположить на полке 7 различных учебников так, чтобы «Алгебра» и «Геометрия» не стояли рядом?
□ Условимся указанные учебники обозначать для краткости буквами А и Г соответственно. Число всевозможных способов расстановки учебников равно числу перестановок из семи элементов, т.е. . Но при этом сосчитаны и те, в которых встречаются рядом учебники А и Г, причем в двух позициях: АГ и ГА. Считая АГ и ГА за одну книгу, для каждого такого расположения получим расстановок, в которых учебники А и Г встречаются рядом. Искомое число расстановок учебников равно .
3. Сочетания.
Одной из важнейших задач комбинаторики является подсчет числа k
-подмножеств данного n
-множества . Такие неупорядоченные подмножества называются сочетаниями из элементов по
, а их число обозначают через (от французского слова combinaison – сочетание). Например, из элементов 4-множества 
можно составить следующие 2-множества: , , , , , . Число этих подмножеств равно 6. Следовательно, = 6. Отметим, что = 1, так как каждое множество имеет лишь одно 0-множество, а именно, пустое множество . Далее понятно, что = , поскольку в ‑множества содержится одноэлементных подмножеств. Ясно также, что .
Выведем формулу, выражающую через и . Для этого укажем способ получения всех размещений из элементов по . Выберем любое k -подмножество данного n -множества . Это можно сделать способами. Каждое такое k -подмножество упорядочим всевозможными способами. Таких различных упорядочений столько, сколько можно составить перестановок из элементов, т.е. = . Понятно, что таким способом получатся все размещений из элементов по . Значит, имеет место равенство = . Отсюда вытекает справедливость следующего утверждения.
Т е о р е м а 3. Число сочетаний из n элементов по k вычисляется по формуле :
= = 
= . (5)
Пример 3. Найти число всех диагоналей правильного n -угольника.
□ Любые две вершины n -угольника однозначно определяют отрезок, соединяющие эти вершины. Поэтому число всевозможных отрезков, соединяющих вершины n -угольника, равно числу сочетаний из по 2, т.е. . Но среди них находятся и сторон n -угольника, которые диагоналями не являются,
Таким образом, искомое число равно
.
Например, при получаем, что правильный 10-угольник имеет = 35 диагоналей.
Свойства сочетаний.
□ В самом деле, в силу формулы (5) имеем
= 
= = .
□ Действительно,
= 
= = . =
Непосредственно свойств ‑ сочетаний вытекают следующие
Следует отметить, что комбинаторика является самостоятельным разделом высшей математики (а не частью тервера) и по данной дисциплине написаны увесистые учебники, содержание которых, порой, ничуть не легче абстрактной алгебры. Однако нам будет достаточно небольшой доли теоретических знаний, и в данной статье я постараюсь в доступной форме разобрать основы темы с типовыми комбинаторными задачами. А многие из вас мне помогут;-)
Чем будем заниматься? В узком смысле комбинаторика - это подсчёт различных комбинаций, которые можно составить из некоторого множества дискретных объектов. Под объектами понимаются какие-либо обособленные предметы или живые существа - люди, звери, грибы, растения, насекомые и т.д. При этом комбинаторику совершенно не волнует, что множество состоит из тарелки манной каши, паяльника и болотной лягушки. Принципиально важно, что эти объекты поддаются перечислению - их три (дискретность) и существенно то, что среди них нет одинаковых.
С множеством разобрались, теперь о комбинациях. Самыми распространёнными видами комбинаций являются перестановки объектов, их выборка из множества (сочетание) и распределение (размещение). Давайте прямо сейчас посмотрим, как это происходит:
Перестановки, сочетания и размещения без повторений
Не пугайтесь малопонятных терминов, тем более, некоторые из них действительно не очень удачны. Начнём с хвоста заголовка - что значит «без повторений »? Это значит, что в данном параграфе будут рассматриваться множества, которые состоят из различных объектов. Например, … нет, кашу с паяльником и лягушкой предлагать не буду, лучше что-нибудь повкуснее =) Представьте, что перед вами на столе материализовалось яблоко, груша и банан (при наличии таковых ситуацию можно смоделировать и реально). Выкладываем фрукты слева направо в следующем порядке:
яблоко / груша / банан
Вопрос первый : сколькими способами их можно переставить?
Одна комбинация уже записана выше и с остальными проблем не возникает:
яблоко / банан / груша
груша / яблоко / банан
груша / банан / яблоко
банан / яблоко / груша
банан / груша / яблоко
Итого : 6 комбинаций или 6 перестановок .
Хорошо, здесь не составило особого труда перечислить все возможные случаи, но как быть, если предметов больше? Уже с четырьмя различными фруктами количество комбинаций значительно возрастёт!
Никаких мучений - 3 объекта можно переставить способами.
Вопрос второй : сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт?
Зачем выбирать? Так нагуляли же аппетит в предыдущем пункте - для того, чтобы съесть! а) Один фрукт можно выбрать, очевидно, тремя способами - взять либо яблоко, либо грушу, либо банан.
Формальный подсчёт проводится по формуле количества сочетаний
:
Запись в данном случае следует понимать так: «сколькими способами можно выбрать 1 фрукт из трёх?»
б) Перечислим все возможные сочетания двух фруктов:
яблоко и груша;
яблоко и банан;
груша и банан.
Количество комбинаций легко проверить по той же формуле:
Запись понимается аналогично: «сколькими способами можно выбрать 2 фрукта из трёх?».
в) И, наконец, три фрукта можно выбрать единственным способом:
Кстати, формула количества сочетаний сохраняет смысл и для пустой выборки:
способом можно выбрать ни одного фрукта - собственно, ничего не взять и всё.
г) Сколькими способами можно взять хотя бы один
фрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта или все 3 фрукта:
способами можно выбрать хотя бы один фрукт.
Для ответа на следующий вопрос мне требуется два добровольца… …Ну что же, раз никто не хочет, тогда буду вызывать к доске =)
Вопрос третий : сколькими способами можно раздать по одному фрукту Даше и Наташе?
Для того чтобы раздать два фрукта, сначала нужно их выбрать. Согласно пункту «бэ» предыдущего вопроса, сделать это можно способами, перепишу их заново:
яблоко и груша;
яблоко и банан;
груша и банан.
Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов:
яблоком можно угостить Дашу, а грушей - Наташу;
либо наоборот - груша достанется Даше, а яблоко - Наташе.
И такая перестановка возможна для каждой пары фруктов.
В данном случае работает формула количества размещений
:
Она отличается от формулы тем, что учитывает не только количество способов, которым можно выбрать несколько объектов, но и все перестановки объектов в каждой возможной выборке. Так, в рассмотренном примере, важно не только то, что можно просто выбрать, например, грушу и банан, но и то, как они будут распределены (размещены) между Дашей и Наташей.
Постарайтесь хорошо уяснить разницу между перестановками, сочетаниями и размещениями. В простейших случаях можно пересчитать все возможные комбинации вручную, но чаще всего это становится неподъемной задачей, именно поэтому и нужно понимать смысл формул.
Также напоминаю, что сейчас речь идёт о множестве с различными объектами, и если яблоко/грушу/банан заменить на 3 яблока или даже на 3 очень похожих яблока, то в контексте рассмотренной задачи они всё равно будут считаться различными .
Остановимся на каждом виде комбинаций подробнее:
Перестановки
Перестановками называют комбинации, состоящие из одних и тех же различных объектов и отличающиеся только порядком их расположения. Количество всех возможных перестановок выражается формулой
Отличительной особенностью перестановок является то, что в каждой из них участвует ВСЁ множество, то есть, все объектов. Например, дружная семья:
Задача 1
Сколькими способами можно рассадить 5 человек за столом?
Решение : используем формулу количества перестановок:
Ответ : 120 способами
Невероятно, но факт. Обратите внимание, что здесь не имеет значения круглый ли стол, квадратный, или вообще все люди сели на скамейку вдоль одной стены - важно лишь количество объектов и их взаимное расположение. Помимо перестановок людей, часто встречается задача о перестановках различных книг на полке, но это было бы слишком просто даже для чайника:
Задача 2
Сколько четырёхзначных чисел можно составить из четырёх карточек с цифрами 0, 5, 7, 9?
Для того чтобы составить четырёхзначное число нужно задействовать все четыре карточки (цифры на которых различны! ) , и это очень важная предпосылка для применения формулы Очевидно, что, переставляя карточки, мы будем получать различные четырёхзначные числа, … стоп, а всё ли тут в порядке? ;-)
Хорошенько подумайте над задачей! Вообще, это характерная черта комбинаторных и вероятностных задач - в них НУЖНО ДУМАТЬ. И зачастую думать по-житейски, как, например, в разборе вступительного примера с фруктами. Нет, конечно, я не призываю тупо прорабатывать другие разделы математики, однако должен заметить, что те же интегралы можно научиться решать чисто механически.
Решение и ответ в конце урока.
Увеличиваем обороты:
Сочетания
В учебниках обычно даётся лаконичное и не очень понятное определение сочетаний, поэтому, в моих устах формулировка будет не особо рациональной, но, надеюсь, доходчивой:
Сочетаниями
называют различные комбинации из объектов, которые выбраны из множества различных объектов, и которые отличаются друг от друга хотя бы одним объектом. Иными словами, отдельно взятое сочетание - это уникальная выборка из элементов, в которой не важен их порядок
(расположение). Общее же количество таких уникальных сочетаний рассчитывается по формуле 
.
Задача 3
В ящике находится 15 деталей. Сколькими способами можно взять 4 детали?
Решение : прежде всего, снова обращаю внимание на то, что по логике условия, детали считаются различными - даже если они на самом деле однотипны и визуально одинаковы (в этом случае их можно, например, пронумеровать) .
В задаче речь идёт о выборке из 4-х деталей, в которой не имеет значения их «дальнейшая судьба» - грубо говоря, «просто выбрали 4 штуки и всё». Таким образом, у нас имеют место сочетания деталей. Считаем их количество:
Здесь, конечно же, не нужно ворочать огромные числа .
В похожей ситуации я советую использовать следующий приём: в знаменателе выбираем наибольший факториал (в данном случае ) и сокращаем на него дробь. Для этого числитель следует представить в виде . Распишу очень подробно:
Способами можно взять 4 детали из ящика.
Ещё раз: что это значит? Это значит, что из набора 15-ти различных деталей можно составить одну тысячу триста шестьдесят пять уникальных сочетания 4-х деталей. То есть, каждая такая комбинация из 4-х деталей будет отличаться от других комбинаций хотя бы одной деталью.
Ответ : 1365 способами
Формуле необходимо уделить самое пристальное внимание, поскольку она является «хитом» комбинаторики. При этом полезно понимать и без всяких вычислений записывать «крайние» значения: . Применительно к разобранной задаче:
Единственным способом можно взять ни одной детали;
способами можно взять 1 деталь (любую из 15-ти);
способами можно взять 14 деталей (при этом какая-то одна из 15-ти останется в ящике);
- единственным способом можно взять все пятнадцать деталей.
Рекомендую внимательно ознакомиться с биномом Ньютона и треугольником Паскаля , по которому, к слову, очень удобно выполнять проверку вычислений при небольших значениях «эн».
Задача 4
Сколькими способами из колоды в 36 карт можно выбрать 3 карты?
Это пример для самостоятельного решения. Чем приятны многие комбинаторные задачи, так это краткостью - главное, разобраться в сути. И суть, бывает, открывается с различных сторон. Разберём весьма поучительный пример:
Задача 4
В шахматном турнире участвует человек и каждый с каждым играет по 1-й партии. Сколько всего партий сыграно в турнире?
Поскольку я сам играю в шахматы и неоднократно принимал участие в круговых турнирах, то сразу же сориентировался по турнирной таблице размером клеток, в которой результат каждой партии учитывается дважды и, кроме того, затушёвываются клетки «главной диагонали» (т.к. участники не играют сами с собой) . Исходя из проведённых рассуждений, общее количество сыгранных партий рассчитывается по формуле . Такое решение полностью корректно (см. соответствующий файл банка готовых решений ) и на долгое время я забыл о нём по принципу «решено, да и ладно».
Однако один из посетителей сайта заметил, что на самом деле здесь можно руководствоваться самыми что ни на есть банальными сочетаниями:
различных пар можно составить из соперников (кто играет белыми, кто чёрными - не важно)
.
Эквивалентной является задача о рукопожатиях: в отделе работает мужчин и каждый с каждым здоровается за руку, сколько рукопожатий они совершают? К слову, шахматисты тоже пожимают друг другу руку перед каждой партией.
Ну а вывода тут два:
Во-первых, не всё очевидное - очевидно;
И во-вторых, не бойтесь решать задачи «нестандартно»!
Большое спасибо за ваши письма, они помогают улучшить качество учебных материалов!
Размещения
Или «продвинутые» сочетания. Размещениями называют различные комбинации из объектов, которые выбраны из множества различных объектов, и которые отличаются друг от друга как составом объектов в выборке, так и их порядком . Количество размещений рассчитывается по формуле
Что наша жизнь? Игра:
Задача 5
Боря, Дима и Володя сели играть в «очко». Сколькими способами им можно сдать по одной карте? (колода содержит 36 карт)
Решение : ситуация похожа на Задачу 4, но отличается тем, что здесь важно не только то, какие три карты будут извлечены из колоды, но и то, КАК они будут распределены между игроками. По формуле размещений:
Способами можно раздать 3 карты игрокам.
Есть и другая схема решения, которая, с моей точки зрения, даже понятнее:
способами можно извлечь 3 карты из колоды.
Теперь давайте рассмотрим, какую-нибудь одну из семи тысяч ста сорока комбинаций, например: король пик, 9 червей, 7 червей. Выражаясь комбинаторной терминологией, эти 3 карты можно «переставить» между Борей, Димой и Володей способами:
КП, 9Ч, 7Ч;
КП, 7Ч, 9Ч;
9Ч, КП, 7Ч;
9Ч, 7Ч, КП;
7Ч, КП, 9Ч;
7Ч, 9Ч, КП.
И аналогичный факт справедлив для любого уникального набора из 3-х карт. А таких наборов, не забываем, мы насчитали . Не нужно быть профессором, чтобы понять, что найденное количество сочетаний следует умножить на шесть:
Способами можно сдать по одной карте 3-м игрокам.
По существу, получилась наглядная проверка формулы , окончательный смысл которой мы проясним в следующем параграфе.
Ответ : 42840
Возможно, у вас остался вопрос, а кто же раздавал карты? …Наверное, преподаватель =)
И чтобы никому не было обидно, в следующей задаче примет участие вся студенческая группа:
Задача 6
В студенческой группе 23 человека. Сколькими способами можно выбрать старосту и его заместителя?
Задача о «размещении» должностей в коллективе встречается очень часто и является самым настоящим баяном. Краткое решение и ответ в конце урока.
Число размещений без повторений из n по k n k различными координатами.
Число размещений без повторений находится по формуле:
Пример: Сколькими способами можно построить 3-значное число с различными цифрами, не содержащее цифры 0?
Количество цифр
,
размерность вектора с различными
координатами
Число размещений с повторениями
Число размещений с повторениями из n по k – это число способов, сколькими можно из n различных элементов построить векторов с k координатами, среди которых могут быть одинаковые.
Число размещений с повторениями находится по формуле:
.
Пример: Сколько слов длины 6 можно составить из 26 букв латинского алфавита?
Количество букв
,
размерность вектора
Число перестановок без повторений
Число перестановок без повторений из n элементов – это число способов, сколькими можно расположить на n различных местах n различных элементов.
Число перестановок без повторений находится по формуле:
.
Замечание:
Мощность искомого множества А
удобно искать по формуле:
,
гдех
– число способов выбрать нужные места;
у
– число
способов расположить на них нужные
элементы; z
– число
способов расположить остальные элементы
на оставшихся местах.
Пример. Сколькими способами можно расставить на книжной полке 5 различных книг? В скольких случаях две определенные книги А и В окажутся рядом?
Всего способов
расставить 5 книг на 5-ти местах – равно
= 5! = 120.
В задаче х
– число способов выбрать два места
рядом, х
= 4;
у
– число
способов расположить две книги на двух
местах, у
= 2! = 2;
z
– число
способов расположить остальные 3 книги
на оставшихся 3-х местах, z
= 3! = 6.
Значит
=
48.
Число сочетаний без повторений
Число сочетаний без повторений из n по k – это число способов, сколькими можно из n различных элементов выбрать k штук без учета порядка.
Число сочетаний без повторений находится по формуле:
.
Свойства:
1)
;
2)
;
3)
;
4)
;
5)
;
6)
.
Пример. В урне 7 шаров. Из них 3 белых. Наугад выбирают 3 шара. Сколькими способами это можно сделать? В скольких случаях среди них будет ровно один белый.
Всего способов
.
Чтобы получить число способов выбрать
1 белый шар (из 3-х белых) и 2 черных шара
(из 4-х черных), надо перемножить
и
Таким образом искомое количество
способов
Упражнения
1. Из 35 учащихся класс по итогам года имели “5” по математике – 14 человек; по физике – 15 человек; по химии – 18 человек; по математике и физике – 7 человек; по математике и химии – 9 человек; по физике и химии – 6 человек; по всем трем предметам – 4 человек. Сколько человек имеют “5” по указанным предметам? Сколько человек не имеет “5” по указанным предметам? Имеет “5” только по математике? Имеет “5” только по двум предметам?
2. В группе из 30 студентов каждый знает, по крайней мере, один иностранный язык – английский или немецкий. Английский знают 22 студента, немецкий – 17. Сколько студентов знают оба языка? Сколько студентов знают немецкий язык, но не знают английский?
3. В 20 комнатах общежития института Дружбы Народов живут студенты из России; в 15 – из Африки; в 20 – из стран Южной Америки. Причем в 7 – живут россияне и африканцы, в 8 – россияне и южноамериканцы; в 9 – африканцы и южноамериканцы; в 3 – и россияне, и южноамериканцы, и африканцы. В скольких комнатах живут студенты: 1) только с одного континента; 2) только с двух континентов; 3) только африканцы.
4. Каждый из 500 студентов обязан посещать хотя бы один из трех спецкурсов: по математике, физике и астрономии. Три спецкурса посещают 10 студентов, по математике и физике – 30 студентов, по математике и астрономии – 25; спецкурс только по физике – 80 студентов. Известно также, что спецкурс по математике посещают 345 студентов, по физике – 145, по астрономии – 100 студентов. Сколько студентов посещают спецкурс только по астрономии? Сколько студентов посещают два спецкурса?
5. Староста курса представил следующий отчет по физкультурной работе. Всего – 45 студентов. Футбольная секция – 25 человек, баскетбольная секция – 30 человек, шахматная секция – 28 человек. При этом, 16 человек одновременно посещают футбольную и баскетбольную секции, 18 – футбольную и шахматную, 17 – баскетбольную и шахматную, 15 человек посещают все три секции. Объясните, почему отчет не был принят.
6. В аквариуме 11 рыбок. Из них 4 красных, остальные золотые. Наугад выбирают 4 рыбки. Сколькими способами это можно сделать? Найти число способов сделать это так, чтобы среди них будет: 1) ровно одна красная; 2) ровно 2 золотых; 3) хотя бы одна красная.
7. В списке 8 фамилий. Из них 4 – женские. Сколькими способами их можно разделить на две равные группы так, чтоб в каждой была женская фамилия?
8. Из колоды в 36 карт выбирают 4 . Сколько способов сделать это так, чтобы: 1) все карты были разных мастей; 2) все карты были одной масти; 3) 2 красные и 2 черные.
9. На карточках разрезной азбуки даны буквы К, К, К, У, У, А, Е, Р. Сколько способов сложить их в ряд так, что бы получилось «кукареку».
10. Даны карточки разрезанной азбуки с буквами О, Т, О, Л, О, Р, И, Н, Г, О, Л, О, Г. Сколько способов сложить их так, что бы получилось слово «отолоринголог».
11. Даны карточки нарезной азбуки с буквами Л, И, Т, Е, Р, А, Т, У, Р, А. Сколько способов сложить их в ряд так, что бы получилось слово «литература».
12. 8 человек становятся в очередь. Сколько способов сделать это так, что бы два определенных человека А и Б оказались: 1) рядом; 2) на краях очереди;
13. 10 человек садятся за круглый стол на 10 мест. Сколькими способами это можно сделать так, чтоб рядом оказались: 1) два определенных человека А и Б; 2) три определенных человека А, Б и С.
14. Из 10 арабских цифр составляют 5-значный код. Сколькими способами это можно сделать так, чтобы: 1) все цифры были разными; 2) на последнем месте четная цифра.
15. Из 26 букв латинского алфавита (среди них 6 гласных) составляется шестибуквенное слово. Сколькими способами это можно сделать так, чтобы в слове были: 1) ровно одна буква «а»; 2) ровно одна гласная буква; ровно две буквы «а»; в) ровно две гласные.
16. Сколько четырехзначных чисел делятся на 5?
17. Сколько четырехзначных чисел с различными цифрами делятся на 25?
19. Брошены 3 игральные кости. В скольких случаях выпала: 1) ровно 1 «шестерка»; 2) хотя бы одна «шестерка».
20. Брошены 3 игральные кости. В скольких случаях будет: 1) все разные; 2) ровно два одинаковых числа очков.
21. Сколько слов с различными буквами можно составить из алфавита а, в, с, d. Перечислить их все в лексикографическом порядке: abcd, abcd….
Основные формулы комбинаторики
Задачи, в которых речь идет о тех или иных комбинациях объектов, их называют комбинаторными задачами . Область математики, в которой рассматриваются комбинаторные задачи, называют комбинаторикой .
Комбинаторика – область математики, в которой рассматриваются задачи о тех или иных комбинациях объектов.
Правило суммы
Пусть имеется n попарно непересекающихся множеств A 1 , A 2 ,…A n, содержащих m 1 , m 2 ,…, m n элементов соответственно. Число способов, которыми можно выбрать один элемент из всех этих множеств, равно
m 1 m 2 … m n .
Пример. На курсе имеется 3 группы. В первой – 25 человек, во второй – 30, в третьей – 20. Сколькими способами из них можно выбрать одного студента?
Решение. Из первой группы одного человека можно выбрать 25 способами, из второй – 30, из третьей – 20. Чтобы найти ответ, нужно сложить все эти способы:
25 30 20=75.
Ответ: выбрать одного студента из трех групп можно 75 способами.
Правило произведения
Пусть имеется. n множеств A 1 , A 2 ,…A n ,содержащих m 1 , m 2,…, m n элементов соответственно. Число способов, которыми можно выбрать по одному элементу из каждого множества
m 1 ּm 2 ּ …ּm n .
Пример. На курсе имеется 3 группы. В первой – 25 человек, во второй – 30, в третьей – 20. Сколькими способами из каждой из них можно выбрать по одному студенту?
Решение. Из первой группы одного человека можно выбрать 25 способами, из второй – 30, из третьей – 20. Чтобы найти ответ, нужно перемножить эти числа:
25ּ30ּ20=15000.
Ответ: для того, чтобы из каждой группы выбрать по одному студенту, существует 15000 способов.
^ Если выбираем один элемент из нескольких множеств, то применяем правило суммы.
Если выбираем по одному элементу из нескольких множеств, то применяем правило произведения.
Факториалом числаn называется последовательное произведение натуральных чисел от единицы до самого числа n:
Примечание: 0!=1.
Перестановки без повторений
Перестановками из n различных элементов называются размещения из этих n элементов по n. Перестановки - частный случай размещений.
Пример. Сколькими способами можно расставить в шеренгу студентов группы из 25 человек?
Решение. Число способов есть число перестановок из 25 элементов, то есть:
P 25 = 25ּ24ּ23ּ…ּ1=25!=1,55ּ10 25 .
Ответ: расставить в шеренгу студентов группы из 25 человек можно 1,55ּ10 25 способами.
Размещения без повторений
Различные упорядоченные подмножества по m элементов данного множества, содержащего n элементов, называются размещениями из n по m. Их число равно:
В частности: 
.
Пример. Из группы, состоящей из 25 человек, надо выбрать шахматную команду из четырех человек на I, II, III и IV доски. Сколькими способами это можно сделать?
Решение. Так как из 25 человек выбираются 4 и порядок важен, то число способов есть число размещений из 25 по 4, то есть:
Ответ: выбрать из 25 человек шахматную команду из четырех человек на I, II, III и IV доски можно 303600 способами.
Сочетания без повторений.
Различные неупорядоченные подмножества по m элементов из данного множества, содержащего n элементов, называются сочетаниями из n по m. Их число равно:
В частности, .
Пример. Сколькими способами из группы в 25 человек можно выбрать баскетбольную команду из пяти человек?
Решение. Так как из 25 человек выбираются 5 и порядок не важен, то число способов есть число сочетаний из 25 по 5, то есть:
Ответ: из группы в 25 человек можно выбрать баскетбольную команду 53130 способами.
Перестановки - это комбинации, состоящие из одних и тех же элементов и отличающиеся только порядком расположения этих элементов. Возьмем n различных элементов a 1 , a 2 , a 3 , … a n ; будем переставлять эти элементы всевозможными способами, оставляя без изменения число элементов и меняя только порядок их расположения. Обозначим общее число полученных таким образом перестановок P(n). P - первая буква французского слова permutation - перестановка.
Составив таблицу перестановок для n элементов и применив (n - 1) раз правило произведения, получим число всех возможных перестановок:
P(n) = n (n -1) (n - 2) … 3 2 1 = n!
Такие перестановки называются перестановками без повторений (один и тот же элемент не может повториться в комбинации, все элементы различны).
Задача: шесть человек могут в разном порядке сесть за круглый стол, сколько существует способов разместить эти шесть человек за столом?
Решение: т.к. все люди различны и их комбинации различаются только порядком следования, то мы имеем перестановки без повторений. Определим их число:
Р(6) = 6! = 1 2 3 4 5 6 = 720.
Перестановки с повторениями
Рассматривая различные перестановки, мы предполагали, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам.
Если среди n элементов есть n 1 элементов одного вида, n 2 элементов другого вида и т.д., n k элементов к-го вида, то имеем перестановки с повторениями, их число:
Где n 1 +…+n k = n.
Задача: сколько различных «слов» можно составить из букв слова ДЕД, МАТЕМАТИКА.
Решение: имеем перестановки с повторениями.
А) ДЕД n=3, k=2, n 1 =2, n 2 =1
P 3 (2, 1) = 3!/(2! 1!) = 6 / 2 = 3;
Б) МАТЕМАТИКА n=10, k=6, n 1 =2, n 2 =3, n 3 =2, n 4 =n 5 =n 6 =1
P 10 (2,3,2,1,1,1)=10!/(2! 3! 2!)=2 4 5 6 7 9 10 = 134 400.
Размещения
Размещения без повторений.
Размещениями называют комбинации, составленные из n данных элементов по k элементов (k<=n, k>0), которые отличаются либо составом элементов, либо порядком расположения элементов. Обозначаются размещения A n k . А - первая буква французского слова arrangement , что в переводе означает "размещение", "приведение в порядок". Число всех возможных размещений находится по формуле:
Задача: расписание одного дня состоит из двух пар. Определить число вариантов расписания при выборе из пяти дисциплин, если не может быть одинаковых пар.
Решение: имеем размещения без повторений из пяти элементов по два, из число: .
Размещения с повторениями.
Пусть существуют n различных элементов. Выберем из них m штук, действуя по следующему принципу: возьмем любой элемент, но не будем устанавливать его в какой-либо ряд, а просто запишем под номером 1 его название, сам же элемент вернем к остальным элементам. Затем опять из всех n элементов выберем один, запишем его название под номером 2 и снова вернем элемент обратно. Будем выполнять эти операции, пока не получим m названий. Размещения с повторениями вычисляются по формуле:
Задача: сколько четырехзначных номеров можно составить из 10 цифр?
Решение: имеем размещения с повторениями из 10 элементов по 4, их число: .
Сочетания
Сочетания без повторений.
Сочетаниями называют комбинации, составленные из n различных элементов по k (k =< n) элементов, которые отличаются хотя бы одним элементом. Сочетания обозначаются: C n k C - первая буква французского слова combinasion - сочетание.
Составим из n элементов всевозможные сочетания по k элементов в каждом. Их будет C n k . Внутри каждого сочетания, состоящего из k элементов, образуем всевозможные комбинации, учитывающие порядок следования в них элементов. Таких комбинаций будет P k , т.к. мы в нашем сочетании образовываем перестановки. Всего различных комбинаций из n элементов по k в каждой, отличающихся друг от друга либо составом (элементами), либо порядком их следования, будет C n k P k . Но такие комбинации называются размещениями. Таким образом, A n k = C n k P k , тогда:
Задача: в шахматном турнире участвует 7 человек; сколько партий будет сыграно, если между любыми двумя участниками должна быть сыграна партия?
Решение: имеем сочетания без повторений из 7 элементов по 2; их число: .
Сочетания с повторениями.
Если в сочетаниях некоторые элементы (или все) могут оказаться одинаковыми, то такие сочетания называются сочетаниями с повторениями. Их число определяется по формуле: .
Задача: сколько наборов из 7 пирожных можно составить, если в продаже имеется 4 сорта пирожных?
Решение: имеем сочетания с повторениями из четырех по 7 по, их число: .
3. Графы.. 2
3.1. Основные понятия. 2
3.1.1. История теории графов. 2
3.1.2. Определения. 3
3.1.3. Смежности и инцидентность. 4
3.1.4. Изоморфизм графов. 5
3.2. Представление графов в ЭВМ.. 6
3.2.1. Требования к представлению графов. 6
3.2.2. Матрица смежности. 7
3.2.3. Матрица инциденций. 7
3.3. Геометрическая реализация графов. 8
3.4. Маршруты, цепи, циклы.. 8
3.4.1. Определения. 8
3.4.2. Эйлеровы графы.. 9
3.4.3. Гамильтоновы графы.. 10
3.5. Заключение. 12
Графы
Среди дисциплин и методов дискретной математики теория графов и особенно алгоритмы на графах находят наиболее широкое применение в программировании. Дело в том, что теория графов предоставляет очень удобный язык для описания программных (да и многих других) моделей.
Этот тезис можно пояснить следующей аналогией. Понятие отношения также можно полностью выразить через понятие множества. Однако независимое определение понятия отношения удобнее - введение специальных терминов и обозначений упрощает изложение теории и делает ее более понятной.
То же относится и к теории графов. Стройная система специальных терминов и обозначений теории графов позволяют просто и доступно описывать сложные и тонкие вещи.
Особенно важно наличие наглядной графической интерпретации понятия графа. Само название «граф» подразумевает наличие графической интерпретации. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказательства и сложные формулы.
Основные понятия
История теории графов
Теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.
1. Задача о Кенигсбергских мостах. Обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку (рис. 3.1). Эта задача была решена Эйлером в 1736 году.
Рис. 3.1. Иллюстрация к задаче о Кенигсбергских мостах
2. Задача о трех домах и трех колодцах. Имеется три дома и три колодца. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 3.2). Эта задача была решена Куратовским в 1930 году.
Рис. 3.2. Иллюстрация к задаче о трех домах и трех колодцах
Предметом первых задач теории графов были различные конфигурации, состоящие из точек и соединяющих их линий. При этом несущественно: являются ли эти линии прямыми или кривыми, длинными или короткими, тонкими или толстыми; важно только то, какие точки они соединяют. Т.о. граф – это абстрактное математическое понятие.
Определения
Графом G(V,E) называется совокупность двух множеств - непустого множества V (множества вершин ) и множества Е неупорядоченных пар различных элементов множества V (Е - множество ребер ).
G(V,E): , E VxV.
Число вершин графа G обозначим р, а число ребер – q.
р(G) = |V| q(G) = |E|.
Часто рассматриваются следующие родственные графам объекты.
1. Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (или орграфом ). В этом случае элементы множества V называются узлами, а элементы множества - дугами (G(V, )).
2. Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей , а граф называется графом с петлями (или псевдографом).
3. Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами , а граф называется мультиграфом .
Обычно граф изображают диаграммой : вершины - точками (или кружками), ребра - линиями.
Рис. 3.4. Ориентированный граф с петлей и кратными ребрами.
3. . , т.о.
Рис. 3.5. Неориентированный граф с петлей.
Смежность и инцидентность
Пусть v 1 , v 2 - вершины, е = (v 1 , v 2) - соединяющее их ребро. Тогда вершина v 1 и ребро е инцидентны , вершина v 2 и ребро е также инцидентны. Два ребра, инцидентные одной вершине, называются смежными ; две вершины, инцидентные одному ребру, также называются смежными.
Степенью вершины v графа G(V,E) называется число ребер, инцидентных данной вершине. Обозначение: .
Вершина, имеющая степень 0 называется изолированной, имеющая степень 1 – висячей.
Пример. Для графа, изображенного на рис. 3.5: вершина 3 – изолированная, вершины 1 и 4 - висячие.
Пример. Для графа, изображенного на рис. 3.3.
Ребро e 1 инцидентно вершинам v 1 и v 2 . Вершина v 1 инцидентна ребрам e 1 и e 2 . Ребра e 1 и e 2 – смежны. Вершины v 1 и v 2 – смежны.
P(G)=3, q(G)=5.
Т.о. можно заметить, что .
Теорема Эйлера : .
Доказательство данной теоремы вытекает из того, что каждое ребро дает двойной вклад в сумму степеней вершин.
Изоморфизм графов
Говорят, что два графа G 1 (V 1 ,E 1) и G 2 (V 2 ,E 2) изоморфны (обозначается G 1 ~ G 2), если существует биекция h: V 1 V 2 , сохраняющая смежность.
Графы рассматриваются с точностью до изоморфизма.
Три внешне различные диаграммы, приведенные на рис. 3.6, являются диаграммами одного и того же графа К 3,3 .
Рис. 3.6. Диаграммы изоморфных графов
Числовая характеристика, одинаковая для всех изоморфных графов, называется инвариантом графа . Так, p(G) и q(G) - инварианты графа G.
Не известно никакого набора инвариантов, определяющих граф с точностью до изоморфизма.
Рис. 3.8. Диаграммы неизоморфных графов с совпадающими инвариантами
Представление графов в ЭВМ
Следует подчеркнуть, что конструирование структур данных для представления в программе объектов математической модели - это основа искусства практического программирования. Мы приводим два различных базовых представления графов.
Выбор наилучшего представления определяется требованиями конкретной задачи. Более того, при решении конкретных задач используются, как правило, некоторые комбинации или модификации указанных представлений, общее число которых необозримо. Но все они, так или иначе, основаны на тех базовых идеях, которые описаны в этом разделе.
Требования к представлению графов
Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами.
Представление выбирается, исходя из потребностей конкретной задачи. Далее приведены два из наиболее часто используемых представления.
Указанные представления пригодны для графов и орграфов, а после некоторой модификации также и для псевдографов, мультиграфов.
Представления иллюстрируются на конкретных примерах графа G и орграфа D, диаграммы которых представлены на рис. 7.10.
Рис. 3.9. Диаграммы графа (слева) и орграфа (справа), используемых в качестве примеров
Матрица смежности
Представление графа с помощью квадратной булевской матрицы
отражающей смежность вершин, называется матрицей смежности, где
Матрица инциденций
Представление графа с помощью матрицы Н: array of 0..1 (для орграфов Н: array of -1..1), отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа:
а для ориентированного графа
