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

Рассмотрим правило суммы.

Если некоторый элемент из одного множества можно выбрать n способами, а из другого -- m способами, то существует m+n способов выбора данного объекта из двух множеств.

Пример: Есть возможность добраться из пункта А в пункт В либо самолетом (три рейса в день), либо поездом (два рейса в день). Сколько существует вариантов отправления человека из пункта А в пункт В?

3+2=5 – вариантов. Это и есть правило суммы для непересекающихся множеств.

Если множества пересекаются, то число способов выбора объекта будет m+n-k, где k – элементы, лежащие одновременно в двух множествах.

Пример: Из двух магазинов нужно выбрать один товар. В первом магазине 5 видов подходящего товара, во втором – 10, причем среди 5-ти и 10-ти видов 3 одинаковых. Сколько существует способов выбора подходящего товара?

5+10-3=12 – способов.

Правило умножения.

Пример: Нужно добраться из пункта А в пункт С через пункт В. Из пункта А в пункт В ведут три дороги; из пункта В в пункт С – четыре. Найти все варианты маршрутов следования А–В--С.

3 4=12 вариантов.

В общем виде: если требуется поэтапно выполнить какое-либо действие, причем, первый этап можно осуществить способами, второй -- способами, и т.д., k-й -- способами, то это действие можно осуществить способами. В этом заключается правило произведения.

Известно, что наименьшей расчетной единицей памяти ЭВМ является байт, состоящий из восьми бит – ячеек, в каждую из которых может быть помещены 1 или 0. Набор единиц и нулей может быть различным и в каждом отдельном случае составляет комбинацию. Для нахождения всех возможных комбинаций используется правило умножения. В первой ячейке возможны два варианта – 1 или 0. Каждому из вариантов первой ячейки соответствуют два варианта второй ячейки, т.е. . Продолжая далее, можно посчитать количество всех возможных комбинаций заполнения ячеек единицами и нулями: .