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

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

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

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

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

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

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

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

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

Итого : 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 человека. Сколькими способами можно выбрать старосту и его заместителя?

Задача о «размещении» должностей в коллективе встречается очень часто и является самым настоящим баяном. Краткое решение и ответ в конце урока.

Основные правила комбинаторики.

Комбинаторика - это раздел математики, изучающий способы расположения объектов в соответствии со специальными правилами и методы подсчета числа всех возможных способов. Правило умножения. Если некоторый выбор A можно осуществить m способами, а для каждого из них некоторый другой выбор B можно осуществить n способами, то выбор A и B (в указанном порядке) можно осуществить m×n способами. Пример 1. На гору ведут 6 дорог. Сколькими способами можно подняться на гору и спуститься с горы, если подъем и спуск должен быть по разным дорогам? Решение. Дорогу на гору можно выбрать 6-ю способами, так как подъем и спуск должны быть по разным дорогам, то выбрать дорогу для спуска можно 5-ю способами. Тогда по правилу умножения число способов выбора дороги для подъема и спуска равно 6×5=30. Правило сложения. Если некоторый выбор A можно осуществить m способами, а выбор B можно осуществить n способами, то выбор A или B можно осуществить m+n способами. Пример 2. В ящике имеется 6 красных карандашей, 5 синих и 3 простых карандаша. Сколькими способами можно выбрать цветной карандаш? Решение. Цветной карандаш - это красный или синий, следовательно, по правилу сложения число способов выбора цветного карандаша равно 6+5=11. Замечание. Данные правила можно обобщить на большее число выборов. Вопрос. Сколько основных правил комбинаторики существует?

Перестановки.

Определение 1. Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое натуральное число от 1 до n, где n - это число элементов данного множества, причем разным элементам поставлены в соответствие разные числа.

Упорядоченные множества считаются различными, если они отличаются либо своими элементами, либо их порядком. Определение 2. Различные упорядоченные множества, составленные из элементов данного множества, отличающиеся лишь порядком элементов, называются его перестановками. Пример 3. Рассмотрим множество M={a,b,c}. Это множество из трех элементов. Составим его различные перестановки: (a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a). Получили 6 перестановок. P n - число всех перестановок множества из n элементов.

P n =n! (1), где

n!=1·2·3·...·n (читается "н факториал"). Замечание. 0!=1; (n+1)!=n!·(n+1) . Пример 4. Сколько шестизначных чисел, кратных пяти, можно составить из цифр 0,1,2,3,4,5, при условии, что в числе нет одинаковых цифр? Решение. Числа, кратные пяти(делящиеся на пять), оканчиваются либо на 0, либо на 5. Если последняя цифра числа 0, то остальные цифры можно располагать в любом порядке, получим перестановки из пяти элементов, их P 5 =5!=120. Если на конце 5, то остальные можно расположить P 5 =120 способами, но среди них не подходят те, которые начинаются на 0, так как это будут не шестизначные числа. а пятизначные, данных чисел P 4 =4!=24.Тогда требуемых чисел будет 120+120-24=216.

Вопрос. Сколько существует перестановок из шести элементов?

Ваш ответ : 720

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

