§ 2. Правило произведения для конечных множеств

Рассмотрим пример. Из Казани в Самару можно добраться (летом) пароходом, поездом и самолетом, т.е. тремя способами. Из Самары до Тольятти можно доехать на автобусе или такси. Сколькими способами можно добраться из Казани до Тольятти, используя указанные возможности? Очевидно, что 3×2=6 способами.

Пусть даны произвольные конечные множества А и В. Выясним сколько элементов содержит их декартово произведение А×В. Напомним, что декартовым произведением непустых множеств А и В называется множество упорядоченных пар: $А×В=\{〈x,y〉: (x∈А)$&$(y∈В)\}$

Для k множеств $A_1, A_2, ..., A_k$ их декартово произведение определяется как множество упорядоченных k элементов: $А_1×А_2×…×А_k=\{〈x_1,x_2,…,x_k〉 : (x_1∈А_1)$&$(x_2∈А_2)$& … &$( x_k∈А_k)\}$

Для каждого а∈А обозначим через R(a) множество всех упорядоченных пар 〈а,b〉, составленных из элемента а и всевозможных b из В, т.е. $R(a)={〈а,b〉: b∈В}$.

Очевидно, что n(R(a))= n(В). При различных а1 и а2 (а1 ≠ а2) множества R(а1) и R(а2) не имеют общих элементов, т.е. R(а1)∩R(а2)=∅. Ясно, что . Тогда по правилу суммы получим:

($a∈A$) $∪R(a) = A×B$

$n(A×B) = \sum_{a∈A} n(R(a))$

Число слагаемых, очевидно равно n(А), следовательно,

$n(A×B) = n(A) n(B) = nm$

где n=n(А) и m=n(В). Это соотношение и называется правилом произведения.

Правило произведения можно сформулировать следующим образом: если объект А может быть выбран n способами и после каждого из таких выборов объект В в свою очередь может быть выбран m способами, то выбор «А и В» в указанном порядке может быть осуществлен nm способами.

Индукцией можно доказать следующее обобщенное правило произведения:

$n(А_1×А_2×…×А_к)= n(А_1) n(А_2) … n(А_к)$