Формулы для всех видов соединений в комбинаторике - перестановки и размещения с повторениями и без повторений с примерами

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

План

• 1. Выборки
• 2. Размещения без и с повторениями.
• 3. Перестановки без повторений
• 4. Перестановки с повторениями
• 5. Сочетания без повторений
• 6. Сочетания с повторениями
• 7. Комбинаторика разбиений
• 8. Рекомендации по решению задач по комбинаторике

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

Примерами комбинаторных конфигураций являются:

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

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

Схема решения комбинаторных задач

Открыть на весь экран

1. Выборки

Рассмотрим множество А = {а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) воз- можностей.

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

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

. Считается, что 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 разных книг.

Будем считать выделенные 4 книги за одну.

Тогда для остальных 6 книг (9-4+1 , 1 это новая книга из 4х книг) существует Р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 треугольник Паскаля легко продолжить вниз на любое число шагов.

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

Вау!! 😲 Ты еще не читал? Это зря!

• перестановки , сочетания , размещения , перестановки с повторениями ,
• перестановки , сочетания , размещения , бином ньютона ,