Если взять цифры 1, 2, 3, 4, то из них можно составить 24 перестановки. Но если взять четыре цифры 1, 1, 2, 2, то можно получить только следующие различные перестановки: (1,1,2,2),(1,2,1,2),(1,2,2,1),((2,2,1,1),(2,1,2,1),(2,1,1,2), то есть шесть перестановок, их в 4 раза меньше, чем перестановок из четырех различных чисел, так как перестановки, в которых меняются местами одинаковые числа - это не новые перестановки, их 2!·2!=4. Рассмотрим задачу в общем виде:пусть имеется множество из элементов, в котором элементывстречаютсяраз, элементывстречаютсяраз,..., элементывстречаютсяраз, причем.

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

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

Сочетания.

Пусть некоторое множество содержит n элементов.

Определение 4. Всякое m- элементное подмножество n- элементного множества называется сочетанием из n элементов по m. - число всех сочетаний.

(3)

Пример 5. Для соревнований из 30 спортсменов надо выбрать трех человек. Сколькими способами это можно сделать? Решение. Команда из 3 спортсменов - это подмножество из трех элементов, то есть сочетание из 30 по 3, поэтому количество способов выбора таких команд вычисляется по формуле (3): .

Свойства сочетаний.

1. 2.. Из данных свойств следует, что, тогда, далее,,и так далее. Можно расположить эти числа в виде таблицы:

.....................................................

.......................

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

Определение 5. Выражение a+b называется биномом.

Формула (4) называется биномиальной формулой Ньютона, а коэффициенты называются биномиальными коэффициентами. Из данной формулы вытекает следующее свойство числа сочетаний

Вопрос. .

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

Пусть имеется множество, содержащее n видов элементов, поэтому есть взять какое-то подмножество этого множества, то в нем могут быть одинаковые элементы. Определение 6. Сочетание с повторениями - это m- элементное подмножество множества, содержащего n видов элементов, в котором элементы повторяются. - число всех сочетаний с повторениями из n по m. Состав m- элементного подмножества имеет вид, где. Заменяя каждое из чиселсоответствующим количеством единиц и разделяя единицы нулями, получаем набор, состоящий из m единиц и n-1 нулей. Каждому составу отвечает только одна запись из нулей и единиц, а каждая запись задает только один состав, следовательно, число различных составов равно числу перестановок с повторениями из n-1 нулей и m единиц. Получаем формулу для вычисления всех сочетаний с повторениями.

(5)

Пример 6. В кондитерском магазине продаются пирожные четырех видов: наполеоны, эклеры, песочные и бисквитные. Сколькими способами можно купить 7 пирожных? Решение. Любая покупка - это подмножество, в котором могут быть одинаковые элементы, поэтому это сочетание с повторениями. Число всех возможных покупок находим по формуле (5): .Вопрос. В формуле (5) m может быть больше n.

Размещения

Определение 7. Упорядоченное m - элементное подмножество n- элементного множества называется размещением. - число всех размещений из n элементов по m. Число всех размещений из n по m больше числа всех сочетаний из n по m, так как из каждого подмножества из m элементов с помощью перестановок можно получить m! упорядоченных подмножеств, получаем формулу для числа размещений

(6)

Пример 7. В группе 25 человек. Нужно выбрать актив группы: старосту, заместителя старосты и профорга. Сколькими способами это можно сделать? Решение. Актив группы - это упорядоченное подмножество из трех элементов, так как надо выбрать не только трех человек, но и распределить между ними должности, значит актив группы - это размещение, число всех размещений вычисляем по формуле (6): .Вопрос. Во сколько раз число сочетаний из 20 по 4 меньше числа размещений из 20 по 4?

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

Пусть дано множество из n элементов, в котором есть одинаковые элементы, тогда его подмножества тоже могут содержать одинаковые элементы. Определение 8. Упорядоченные m- элементные подмножества n- элементного множества, в которых элементы могут повторяться, называются размещениями с повторениями. - число всех размещений из n по m. В подмножестве из m элементов первый элемент можно выбрать n способами(то есть любой элемент множества) , так как элементы могут повторяться, то второй элемент тоже можно выбрать n способами, аналогично остальные элементы подмножества можно выбрать n способами, если воспользоваться правилом умножения, получим формулу для вычисления числа размещений с повторениями:

Пример 8. В лифт десятиэтажного дома вошли 5 человек. Каждый из них может выйти на любом этаже, начиная со второго. Сколькими способами они могут это сделать? Решение. Так как каждый человек может выйти на любом этаже, начиная со второго, то этажей для выхода 9. Надо выбрать этажи для возможности выхода каждого человека: для первого человека - можно выбрать любой из девяти этажей, аналогично для остальных пассажиров, тогда по формуле (7): способов.Вопрос. Вычислить .

Рассмотрим задачу подсчета числа выборок из данного множества в общем виде. Пусть имеется некоторое множество 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. Сколькими способами это можно сделать?

Ответ :

Перестановка – это комбинация элементов из N разных элементов взятых в определенном порядке. В перестановке важен порядок следования элементов, и в перестановке должны быть задействованы все N элементов.

Задача : Найти все возможные перестановки для последовательности чисел 1, 2, 3.
Существуют следующие перестановки:

1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1

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

Количество перестановок для N различных элементов составляет N! . Действительно:

• на первое место может быть помещен любой из N элементов (всего вариантов N ),
• на вторую позицию может быть помещен любой из оставшихся (N-1) элементов (итого вариантов N·(N-1) ),
• если продолжить данную последовательность для всех N мест, то получим: N·(N-1)·(N-2)· … ·1 , то есть всего N! перестановок.

Рассмотрим задачу получения всех перестановок чисел 1…N (то есть последовательности длины N ), где каждое из чисел входит ровно по 1 разу. Существует множество вариантов порядка получения перестановок. Однако наиболее часто решается задача генерации перестановок в лексикографическом порядке (см. пример выше). При этом все перестановки сортируются сначала по первому числу, затем по второму и т.д. в порядке возрастания. Таким образом, первой будет перестановка 1 2 … N , а последней — N N-1 … 1 .

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

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

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

Реализация на С++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include
using namespace std;

{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int *a, int n)
{
int j = n - 2;
while (j != -1 && a[j] >= a) j--;
if (j == -1)
return false; // больше перестановок нет
int k = n - 1;
while (a[j] >= a[k]) k--;
swap(a, j, k);
int l = j + 1, r = n - 1;
while (l swap(a, l++, r--);
return true;
}
void Print(int *a, int n) // вывод перестановки
{
static int num = 1; // номер перестановки
cout.width(3);
cout << num++ << ": " ;
for (int i = 0; i < n; i++)
cout << a[i] << " " ;
cout << endl;
}
int main()
{
int n, *a;
cout << "N = " ;
cin >> n;
a = new int [n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
Print(a, n);
while (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return 0;
}

Результат выполнения

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

Особого внимания заслуживает задача генерации перестановок N элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов n 1 , n 2 ... n k , где элемент n 1 повторяется r 1 раз, n 2 повторяется r 2 раз и т.д. При этом n 1 +n 2 +...+n k =N . Если мы будем считать все n 1 +n 2 +...+n k элементов перестановки с повторениями различными, то всего различных вариантов перестановок (n 1 +n 2 +...+n k)! . Однако среди этих перестановок не все различны. В самом деле, все r 1 элементов n 1 мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы n 2 , n 3 и т. д. В итоге имеем r 1 ! вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов n 1 . Таким образом, всякая перестановка может быть записана r 1 !·r 2 !·...·r k ! способами. Следовательно, число различных перестановок с повторениями равно

Для генерации перестановок с повторениями можно использовать алгоритм генерации перестановок без повторений, приведенный выше. Введем повторяющийся элемент в массив a. Ниже приведен код программы для генерации перестановок с повторениями (изменен только код функции main() ).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include
using namespace std;
void swap(int *a, int i, int j)
{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int *a, int n)
{
int j = n - 2;
while (j != -1 && a[j] >= a) j--;
if (j == -1)
return false; // больше перестановок нет
int k = n - 1;
while (a[j] >= a[k]) k--;
swap(a, j, k);
int l = j + 1, r = n - 1; // сортируем оставшуюся часть последовательности
while (l swap(a, l++, r--);
return true;
}
void Print(int *a, int n) // вывод перестановки
{
static int num = 1; // номер перестановки
cout.width(3); // ширина поля вывода номера перестановки
cout << num++ << ": " ;
for (int i = 0; i < n; i++)
cout << a[i] << " " ;
cout << endl;
}
int main()
{
int n, *a;
cout << "N = " ;
cin >> n;
a = new int [n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
a = 1; // повторяющийся элемент
Print(a, n);
while (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return 0;
}

Результат работы приведенного выше алгоритма:

Рассмотрим множество А = {а1, а2,..., аn}, содержащее n различных элементов, которое будем называть n-множеством
или генеральной совокупностью объема n. Из n-множества можно образовать его части (подмножества).
Определение. Подмножество, состоящее из m элементов n-множества, называют m-подмножеством n-множества или со-
единением из n элементов по m, или выборкой объема m из генеральной совокупности объема n.
Возможны два способа выбора:

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

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

Какие выборки одного и того же объема считать различными и какие одинаковыми, зависит от правил выбора соедине-
ния (подмножества, выборки).
Два соединения могут отличаться либо 1) составом, если они содержат хотя бы по одному различному элементу, либо
2) порядком входящих элементов.
В зависимости от правил выбора соединения делят на три типа: размещения, перестановки, сочетания. В зависимости от
способа выбора (без возвращения или с возвращением) каждый тип соединения может быть без повторений или с повторениями.

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

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно
выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?
Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой
можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов,
среди которых есть одинаковые?

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

На языке теории множеств это звучит следующим образом: размещения из n элементов по m – это упорядоченное
m-подмножество n-множества (упорядоченная m-выборка из генеральной совокупности объема n). Термин «упорядоченная»
означает, что порядок следования элементов в выборке существенен: выборки с одними и теми же элементами, но с разным
порядком их следования различны.

Задача . Пусть имеется множество, содержащее 4 буквы:
{А, B, C, D}. Записать все возможные размещения из 4 указанных букв по две:

а) без повторений;

б) с повторениями.

Решение.

а) Таких размещений 12: (АВ), (AC), (АD), (ВС),(ВD), (BA), (CA), (CB), (СD), (DА), (DВ), (DС). Заметим, что
размещения отличаются порядком входящих в них элементов и их составом. Размещения АВ и ВА содержат одинаковые буквы,
но порядок их расположения различен.
б) Таких размещений 16. К приведенным для случая (а)
размещениям добавляются размещения из одинаковых элементов (АА), (BB), (CC), (DD).

Задача . Пусть имеется множество, содержащее 2 буквы:{A, B}. Записать все возможные размещения с повторениями из
4-х букв.
Решение. Таких размещений 16: (AAAA), (BBBB), (AAAB),(AABA), (ABAA), (BAAA), (AABB), (ABAB), (BABA), (BBAA), (ABBA),
(BAAB), (BBBA), (BBAB), (BABB), (ABBB).

Теорема 3. 3.1 Число различных размещений без повторений из n элементов по m равно

для выборки без возвращения.

3.2 Число размещений с повторениями из n элементов по m равноm (2) для выборки с возвращением.

Доказательство. Для доказательства воспользуемся пра- вилом умножения.

Рассмотрим выборки без возвращения. Для выбора первого элемента имеется n возможностей, второго – (n – 1)

(перед вторым выбором в генеральной совокупности ос- талось (n –1) элементов),..., при m-ом выборе (n – m + 1) воз- можностей.

Таким образом, по правилу умножения

Запишем выражение в более удобном виде, умножив и разделив его на (m – n)!

Считается, что 0! = 1, что позволяет использовать эту формулу для случая m = n.

Рассмотрим выборки с возвращением . Для выбора первого элемента имеется n возможностей, второго – тоже n (перед выбо-
ром очередного элемента предыдущий выбранный элемент зафиксирован и возвращен в генеральную совокупность), при m-м вы-
боре тоже n возможностей. Таким образом .

Задача . В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии.

Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?
Решение . В данной задаче генеральной совокупностью являются 12 страниц газеты, и выборкой без возвращения 4 выбранные из них страницы для фотографий. В данной задаче важно не только то, какие выбраны страницы, но и в каком порядке (для расположения фотографий). Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

Задача . У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих
штампов нанести на все книги пятизначные номера – составить каталог. Сколько различных пятизначных номеров может со-
ставить мальчик?
Решение. Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр {1, 3, 7}. Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:

3. Перестановки без повторений
Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно
выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?
Определение. Размещения, в которых участвуют все n элементов генеральной совокупности, называются перестанов-
ками без повторений из n элементов. Перестановки состоят из одних и тех же элементов, но отличаются между собой порядком.

Задача . Пусть имеется множество букв {A, B, C}. Записать все возможные перестановки.
Решение. Этому множеству букв соответствует 6 перестановок: (АВС), (ACB), (BAC), (BCA), (CBA), (CAB).

Теорема . Число перестановок n различных элементов равно n!, т. е. Рn = n!

Доказательство. Так как перестановки являются частным случаем размещений, то при n = m получаем

Замечание. При больших n для подсчета факториала исполь- зуют таблицу логарифмов факториалов либо приближенную формулу Стирлинга

Задача . Сколько можно составить четырехбуквенных «слов» из букв слова «брак»?

Решение . Генеральной совокупностью являются 4 буквы слова «брак» {б, р, а, к}.

Число «слов» определяется перестановками этих 4 букв, т. е. Р4 = 4! = 1 x 2 x 3 x 4 = 24.

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

Решение . В исходной генеральной совокупности – 9 разных книг.

Тогда для остальных 6 книг существует Р6 = 6! = 720 перестановок.

Однако четыре определенные книги можно переставить между собой Р4 = 4! = 24 способами.

По правилу умножения имеем Р6 x Р4 = 720 x 24 = 17280.

4. Перестановки с повторениями
Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на
n различных местах, если среди n предметов имеются k различных типов (k < n), т. е. есть одинаковые предметы.

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

а1 повторяется n1 раз,
а2 повторяется n2 раз,
. . . . . . . . . . . . . . . . . . .
аn повторяется nk раз
n1 + n2 + ... + nk = n
и которые отличаются друг от друга только порядком расположения различных элементов.

Теорема. Число перестановок с повторениями

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

Задача .

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

Решение. Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв.

Следовательно, число перестановок с повторениями равно

5. Сочетания без повторений
Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из п различных предметов?
Определение. Сочетаниями из n различных элементов по m называются соединения из n элементов по m (m <=n), которые
отличаются друг от друга только составом элементов.

Задача. Пусть имеется множество, содержащее 4 буквы {A, B, C, D}. Запишем все возможные сочетания из указанных
букв по 3.
Решение. Таких сочетаний 4: ABC, ACD, ABD, BCD.
Здесь в число сочетаний не включены, например, АСВ,ВСА, так как они не отличаются по составу от последовательно-
сти букв АВС, потому что перестановка элементов нового сочетания не дает.

Теорема. Число сочетаний из n элементов по m равно

Доказательство.

Вспомним, что и сочетания, и размещения из n элементов по m – это выборки объема m из генеральной совокупности объема n и разница между ними в том, что в случае размещений важен и состав, и порядок элементов, тогда как в случае сочетаний важен только состав элементов. Пусть имеется какое-то одно сочетание. Для того, чтобы образовать все размещения с такими же элементами, нужно осуществить всевозможные перестановки элементов этого сочетания. Поскольку в сочетании m элементов, то существует m! перестановок. Следовательно, одному сочетанию, состоящему из m элементов, соответствует m! размещений с этими элементами. Поэтому

Числа называются биномиальными коэффициентами: они являются коэффициентами в разложении бинома Ньютона

Задача . Необходимо выбрать в подарок 4 из 10 имеющих- ся различных книг. Сколькими способами можно это сделать?

Решение . Генеральной совокупностью является 10 раз- личных книг. Из них нужно выбрать 4, причем порядок выбора книг не играет роли. Нужно найти число сочетаний из 10 элементов по

Задача . Имеется 10 белых и 5 черных шаров. Сколькими способами можно выбрать 7 шаров, чтобы среди них были 3 черных?

Решение . Имеем 15 шаров: 10 белых и 5 черных. Нужно выбрать 7 шаров: 4 белых и 3 черных.

Разобьем 15 шаров на 2 генеральные совокупности:

1) 10 белых шаров;

