Комбинаторная теория является одной из важнейших областей математики, без знания которой не обойтись ни менеджеру, ни программисту, ни другим специалистам. Знать, как проводится решение задач по комбинаторике, значит быть востребованным работником, умеющим решать широкий круг практических задач.
Возникновение комбинаторной теории
Комбинаторика – это область математики, изучающая вопрос, сколько разных комбинаций (наборов) можно составить из элементов заданного множества. При этом нужные комбинации подчиняются определенным требованиям, что приводит к различным методам решение задач по комбинаторике.
Истоки этой науки были положены знаменитым математиком и философом Готфридом Лейбницем.
Два основных правила комбинаторной теории
Теория комбинаторики зиждется на двух основных принципах – это правило сложения и правило умножения. Рассмотрим их подробнее.
Правило сложения: Пусть объект А мы можем выбрать из множества mm способами, а объект В можно выбрать nn способами, то объект «А+В» можно выбрать m + nm+n способами.
Возможно, это правило покажется непосвященному человеку абракадаброй, но ничего сложного нет. Рассмотрим пример – пусть в одном ящике есть mm шариков, а во втором ящике – nn шариков. Сколькими способами можно вытащить шарик из одного этих ящиков. Очевидно, что ОДИН шарик можно достать m + nm+n способами.
Правило умножения: Пусть объект А выбирается mm способами, объект В выбирается nn способами, то оба объекта можно выбрать mnmn способами.
Все очень просто – каждый из mm способов выбора объекта А комбинируется с каждым из nn способов выбора объекта В, то есть количество способов просто умножается друг на друга.
Рассмотрим простой пример: сколько чисел можно составить из цифр 0,1,2,3,4,5,6,7,8,9, если число должно быть двузначным?
Можно
составить 90 чисел – первую цифру числа (объект А) можем выбрать 9
способами, так как число не может начинаться с нуля. Вторую цифру числа
(объект В) можем выбрать 10 способами, так как у нас есть 10 цифр. Итого
получается 9*10=909∗10=90 чисел.
Это были главные правила, на которые опираются все методы решения задач по комбинаторике. Еще больше теории о началах комбинаторики вы найдете в онлайн учебнике: Элементы комбинаторики онлайн.
Примеры решения задач по комбинаторике
Перейдем к более продвинутым случаям и рассмотрим другие понятия комбинаторики.
Есть 5 книг. Сколькими способами их можно расположить на книжной полке?
Ответ – 120 способов. Первую книгу можем выбрать 5 способами, вторую
книгу 4 способами и т.д. Перемножая числа с 5 до 1, получим 120.
С этой задачи начинается понятие факториала. N-факториал или N! – это количество перестановок из N объектов, вычисляемое по формуле PN=N!=1∗2∗3∗…∗(N−1)∗N.
Следующий пример – в чемпионате мира участвуют 18 команд по
футболу. Сколькими способами можно распределить золотые, серебряные и
бронзовые комплекты?
Ясно, что золотые медали может получить любая из команд, значит
золотого призера (объект А) можно выбрать 18 способами. Остается два
комплекта и 17 команд. Серебряным медалистом может стать одна из 17
команд, а бронзовым – одна из 16 команд. Значит, серебряного и
бронзового медалиста можно выбрать 17 и 16 способами.
Итого, три комплекта медалей могут распределиться 18*17*16 = 4896 способами.
Add a Comment