Комбинаторика – это область математики, изучающая вопрос, сколько разных комбинаций (наборов) можно составить из элементов заданного множества. При этом нужные комбинации подчиняются определенным требованиям, что приводит к различным методам решения задач по комбинаторике.
Теория комбинаторики зиждется на двух основных принципах – это правило сложения и правило умножения.
Правило сложения
Пусть в множестве А имеется m элементов, а в множестве В – n элементов. Если у множеств А и В нет общих элементов, то в их объединении число элементов равно
Если для конечного множества Х мы через |Х| обозначим количество его элементов, то правило сложения можно записать так:
Если то
Это правило несложно обобщается на случай, когда у множеств А и В есть общая часть.
Пример – пусть в одном ящике есть m шариков, а во втором ящике – n шариков. Сколькими способами можно вытащить шарик из одного этих ящиков. Очевидно, что ОДИН шарик можно достать m+n способами.
Правило умножения
Число пар, составленных из элементов множеств А и В, равно произведению количеств элементов этих множеств.
Множество пар элементов двух множеств часто обозначают с помощью знака произведения. Тогда правило умножения можно записать так:
Правило умножения легко пояснить с помощью таблицы. Если мы составим прямоугольную таблицу и занумеруем (обозначим) ее строчки элементами множества А, а столбцы – элементами множества В, то клетки таблицы будут соответствовать парам где Число клеток таблицы очевидно равно произведению числа строк и числа столбцов.
Пример – пусть в одном ящике есть m шариков, а во втором ящике – n шариков. Сколькими способами можно вытащить шарик из одного этих ящиков. Очевидно, что ОДИН шарик можно достать m+n способами.
Пример: сколько чисел можно составить из цифр 0,1,2,3,4,5,6,7,8,9, если число должно быть двузначным?
Можно составить 90 чисел – первую цифру числа (объект А) можем выбрать 9 способами, так как число не может начинаться с нуля. Вторую цифру числа (объект В) можем выбрать 10 способами, так как у нас есть 10 цифр. Итого получается 9∗10=90 чисел.