Комбинаторика - это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиальновозможное количество различных вариантов развития событий.
Основная формула комбинаторики
Пусть имеется k групп элементов, причем i-я группа состоит из n i элементов. Выберем по одному элементу из каждой группы. Тогда общее число N способов, которыми можно произвести такой выбор, определяется соотношением N=n 1 *n 2 *n 3 *...*n k .
Пример 1. Поясним это правило на простом примере. Пусть имеется две группы элементов, причем первая группа состоит из n 1 элементов, а вторая - из n 2 элементов. Сколько различных пар элементов можно составить из этих двух групп, таким образом, чтобы в паре было по одному элементу от каждой группы? Допустим, мы взяли первый элемент из первой группы и, не меняя его, перебрали все возможные пары, меняя только элементы из второй группы. Таких пар для этого элемента можно составить n 2 . Затем мы берем второй элемент из первой группы и также составляем для него все возможные пары. Таких пар тоже будет n 2 . Так как в первой группе всего n 1 элемент, всего возможных вариантов будет n 1 *n 2 .
Пример 2.
Сколько
трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если
цифры могут повторяться?
Решение:
n 1 =6
(т.к. в качестве первой цифры можно взять любую цифру из 1, 2, 3, 4, 5, 6), n 2 =7
(т.к. в качестве второй цифры можно взять любую цифру из 0, 1, 2, 3, 4, 5,
6), n 3 =4 (т.к. в качестве третьей цифры можно взять любую цифру из 0, 2, 4,
6).
Итак, N=n 1 *n 2 *n 3 =6*7*4=168.
В том случае, когда все группы состоят из одинакового числа элементов, т.е. n 1 =n 2 =...n k =n можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно n k . Такой способ выбора в комбинаторики носит название выборки с возвращением.
Пример 3.
Сколько всех четырехзначных чисел
можно составить из цифр 1, 5, 6, 7, 8?
Решение.
Для каждого разряда
четырехзначного числа имеется пять возможностей, значит N=5*5*5*5=5 4 =625.
Рассмотрим множество, состоящие из n элементов. Это множество в комбинаторике называется генеральной совокупностью .
Число размещений из n элементов по m
Определение 1. Размещением из n элементов по m в комбинаторике называется любой упорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.
Пример 4. Различными размещениями из трех элементов {1, 2, 3} по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 2). Размещения могут отличаться друг от друга как элементами, так и их порядком.
Число размещений в комбинаторике обозначается A n m и вычисляется по формуле:
Замечание: n!=1*2*3*...*n (читается: "эн факториал"), кроме того полагают, что 0!=1.
Пример 5
. Сколько существует двузначных
чисел, в которых цифра десятков и цифра единиц различные
и нечетные?
Решение:
т.к. нечетных цифр
пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на
две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет:
Определение 2. Сочетанием из n элементов по m в комбинаторике называется любой неупорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.
Пример 6 . Для множества {1, 2, 3}сочетаниями являются {1, 2}, {1, 3}, {2, 3}.
Число сочетаний из n элементов по m
Число сочетаний обозначается C n m и вычисляется по формуле:
Пример 7. Сколькими способами читатель может выбрать две книжки из шести имеющихся?
Решение: Число способов равно числу сочетаний из шести книжек по две, т.е. равно:
Перестановки из n элементов
Определение 3. Перестановкой из n элементов называется любой упорядоченный набор этих элементов.
Пример 7a. Всевозможными перестановками множества, состоящего из трех элементов {1, 2, 3} являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).
Число различных перестановок из n элементов обозначается P n и вычисляется по формуле P n =n!.
Пример 8. Сколькими способами семь книг разных авторов можно расставить на полке в один ряд?
Решение: эта задача о числе перестановок семи разных книг. Имеется P 7 =7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.
Обсуждение. Мы видим, что число возможных комбинаций можно посчитать по разным правилам (перестановки, сочетания, размещения) причем результат получится различный, т.к. принцип подсчета и сами формулы отличаются. Внимательно посмотрев на определения, можно заметить, что результат зависит от нескольких факторов одновременно.
Во-первых, от того, из какого количества элементов мы можем комбинировать их наборы (насколько велика генеральная совокупность элементов).
Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны.
И последнее, важно знать, является ли для нас существенным порядок элементов в наборе. Поясним последний фактор на следующем примере.
Пример 9.
На родительском собрании
присутствует 20 человек. Сколько существует различных вариантов состава
родительского комитета, если в него должны войти 5 человек?
Решение:
В этом примере нас
не интересует порядок фамилий в списке комитета. Если в результате в его
составе окажутся одни и те же люди, то по смыслу для нас это один и тот же
вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний
из 20 элементов по 5.
Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантов перестановок , которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5.
Задачи для самопроверки
1. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5,
6, если цифры могут повторяться?
2. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?
3. В классе десять предметов и пять уроков в день. Сколькими способами можно составить расписание на один день?
4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе 20 человек?
5. Сколькими способами можно разложить восемь различных писем по восьми различным конвертам, если в каждый конверт кладется только одно письмо?
6. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать?
Перестановка – это комбинация элементов из 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
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
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;
}
Результат работы приведенного выше алгоритма:
В комбинаторике изучают вопросы о том, сколько комбинаций определенного типа можно составить из данных предметов (элементов).
Рождение комбинаторики как раздела связано с трудами Б. Паскаля и П. Ферма по теории азартных игр. Большой вклад в развитие комбинаторных методов внесли Г.В. Лейбниц, Я. Бернулли и Л. Эйлер.
Французский философ, писатель, математик и физик Блез Паскаль (1623–1662) рано проявил свои выдающиеся математические способности. Круг математических интересов Паскаля был весьма разнообразен. Паскаль доказал одну
из основных теорем проективной геометрии (теорема Паскаля), сконструировал суммирующую машину (арифмометр Паскаля), дал способ вычисления биномиальных коэффициентов (треугольник Паскаля), впервые точно определил и применил для доказательства метод математической индукции, сделал существенный шаг в развитии анализа бесконечно малых, сыграл важную роль в зарождении теории вероятности. В гидростатике Паскаль установил ее основной закон (закон Паскаля). “Письма к провинциалу” Паскаля явились шедевром французской классической прозы.
Готфрид Вильгельм Лейбниц (1646–1716) — немецкий философ, математик, физик и изобретатель, юрист, историк, языковед. В математике наряду с И. Ньютоном разработал дифференциальное и интегральное исчисление. Важный вклад внес в комбинаторику. С его именем, в частности, связаны теоретико-числовые задачи.
Готфрид Вильгельм Лейбниц имел мало внушительную внешность и поэтому производил впечатление довольно невзрачного человека. Однажды в Париже он зашел в книжную лавку в надежде приобрести книгу своего знакомого философа. На вопрос посетителя об этой книге книготорговец, осмотрев его с головы до ног, насмешливо бросил: “Зачем она вам? Неужели вы способны читать такие книги?” Не успел ученый ответить, как в лавку вошел сам автор книги со словами: “Великому Лейбницу привет и уважение!” Продавец никак не мог взять втолк, что перед ним действительно знаменитый Лейбниц, книги которого пользовались большим спросом среди ученых.
В дальнейшем важную роль будет играть следующая
Лемма. Пусть в множестве элементов, а в множестве — элементов. Тогда число всех различных пар , где будет равно .
Доказательство. Действительно, с одним элементом из множества мы можем составить таких различных пар, а всего в множестве элементов.
Размещения, перестановки, сочетания
Пусть у нас есть множество из трех элементов . Какими способами мы можем выбрать из этих элементов два? .
Определение. Размещениями множества из различных элементов по элементов называются комбинации, которые составлены из данных элементов по > элементов и отличаются либо самими элементами, либо порядком элементов.
Число всех размещений множества из элементов по элементов обозначается через (от начальной буквы французского слова “arrangement”, что означает размещение), где и .
Теорема. Число размещений множества из элементов по элементов равно
Доказательство. Пусть у нас есть элементы . Пусть — возможные размещения. Будем строить эти размещения последовательно. Сначала определим — первый элемент размещения. Из данной совокупности элементов его можно выбрать различными способами. После выбора первого элемента для второго элемента остается способов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:
Пример. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти цветов?
Решение. Искомое число трехполосных флагов:
Определение. Перестановкой множества из элементов называется расположение элементов в определенном порядке.
Так, все различные перестановки множества из трех элементов — это
Число всех перестановок из элементов обозначается (от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле
Пример. Сколькими способами можно расставить ладей на шахматной доске так, чтобы они не били друг друга?
Решение. Искомое число расстановки ладей
По определению!
Определение. Сочетаниями из различных элементов по элементов называются комбинации, которые составлены из данных элементов по элементов и отличаются хотя бы одним элементом (иначе говоря, -элементные подмножества данного множества из элементов).
Как видим, в сочетаниях в отличие от размещений не учитывается порядок элементов. Число всех сочетаний из элементов по элементов в каждом обозначается (от начальной буквы французского слова “combinasion”, что значит “сочетание”).
Числа
Все сочетания из множества по два — .
Свойства чисел {\sf C}_n^k
Действительно, каждому -элементному подмножеству данного -элементного множества соответствует одно и только одно -элементное подмножество того же множества.
Действительно, мы можем выбирать подмножества из элементов следующим образом: фиксируем один элемент; число -элементных подмножеств, содержащих этот элемент, равно ; число -элементных подмножеств, не содержащих этот элемент, равно .
Треугольник Паскаля
В этом треугольнике крайние числа в каждой строке равны 1, а каждое не крайнее число равно сумме двух чисел предыдущей строки, стоящих над ним. Таким образом, этот треугольник позволяет вычислять числа .
Теорема.
Доказательство.
Рассмотрим множество из элементов и решим двумя способами следующую задачу: сколько можно составить последовательностей из элементов данного
множества, в каждой из которых никакой элемент не встречается дважды?
1 способ. Выбираем первый член последовательности, затем второй, третий и т.д. член
2 способ. Выберем сначала элементов из данного множества, а затем расположим их в некотором порядке
Домножим числитель и знаменатель этой дроби на :
Пример. Сколькими способами можно в игре “Спортлото” выбрать 5 номеров из 36?
Искомое число способов
Задачи.
1.
Номера машин состоят из 3 букв русского алфавита (33 буквы) и 4 цифр. Сколько существует различных номеров автомашин?
2.
На рояле 88 клавиш. Сколькими способами можно извлечь последовательно 6 звуков?
3.
Сколько есть шестизначных чисел, делящихся на 5?
4.
Сколькими способами можно разложить 7 разных монет в три кармана?
5.
Сколько можно составить пятизначных чисел, в десятичной записи которых хотя бы один раз встречается цифра 5?
6.
Сколькими способами можно усадить 20 человек за круглым столом, считая способы одинаковыми, если их можно получить один из другого движением по кругу?
7.
Сколько есть пятизначных чисел, делящихся на 5, в записи которых нет одинаковых цифр?
8.
На клетчатой бумаге со стороной клетки 1 см нарисована окружность радиуса 100 см, не проходящая через вершины клеток и не касающаяся сторон клеток. Сколько клеток может пересекать эта окружность?
9.
Сколькими способами можно расставить в ряд числа так, чтобы числа стояли рядом и притом шли в порядке возрастания?
10.
Сколько пятизначных чисел можно составить из цифр , если каждую цифру можно использовать только один раз?
11.
Из слова РОТ перестановкой букв можно получить еще такие слова: ТОР, ОРТ, ОТР, ТРО, РТО. Их называют анаграммами. Сколько анаграмм можно составить из слова ЛОГАРИФМ?
12.
Назовем разбиением
натурального числа представление его в виде суммы натуральных чисел. Вот, например, все разбиения числа :
Разбиения считаются разными, если они отличаются либо числами, либо порядком слагаемых.
Сколько существует различных разбиений числа на слагаемых?
13.
Сколько существует трехзначных чисел с невозрастающим порядком цифр?
14.
Сколько существует четырехзначных чисел с невозрастающим порядком цифр?
15.
Сколькими способами можно рассадить в ряд 17 человек, чтобы и оказались рядом?
16.
девочек и мальчиков рассаживаются произвольным образом в ряду из мест. Сколькими способами можно их рассадить так, чтобы никакие две девочки не сидели рядом?
17.
девочек и мальчиков рассаживаются произвольным образом в ряду из мест. Сколькими способами можно их рассадить так, чтобы все девочки сидели рядом?
Задача
.
Определить количество всех упорядоченных
наборов
длиныr
,
которые можно составить из элементов
множестваX
(
),
если выбор каждого элемента
,
производится из всего множестваX
.
Упорядоченный
набор
– это элемент декартова произведения
,
состоящего изr
одинаковых множителейX
.
По правилу произведения количество
элементов множества
равно
.
Мы вывели формулу
.
Пример . Сколько четырехзначных телефонных номеров можно составить, если использовать все десять цифр?
Здесь
,
и количество телефонных номеров равно
2.1.5. Размещения без повторений
Задача
.
Сколько упорядоченных наборов
можно составить изn
элементов множестваX
,
если все элементы набора различны?
Первый элемент
можно выбратьn
способами. Если первый элемент уже
выбран, то второй элемент
можно выбрать лишь
способами,
а если уже выбран
элемент
,
то элемент
можно
выбрать
способами
(повторение уже выбранного элемента не
допускается). По правилу произведения
получаем
Эта формула
записывается иначе с использованием
обозначения
.
Так как
.
Пример . Сколько может быть различных списков победителей олимпиады (первое, второе, третье место), если участвовало 20 человек?
Здесь
,
искомым является число
2.1.6. Перестановки без повторений
Рассмотрим
частный случай размещения без повторений:
если
,
то в размещении участвуют все элементы
множестваX
,
т.е. выборки имеют одинаковый состав и
отличаются друг от друга только порядком
элементов. Такие выборки называютсяперестановками
. Количество
перестановок изn
элементов обозначают
:
Пример. Сколькими способами можно выстроить очередь в кассу, если хотят получить зарплату шесть человек?
2.1.7. Перестановки с повторениями
Пусть множество
X
состоит изk
различных элементов:
.Перестановкой с повторениями
состава
будем называть упорядоченный набор
длины
,
в котором элемент
встречается
раз
.
Количество таких перестановок обозначается
.
Пример
. Из
букв
запишем перестановку с повторением
состава
.
Ее длина
,
причем букваa
входит 2 раза,b
– 2 раза,c
– один раз. Такой перестановкой будет,
например,
или
.
Выведем формулу
количества перестановок с повторениями.
Занумеруем все одинаковые элементы,
входящие в перестановку, различными
индексами, т.е. вместо перестановки
получим
.
Теперь все элементы перестановки
различны, а количество таких перестановок
равно
.
Первый элемент встречается в выборке
раз. Уберем индексы у первого элемента
(в нашем примере получим перестановку
),
при этом число различных перестановок
уменьшится в
раз, т.к. при изменении порядка одинаковых
элементов наша выборка не изменится.
Уберем индексы у второго элемента –
число перестановок уменьшится в
раз. И так далее, до элемента с номеромk
– число перестановок уменьшится в
раз. Получим формулу
Пример . Сколько различных “слов” можно получить, переставляя буквы слова “передача” ?
В этом слове
буквы “е” и “а” встречаются два раза,
остальные по одному разу. Речь идет о
перестановке с повторением состава
длины.
Количество таких перестановок равно
2.1.8. Сочетания
Задача . Сколько различных множеств изr элементов можно составить из множества, содержащегоn элементов?
Будем составлять
вначале упорядоченные наборы по r
элементов в каждом. Количество таких
наборов (это размещения изn
элементов поr
)
равно
.
Теперь учитываем, что порядок записи
элементов нам безразличен. При этом из
различных размещений, отличающихся
только порядком элементов, получим одно
сочетание. Например, два различных
размещения
и
из двух элементов соответствуют одному
сочетанию
.
Таким образом, число сочетаний
в
раз меньше числа размещений
:
Пример . Количество способов, которыми мы можем выбрать из восьми дворников троих равно
Следует отметить, что комбинаторика является самостоятельным разделом высшей математики (а не частью тервера) и по данной дисциплине написаны увесистые учебники, содержание которых, порой, ничуть не легче абстрактной алгебры. Однако нам будет достаточно небольшой доли теоретических знаний, и в данной статье я постараюсь в доступной форме разобрать основы темы с типовыми комбинаторными задачами. А многие из вас мне помогут;-)
Чем будем заниматься? В узком смысле комбинаторика - это подсчёт различных комбинаций, которые можно составить из некоторого множества дискретных объектов. Под объектами понимаются какие-либо обособленные предметы или живые существа - люди, звери, грибы, растения, насекомые и т.д. При этом комбинаторику совершенно не волнует, что множество состоит из тарелки манной каши, паяльника и болотной лягушки. Принципиально важно, что эти объекты поддаются перечислению - их три (дискретность) и существенно то, что среди них нет одинаковых.
С множеством разобрались, теперь о комбинациях. Самыми распространёнными видами комбинаций являются перестановки объектов, их выборка из множества (сочетание) и распределение (размещение). Давайте прямо сейчас посмотрим, как это происходит:
Перестановки, сочетания и размещения без повторений
Не пугайтесь малопонятных терминов, тем более, некоторые из них действительно не очень удачны. Начнём с хвоста заголовка - что значит «без повторений »? Это значит, что в данном параграфе будут рассматриваться множества, которые состоят из различных объектов. Например, … нет, кашу с паяльником и лягушкой предлагать не буду, лучше что-нибудь повкуснее =) Представьте, что перед вами на столе материализовалось яблоко, груша и банан (при наличии таковых ситуацию можно смоделировать и реально). Выкладываем фрукты слева направо в следующем порядке:
яблоко / груша / банан
Вопрос первый : сколькими способами их можно переставить?
Одна комбинация уже записана выше и с остальными проблем не возникает:
яблоко / банан / груша
груша / яблоко / банан
груша / банан / яблоко
банан / яблоко / груша
банан / груша / яблоко
Итого : 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 человека. Сколькими способами можно выбрать старосту и его заместителя?
Задача о «размещении» должностей в коллективе встречается очень часто и является самым настоящим баяном. Краткое решение и ответ в конце урока.