2) 5 черных шаров.

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

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

Способами.

Тогда по правилу умножения искомое число способов равно .

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

Задача . Десять команд участвуют в розыгрыше первенства по футболу, лучшие из которых занимают 1-е, 2-е и 3-е место.

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

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

Решение . Имеется генеральная совокупность объема 10 команд. Из нее будем выбирать 5 команд в 2 этапа:

1) сначала на первые 3 места из 10 с учетом состава и порядка команд;

2) затем на последние 2 места из оставшихся 7 с учетом только состава (порядок выбывших команд не важен).

Первые 3 места могут быть распределены способами.

Число способов исключить 2 команды из оставшихся 7 равно .

Согласно правилу умножения получаем, что число разных результатов неравенства равно 0.

Задача .

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

Решение .

I способ. Имеется генеральная совокупность объема 11 учащихся. Преподаватель может не опросить ни одного из 11 учащихся, что является одним из вариантов. Этому случаю соответствует . Преподаватель может опросить только одного из учащихся, таких вариантов .

Если преподаватель опросит двух учащихся, то число вариантов опроса . Для опроса трех учащихся существует вариантов и т. д.

Наконец, могут быть опрошены все учащиеся. Число вариантов в этом случае .

Число всех возможных вариантов опроса можно найти по пра- вилу сложения

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

