Элементы комбинаторики. Комбинаторика - это теория конечных множеств

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

Основным методом комбинаторики является метод математической индукции. Он состоит в следующем:

Если некоторое свойство, заданное на множестве целых неотрицательных чисел, справедливо для 1, и если, каково бы ни было целое положительное число n, из справедливости этого свойства для n вытекает справедливость его для n=1, то это свойство справедливо для всех положительных целых чисел. Иначе, если В(х) - одноместный предикат, определенный на множестве целых положительных чисел, то приведенное выше определение можно переписать следующим образом:

.

Чтобы доказать методом математической индукции некоторое свойство, необходимо

1. Доказать справедливость этого свойства для 1.

2. Для произвольного n доказать справедливость выражения .

Такое доказательство называется доказательством по индукции. Его первая часть называется базисом индукции, вторая - индукционным шагом. При проведении индукционного шага посылку импликации, т.е. предложение B(n) называют индуктивным предположением.

Нередко метод индукции используется не для доказательства свойств целых чисел, а при рассмотрении каких-либо других объектов, занумерованных этими числами. Именно так он будет использоваться в комбинаторных задачах, к рассмотрению которых мы переходим.

Комбинаторными соединениями называются слова конечной длины, составленные из букв конечного алфавита по заранее определенным правилам. Рассмотрим некоторые из низ и правила подсчета их числа.