|
Комбинаторика – раздел математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить. Комбинаторика (от латинского combinare) означает "соединять, сочетать”. С задачами, в которых приходилось выбирать те или иные предметы, располагать их в определенном порядке и отыскивать среди разных расположений наилучшие, люди столкнулись еще в доисторическую эпоху, выбирая наилучшее положение охотников во время охоты, воинов – во время битвы, инструментов – во время работы. Комбинаторные навыки оказались полезными и в часы досуга; с тех времен появились различные игры: нарды, шахматы, шашки, карты. В каждой из этих игр приходилось рассматривать различные сочетания фигур, и выигрывал тот, кто их лучше изучил, знал выигрышные комбинации. Дипломаты, стремясь к тайне переписки, изобретали сложные шрифты, основанные на комбинаторных принципах. В современном обществе, с развитием вычислительной техники, была решена комбинаторная задача, известная под названием «проблема четырех красок»: удалось доказать, что любую карту можно раскрасить в четыре цвета так, что никакие две страны, имеющие общую границу, не будут окрашены в один и тот же цвет. Задачи, решая которые приходится составлять различные комбинации из конечного числа элементов и подсчитывать число комбинаций, получили название комбинаторных. Так, как же решать комбинаторные задачи? Как мы увидим дальше, комбинаторные задачи бывают самых разных видов. Но большинство задач решается с помощью двух основных правил — правила суммы и правила произведения. Правило суммы. Если на блюде лежат три яблока, то выбрать одно яблоко можно тремя способами (взять одно из трех яблок). Если на другом блюде лежат две груши, то выбрать одну грушу можно двумя способами (взять одну из двух груш). А выбрать один фрукт можно пятью способами (выбирая из пяти фруктов — трех яблок и двух груш). Это и есть правило суммы, которое можно сформулировать так: Если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить m + n способами.
Правило суммы применяют, когда удается разбить все изучаемые комбинации на несколько классов, причем каждая комбинация входит в один и только один класс. Ясно, что в этом случае общее количество комбинаций равно сумме количеств комбинаций во всех классах.
|