II способ. Имеется генеральная совокупность, состоящая из 2 элементов:

{а, в}, где а – ученик опрошен, в – ученик не опрошен на данном занятии.

Опыт состоит в 11-кратном выборе с возвращением одного из элементов этого множества – каждый из 11 учеников либо опрошен, либо не опрошен.

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

но и в каком порядке (т. е. какой именно ученик опрошен или нет).

Число способов такого выбора определяется числом размещений с повторениями из 2 элементов по 11; .

6. Сочетания с повторениями
Рассмотрим задачу о числе сочетаний с повторениями:
имеется по r одинаковых предметов каждого из n различных типов;

сколькими способами можно выбрать m (m <= r) из этих (n x r) предметов?

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

Задача . Имеются 2 буквы А, 2 буквы В, 2 буквы С. Сколькими способами можно выбрать две из этих шести букв?
Решение. Существует 6 способов выбора 2 букв из 6 с повторениями: (АА), (AB), (AC), (BC), (BB), (CC). Порядок следо-
вания букв не учитывается.

Теорема . Число сочетаний с повторениями равно

Доказательство. Пусть имеются предметы n различных типов. Сколько соединений по m элементов можно из них сделать, если не принимать во внимание порядок элементов. Расположим в каждом сочетании элементы по типам (сначала все элементы 1-го типа, потом 2-го и т. д.). После этого перенумеруем все элементы в сочетании, но к номерам элементов второ- го типа прибавим 1, третьего типа – 2 и т. д. Тогда из каждого сочетания с повторениями получится сочетание без повторений, состоящее из чисел 1, 2,..., n + m – 1, причем в каждое сочетание входит m элементов.

