Основные законы комбинаторики.

Правило суммы.

Пример. На блюде лежат 5 яблок и 2 груши. Сколькими способами можно выбрать один плод?

Решение. Плод можно выбрать семью способами (5+2=7).

Если некоторый элемент a может быть выбран из множества элементов способами, а другой элемент может быть выбран способами, причем любой выбор элемента b отличен от любого выбора элемента a, то выбрать либо a, либо b можно способами.

На языке теории множеств это правило формулируется следующим образом:

Теорема. Если пересечение конечных множеств пусто, то число элементов в их объединении равно сумме чисел элементов множеств А и В.

Правило произведения.

Вторым основным правилом комбинаторики является правило произведения.

Пример. Определить количество клеток в игре «морской бой», если номер клетки состоит из буквы (букв 10) и цифры (цифр тоже 10).

Решение. Количество клеток равно 10•10=100.

Если элемент a можно выбрать из множества элементов способами и после каждого такого выбора элемент можно выбрать способами, то два элемента (упорядоченную пару) и можно выбрать способами.

На языке множеств это правило выражается в виде следующей теоремы.

Теорема. Если множества и конечны, то .

Следствие. Если множества - конечны, то

.

Пример. Сколько номеров, состоящих из двух букв, за которыми идут три цифры можно составить, если использовать 29 букв и 10 цифр.

Решение. Обозначим множество букв , множество цифр – ; каждый номер требуемого вида является набором длины из декартова произведения ; по условию , тогда по следствию из теоремы 2 имеем.

Правило суммы

Правило суммы. Если некоторый объект А можно выбрать способами, а другой объект В можно выбрать способами, то выбор «А или В» можно осуществить способами.

Пример. От Октябрьской площади до цирка можно проехать через Северную и Южную дамбы. В первом случае количество дорог равно 4, а во втором – 3. Сколькими способами можно добраться от Октябрьской площади до цирка?

Решение. Очевидно, число разных путей от Октябрьской площади до цирка равно 4+3=7.

Правило произведения

Правило произведения. Пусть некоторый выбор требует выполнения одного за другим действий. Если первое действие можно выполнить n₁ способами, второе (после него) — n₂ способами, третье — n₃ способами и так до –го действия, которое можно выполнить способами (после выполнения предыдущих действий), то все действий в указанном порядке можно выполнить способами.

Пример. Из Перми до Чайковского можно добраться теплоходом, поездом, автобусом или самолетом; из Чайковского до Ижевска – теплоходом или автобусом. Сколькими способами можно осуществить путешествие по маршруту Пермь – Чайковский – Ижевск?

Решение. Число разных путей из Перми до Ижевска равно , так как, выбрав любой из четырех возможных способов путешествия из Перми до Чайковского, имеем 2 возможных способа путешествия из Чайковского до Ижевска.

Пример. Сколько четырехзначных чисел можно составить из цифр 0,1,2,3,4,5,если: а) ни одна цифра не повторяется больше одного раза в записи числа; б) цифры в записи числа могут повторяться; в) цифры могут повторяться в записи числа, но число должно быть нечетным.

Решение. а) Первой цифрой при этом может быть любая из 5 цифр 1,2,3,4,5 (0 не может быть первой цифрой, потому что в таком случае число не четырехзначное). Если первая цифра выбрана, то вторая может быть выбрана 5 способами, третья — 4 способами, четвертая – 3 способами. Согласно правилу произведения общее число способов равно .

б) Для первой цифры имеем 5 возможностей (1,2,3,4,5), для каждой из следующих цифр – 6 возможностей (0,1,2,3,4,5). Следовательно, общее количество чисел равно .

в) Первой цифрой может быть одна из 5 цифр 1,2,3,4,5, а последней 1,3,5. Следовательно, общее количество чисел равно .

Факториал

(читается – факториал) представляет собой произведение всех натуральных чисел от 1 до включительно . Условились считать, что 0!=1!=1.

Размещения.

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

Например, из 3 элементов по 2 можно образовать следующие размещения: .

Число всех возможных размещений, которые можно образовать из элементов по , обозначается символом и вычисляется по формуле:

(всего множителей).

Пример: .

Сочетания.

Сочетаниями из элементов по называются соединения, которые можно образовать из элементов, собирая в каждое соединение элементов; при этом соединения отличаются друг от друга только самими элементами (различие порядка их расположения во внимание не принимается).

Например, из 3 элементов по 2 можно образовать следующие сочетания:

Число всех возможных сочетаний, которые можно образовать из n элементов по k, обозначается символом :

(В числителе и знаменателе по множителей).

Пример:

Полезные формулы: ;

.

Формула бинома Ньютона

Если -й член ( -е слагаемое) разложения степени бинома обозначать через , то .

Часто при решении комбинаторных задач используется биномиальная теорема (бином Ньютона).

Биномиальная теорема. Имеет место равенство

.

Подробнее данная формула расписывается следующим образом: . Это бином Ньютона. Коэффициенты называются биномиальными коэффициентами.

При n =1 имеем тривиальный случай

при n =2 и n =3 получаются формулы, хорошо знакомые из школьного курса математики: и .