Комбинаторика.
Комбинаторика – это раздел математики, в котором рассматриваются вопросы о том, сколько различных комбинаций можно составить из заданных объектов, подчиненных некоторым условиям.
Комбинаторика возникла в XVI веке. Первые задачи комбинаторики касались азартных игр – сколькими способами можно получить данное число очков, бросая две или три кости, или сколькими способами можно вытянуть двух королей из карточной колоды и т.д. Подобные вопросы и явились движущей силой развития комбинаторики и теории вероятностей. Яркий свет в комбинаторике оставили Паскаль, Я. Бернулли, Лейбниц, Эйлер и другие математики. В ХХ веке, в связи с созданием ЭВМ и повышением интереса к дискретной математике комбинаторика переживает бурный рост. Комбинаторные задачи возникают в анализе и алгебре, геометрии и топологии, в различных разделах математики и в приложениях.
Правила комбинаторики.
Основные комбинаторные формулы.
Существует два общих правила комбинаторики: правило сложения и правило умножения.
Правило умножения:
Пусть составляются всевозможные строки 
длины 
. Пусть первая компонента строки может быть выбрана числом способов, равным 
. После того, как первая компонента выбрана и независимо от того, как она выбрана, вторая компонента выбирается числом способов, равным 
. Далее аналогично. Последняя компонента выбирается числом способов, равным 
. Тогда количество всех построенных строк равно произведению: 
.
Правило сложения:
Если некоторый элемент 
можно выбрать 
различными способами, а другой элемент 
выбирается способами, то объект «
» можно выбрать 
способами.
Замечание: Правило сложения, как и правило умножения, можно обобщить на случай слагаемых.
Можно также отметить, что знак умножения в соответствующем правиле соответствует союзу «и» русского языка. А знак сложения – союзу «или». Причём, союз «или» применяется во взаимоисключающем смысле.
Для дальнейшего изложения необходимо ввести следующее вспомогательное понятие.
Определение 1: Пусть дано конечное множество 
из элементов. Всякий набор из 
элементов данного множества (при этом элементы в наборе могут и повторяться) будем называть - расстановками.
Через понятие расстановки вводятся основные определения комбинаторики: сочетания, размещения и перестановки. При этом каждое из этих понятий может быть с повторениями и без повторений.
Размещения.
1) Размещения без повторений.
Определение 2: Пусть имеется различных предметов. Расстановки из элементов по элементов (
) называются размещениями без повторений. Обозначают: 
. Здесь имеется в виду, что элементы в расстановках не повторяются.
В данном определении существенной является следующая позиция: две расстановки различны, если они отличаются хотя бы одним элементом или порядком элементов.
Теорема 1: Число всех размещений без повторений вычисляется по формуле:
.
Пример: Собрание из 25 человек выбирает президиум из 3 человек. Сколько возможно вариантов выбора?
.
Замечание: Число размещений без повторений можно также находить по формуле:
.
Если в знаменателе дроби 
, то принято считать 
.
2) Размещения с повторениями.
Определение размещений с повторениями аналогично предыдущему, но отличается существенно тем, что элементы в подмножествах могут повторяться. Обозначают: 
.
Теорема 2: Число всех размещений из элементов по элементов с повторениями находится по формуле:
.
Доказать теорему можно индукцией по числу .
Примеры: количество телефонных номеров, автомобильных номеров, комбинаций в секретном замке, генетический код. Во всех этих ситуациях в расстановках элементы могут повторяться.
Количество комбинаций в секретном замке, число телефонных номеров, число автомобильных номеров, код Морзе, генетический код.
Разгадка генетического кода – крупнейшее достижение биологии ХХ века. Информация записана в гигантских молекулах ДНК (дезоксирибонуклеиновой кислоты). Различные молекулы ДНК отличаются порядком 4-х азотистых оснований. Эти основания определяют порядок построения белков организма из двух десятков аминокислот, причём каждая аминокислота зафиксирована кодом из 3-х азотистых оснований.
В одной хромосоме содержится несколько десятков миллионов азотистых оснований. Число различных комбинаций, в которых они могут идти друг за другом столь велико, что ничтожной доли этих комбинаций хватит для зашифровки всего многообразия живых организмов за время существования жизни на земле, оно равно 
, где 
– число оснований в хромосоме.
Перестановки.
1) Перестановки без повторений.
Определение 3: Пусть - конечное множество из элементов. Перестановками из элементов множества называются все размещения из элементов множества . Обозначается: 
.
Согласно определению:
.
Таким образом: 
.
2) Перестановки с повторениями.
Перестановки с повторениями используются в тех задачах, в которых речь идёт не о единичных объектах, а о видах, классах, сортах элементов. Понятно, что внутри каждого вида элементы повторяются.
Пусть имеются предметы различных типов:
.
Сколькими способами можно переставить местами 
элемент первого вида, 
элементов второго вида,..., 
элементов последнего вида?
Число элементов в каждой перестановке равно: 
.
Перестановки элементов внутри вида не меняет перестановку. Она изменится только в случае межвидовых перестановок. Если бы все элементы были бы различными, то число всех перестановок равнялось бы 
. Но в силу того, что есть повторяющиеся объекты, получится меньшее число перестановок.
Теорема 3: Число различных перестановок с повторениями находится по формуле:
, где .
Замечание: В комбинаторике если не нужно засчитывать какое-то число способов, то на это число делят.
Поэтому в знаменателе дроби стоят числа 
(число перестановок элементов первого вида, которые не нужно засчитывать), 
(число перестановок элементов второго вида) и т. д. Перестановки элементов первого типа, второго типа и т.д. можно делать независимо друг от друга, поэтому по правилу умножения элементы данной перестановки можно переставлять 
способами. Значит, число различных перестановок с повторениями будет равно указанному числу.
Например, перестановки букв в словах мама, математика, анаграммы – есть перестановки с повторениями.
Сочетания.
1) Сочетания без повторений.
Определение 3: Сочетания из элементов по элементов () – это расстановки, отличающиеся друг от друга составом, но не порядком элементов. Обозначают: 
.
Теорема 4: Число сочетаний находится по следующей формуле:
.
Доказательство: 
.
Следствие: Выведенная формула совпадает с формулой для числа повторений из элементов одного типа и 
элементов второго типа:
.
Иными словами справедливо равенство: 
.
Примеры: Выбор делегации, число призеров в соревновании и т. д.
Замечание: 
, 
.
Существенное отличие числа сочетаний от числа соответствующих размещений состоит в том, что для размещений важен состав и порядок элементов в подмножествах, а для сочетаний важен только состав.
2) Сочетания с повторениями.
Пусть имеется предметы различных типов. Сколько комбинаций можно сделать из них, если не принимать во внимание порядок элементов? Эту задачу в общем виде можно решать точно так же, как задачу с пирожными.
Задача: В кондитерском магазине продаются пирожные 4 сортов: наполеон, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?
Зашифруем каждую покупку с помощью нулей и единиц. Напишем столько единиц, сколько куплено наполеонов, затем пишем 0, чтобы отделить пирожные одного типа от другого и т.д. Тогда каждой покупке будет соответствовать последовательность из семи единиц и трех нулей в различном порядке. Число всех таких покупок тогда будет равно:
.
Для числа сочетаний с повторениями существует формула:
.
Свойства сочетаний. Бином Ньютона.
Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать следующие свойства сочетаний:
1. 
.
2. 
.
Доказательство:
1) 
.
2) 
.
Сочетания можно встретить и в школьном курсе математики. Например, в качестве коэффициентов бинома Ньютона выступают именно сочетания. Формула бинома Ньютона в общем виде и её доказательство приводятся в следующей теореме.
Теорема 1: 
.
Доказательство: Применим индукцию по .
При 
: 
.
Пусть формула верна, для случая, когда 
. В этом случае следующее равенство будем считать выполненным:
.
Покажем, что формула выполняется для - й степени:
.
В доказательстве можно также использовать свойство: 
.
Следствие: Рассмотрим некоторые частные случаи формулы бинома Ньютона:
1) если 
, то 
.
2) если 
, то 
.
Определение 1: Коэффициенты бинома Ньютона называются биномиальными коэффициентами.
Числовые значения биномиальных коэффициентов вычисляются по формуле числа сочетаний: 
. Готовые значения этих коэффициентов располагаются в строках треугольника Паскаля.
1 n = 0
1 1 n = 1
1 2 1 n = 2
1 3 3 1 n = 3
1 4 6 4 1 n = 4
1 5 10 10 5 1 n = 5
.........................
Треугольник Паскаля строится следующим образом. Боковые стороны состоят из единиц. Числа, находящиеся внутри, являются суммой вышестоящих чисел. Каждая строка треугольника соответствует некоторой степени для суммы 
и содержит соответствующие биномиальные коэффициенты. Таким образом, для того, чтобы раскрыть степень суммы 
, нужно из треугольника Паскаля взять строку, соответствующую данной степени . Эта строка будет содержать нужные коэффициенты , к которым приписываются соответствующие буквенные выражения. Можно заметить, что строки треугольника Паскаля симметричны, поэтому достаточно взять только половину биномиальных коэффициентов и, если нужно, средний элемент.
Формула бинома Ньютона применяется, когда нужно возвести в целую степень сумму двух слагаемых. Если же это требуется произвести для суммы трёх и более слагаемых, тогда применяют полиномиальную формулу:
Сумма в правой части формулы строится по аналогии с формулой бинома. Она представляет собой сумму слагаемых, состоящих из коэффициента 
и буквенной части 
. Сумма этих слагаемых берется по всевозможным разбиениям числа на целых неотрицательных слагаемых 
, при этом коэффициент находится по формуле числа перестановок с повторениями:
.
Если числа 
получаются перестановкой из чисел 
, то считается, что
.
Пример: Возвести в пятую степень сумму трёх слагаемых.
Здесь учитывается, что 5 можно разбить на 3 слагаемых пятью способами:
; 
; 
; 
; 
.
Тогда для каждого такого разбиения известны числа 
, 
. Значит, все коэффициенты можно для каждого случая найти по формуле:
.
Полученные коэффициенты: 
, 
, 
, 
, 
. Буквенная часть также формируется в связи с разложениями числа 5 на 3 слагаемых. Таким образом, получается разложение, приведённое выше.
Замечание: Сумма полиномиальных коэффициентов может быть найдена по формуле:
.
Для коэффициентов из рассмотренного примера можно проверить:
,
.
Рассмотрим - сочетания с повторениями, составленные из элементов 
типа, например из буквы 
. Число таких сочетаний равно: 
. Разобьём все эти сочетания на классы, отнеся к ‑ му классу сочетания, в которых раз входит буква 
. Остальные 
мест могут быть заняты оставшимися буквами 
, число которых равно . Поэтому в - й класс входит столько сочетаний, сколько можно составить 
сочетаний с повторениями из элементов типов, т.е. 
.
Значит общее число всех таких сочетаний равно:
, т.е.
.
Меняя теперь на и на 
и используя равенство , получаем зависимость между биномиальными коэффициентами:
.
Доказать эту формулу можно методом математической индукции по числу слагаемых в правой части. Используя эту зависимость, можно получить формулы для подсчёта суммы чисел натурального ряда от 1 до (при 
), суммы квадратов натуральных чисел (при 
), сумму кубов (при 
).
Если , то искомая зависимость имеет вид:
.
Для имеем:
,
или окончательно:
.
Для получаем:
,
или после преобразований:
.
Таким образом, можно получить формулы для сумм более высоких степеней натуральных чисел.
Числа Фибоначчи.