Отсюда следует, что

Задача . В технической библиотеке имеются книги по ма- тематике, физике, химии и т. д., всего по 16 разделам науки.

Поступили очередные 4 заказа на литературу. Сколько сущест- вует вариантов такого заказа?

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

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

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

7. Комбинаторика разбиений

Рассмотрим в этом классе задач две следующие задачи:

1. Даны n различных предметов и k различных групп. Сколькими способами можно распределить n различных предметов по k различным группам, если допускаются пустые группы. Ниже покажем, что число способов равно k^n .

2. Даны n различных предметов и k различных групп. Сколькими способами можно распределить n различных пред- метов по k группам, если в первой группе n1 предметов, во второй – n2 , в k-й – nk , где n1 + n2 +... + nk = n . Ниже покажем, что число способов равно

Рассмотрим решение первой задачи. Пусть генеральной совокупностью будет k различных групп {1, 2,..., k}. Можно считать, что опыт состоит в n-кратном выборе с возвращением номера группы для каждого предмета. Заметим, что поскольку предметы разные, то важно не только, какие группы выбираются для предметов, но и в каком порядке выбираются эти группы. Таким образом, число способов раз- бить n различных предметов на k групп определяется числом размещений с повторениями и k элементов по n:

Рассмотрим решение второй задачи.

