Т е о р е м а 1 (правило произведения). Если множество содержит элементов, а множество содержит n элементов, то их декартово произведение содержит элементов, т.е.

(4)

□ Пусть = и = .Выпишем элементы множества в виде прямоугольной таблицы:

, , …, ,

, , …, ,

…………………………………

, , …, .

В этой таблице m строк и n столбцов и поэтому число ее элементов равно , что и доказывает равенство (4).

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

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

Теорема 1 обобщается на любое конечное число множителей в декартовом произведении.

Т е о р е м а 2 (обобщенное правило произведения).Если конечные множества содержат соответственно элементов, то множество имеет элементов, т.е.

. (5)

□ Применим индукцию по числу .

База индукции.При равенство (5) справедливо.

Шаг индукции.Предположим истинность равенства (5) для , т.е. что

, (6)

и рассмотрим . Легко видеть, что

= (7)

(это равенство вытекает из существования взаимно‑однозначного соответствия

между множествами и ). Используя теорему 1 и предположение индукции (6), отсюда получаем

= = . (8)

Из (7) и (8) следует теперь,

= .

Таким образом, мы доказали, что равенство (5) справедливо при .

Вывод.На основании обычного принципа математической индукции равенства (5) истинно при любом натуральном .