Как решать задачи по комбинаторике?

Комбинаторика – это область математики, изучающая вопрос, сколько разных комбинаций (наборов) можно составить из элементов заданного множества. При этом нужные комбинации подчиняются определенным требованиям, что приводит к различным методам решения задач по комбинаторике.

Истоки этой науки были положены знаменитым математиком и философом Готфридом Лейбницем.

Два основных правила комбинаторной теории

Теория комбинаторики зиждется на двух основных принципах – это правило сложения и правило умножения. Рассмотрим их подробнее.

Правило сложения: Пусть объект А мы можем выбрать из множества 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 цифр. Итого получается 910=909∗10=90 чисел.

Это были главные правила, на которые опираются все методы решения задач по комбинаторике. Еще больше теории о началах комбинаторики вы найдете в онлайн учебнике: Элементы комбинаторики онлайн.

 

Готовые решения задач по теории вероятностей, в том числе по комбинаторике— более 400 решений. Найди свою задачу:

 

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

Перейдем к более продвинутым случаям и рассмотрим другие понятия комбинаторики.

Есть 5 книг. Сколькими способами их можно расположить на книжной полке?
Ответ – 120 способов. Первую книгу можем выбрать 5 способами, вторую книгу 4 способами и т.д. Перемножая числа с 5 до 1, получим 120.

С этой задачи начинается понятие факториала. N-факториал или N! – это количество перестановок из N объектов, вычисляемое по формуле PN=N!=123(N1)NPN=N!=1∗2∗3∗…∗(N−1)∗N.

Следующий пример – в чемпионате мира участвуют 18 команд по футболу. Сколькими способами можно распределить золотые, серебряные и бронзовые комплекты?
Ясно, что золотые медали может получить любая из команд, значит золотого призера (объект А) можно выбрать 18 способами. Остается два комплекта и 17 команд. Серебряным медалистом может стать одна из 17 команд, а бронзовым – одна из 16 команд. Значит, серебряного и бронзового медалиста можно выбрать 17 и 16 способами.
Итого, три комплекта медалей могут распределиться 18*17*16 = 4896 способами.

Нужны еще примеры решений? Вам сюда: задачи с решениями по комбинаторике, решебник по комбинаторике и теории вероятности. А также отличная наглядная схема для выбора формулы комбинаторики.

Информация