Разбиение n предметов по k группам можно выполнить следующим образом. Сначала положим все n предметов в ряд. После этого возьмем первые n1 предметов и поместим их в первую группу, вторые n2 предмета – во вторую группу, ..., последние nk предметов в k-ю группу. Ясно, что меняя положение предметов в ряду, можно получить всевозможные разбиения предметов. Так как число перестановок из n элементов равно n!, то число расположения предметов в ряд равно n! При этом заметим, что любая перестановка первых n1 предметов ничего не меняет, так же как и вторых n2, ..., и последних nk. В силу правила произведения получим n1!n2!...nk! перестановок предметов, не меняющих результата раздела. Таким образом, число способов разбиения на группы равно

Формула совпадает с формулой для числа перестановок с повторениями. К этому же результату можно прийти иначе. Первые n1 предметов выбираем из n предметов. Так как порядок выбранных предметов безразличен, то имеет выборов. После этого следующие n2 предмета выбираем из оставшихся n – n1. Это можно сделать способами, и т. д.

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

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

Задача. 7 одинаковых шариков случайным образом рас- сыпаются по 4 лункам (в одну лунку может поместиться любое число шаров). Сколько существует различных способов распре- деления 7 шариков по 4 лункам?

Решение. Мы имеем 7 шариков, которые распределяем по 4 лункам (лунки могут быть пустые), т. е. это соответствует первой задаче о разбиениях, число способов равно 4^7 = 16348

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

