Принцип умножения

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

1. Если для пары первый член может быть выбран из элементов , а второй — из элементов , то общее количество таких пар равно произведению .

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

2. Если для тройки первый элемент может быть выбран из элементов , второй — из элементов , а третий — из элементов , то общее количество троек равно произведению .

Действительно, каждая фиксированная пара порождает троек: . Всего, таким образом, получается раз по троек.

3. В общем случае (доказывается по индукции), если строится набор из элементов, причем первый член может быть выбран способами, второй — способами, и т.д., наконец, последний — способами, то общее количество -членных наборов равно произведению .

Для случая пар принцип умножения иллюстрируется (по аналогии с матрицами) прямоугольной таблицей, в которой пара стоит на пересечении -ой строки и -го столбца.

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

Рис.1.

Примеры. 1. Количество четырехзначных натуральных чисел, у которых все цифры разные, и первая цифра отлична от нуля, по принципу умножения, равно .

2. Количество пятизначных натуральных чисел, которые могут быть записаны с помощью цифр равно .

3. Каждое подмножество множества из элементов взаимно однозначно характеризуется набором из нулей и единиц: если элемент входит в подмножество, то на i -м месте набора стоит единица, в противном случае — нуль. Например, пустому множеству соответствует набор из нулей, самому множеству — набор из единиц, одноэлементному подмножеству — набор, в котором на i -м месте стоит единица, а на остальных местах нули. Количество таких наборов, а значит, и количество всех подмножеств, равно .