КОМБИНАТОРИКА
Комбинаторика – это раздел математики, который изучает количества комбинаций, подчиненных определенным условиям, которые можно составить из элементов, безразлично какой природы, заданного конечного множества. Занимается различного вида соединениями, которые можно образовать из элементов конечного множества.
Правило суммы и правило произведения
Рассмотрение основных правил комбинаторики начнем с примера.
Пример: В магазине имеется 5 видов коробок конфет и 4 вида коробок печенья. Определите сколькими способами можно составить подарок из одной коробки конфет или одной коробки печенья. Определите сколькими способами можно составить в подарок набор из одной коробки конфет и одной коробки печенья.
Ответ на первый вопрос – 9=5+4, ответ на второй вопрос 20=5*4.
Этот несложный пример иллюстрирует правило суммы и правило произведения. Сформулируем их в общем виде.
Правило суммы. Если объект А можно выбрать n способами, а объект B можно выбрать m способами, то объект А или B можно выбрать n+m способами.
Правило произведения. Если объект А можно выбрать n способами, а объект B можно выбрать m способами, то объект А и B можно выбрать n*m способами.
Примеры:
1. Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы?
n=17, m=13. По правилу суммы n+m=17+13=30 тем.
2. Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото и 10 билетов автомотолотереи. Сколькими способами можно выбрать один билет?
5+ 6+10=21 вариантов.
3. Переплетчик должен переплести 12 различных книг в красный, зеленый или коричневые переплеты. Сколькими способами он может это сделать?
Имеется 12 книг (m) и 3 цвета (n), значит по правилу произведения возможно 12*3=36 вариантов переплета.
4. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?
В таких числах последняя цифра будет такая же, как и первая, а предпоследняя - как и вторая. Третья цифра будет любой. Числа такого вида можно представить в виде XYZYX, где Y и Z - любые цифры, а X - не ноль. Значит, по правилу произведения количество чисел, одинаково читающихся как слева направо, так и справа налево равно 9*10*10=900.
Все вышесказанное относиться к множествам, которые не имеют общих элементов, т.е. в примере с конфетами и печеньем в множестве коробок конфет не могли оказаться коробки с печеньем, а в множестве коробок с печеньем не могли оказаться коробки конфет.
Пересекающиеся множества
Примеры:
В группе 20 человек знают английский и 10 - немецкий, из них 5 знают и английский, и немецкий. Сколько всего человек в группе?
Решим задачу с помощью кругов Эйлера.
Теперь все множество группы разбито на три непересекающихся множества:
А – множество тех, кто изучает только немецкий язык (красная область),
B – множество тех, кто изучает только английский язык (зеленая область),
C – множество тех, кто изучает и немецкий и английский языки (белая область).
Пока нам известна мощность только множества С, |C|=5. Учитывая, что немецкий язык всего изучает 10 человек, из них 5 изучает и английский, можно сделать вывод, что только немецкий язык изучает 5 человек, т.е. мощность множества А равна 5.
Аналогично, мощность множества В равна 15.
Итого |A|+|B|+|C|=5+5+15=25.
Размещения без повторений
Пусть задано n-элементное множество M. Размещением n-элементного множества M по k называется любое упорядоченное подмножество из k элементов множества M.
Количество размещений из n по k обозначается 
и находится по формуле 
.
n! (n-факториал) – произведение чисел натурального ряда от 1 до числа n включительно.
n!=1*2*3*...*n
0!=1
Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны?
Это пример задачи на размещение без повторений. Размещаются здесь 10 цифр по 6. А варианты, при которых одинаковые цифры стоят в разном порядке считаются разными.
Если X-множество, состоящие из n элементов, m≤n, то размещением без повторений из n элементов множества X по m называется упорядоченное множество X, содержащее m элементов называется упорядоченное множество X, содержащее m элементов.
Количество всех размещений из n элементов по m обозначают
Значит, ответ на выше поставленную задачу будет