Решение. Это задача о разделе 28 костей между 4 игрока- ми по 7 костей. Используя полученную выше формулу для числа способов такого раздела (задача 2), имеем

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

наторные понятия присутствуют в ней в неявной форме. Поэтому после усвоения содержания задачи нужно ее «перевести»
на математический язык.
Для этого необходимо выяснить,
1) что является генеральной совокупностью - она всегда будет присутствовать в задаче, т. е. комбинаторные задачи свя-
заны с выбором объектов, а этот выбор из чего-то (генеральной совокупности) производится; каков объем генеральной сово-
купности;
2) одна или несколько генеральных совокупностей;
3) что является выборкой и каков объем выборки;
4) правила выбора: допустимы или нет повторы, важен ли порядок выбираемых элементов, возможно ли изменение состава.
После этого полезно для себя переформулировать задачу на языке генеральных совокупностей и выборок. В зависимости
от ситуации выбрать нужную формулу (см. таблицу). Иногда в более сложных задачах приходится использовать совместно не-
сколько формул.

В заключение приведем основные свойства чисел .

Прежде всего, построим таблицу таких чисел, используя формулу (3.11).

Таблица чисел имеет треугольную форму и называется треугольником Паскаля по имени математика Блеза Паскаля (1623-1662). Анализируя треугольник Паскаля, легко видеть основные свойства чисел .

Свойства 1 – 2 вытекают из определения сочетания как подмножества, содержащего m элементов множества, имеющего n элементов.

Свойства 3 – 5 доказываются методом математической индукции.

В силу свойства 4 треугольник Паскаля легко продолжить вниз на любое число шагов.

рис 3.2 схема определения вида расстановок и выбора формул