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

Пусть имеем несколько конечных множеств , причем .

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

= .

Полученный результат – один из важнейших в комбинаторике. Есть лишь одна тонкость. Иногда множество бывает не задано, а определяется после выбора , а множество определяется после выбора элементов и и т. д. Но при этом, как бы мы ни выбирали , выбор элемента возможен способами; при любом выборе и на третье место имеется некоторое число претендентов и т. д. И в этом случае ответ получится тот же самый:

Пример. Сколько восьмизначных чисел можно построить из цифр (символов) (0, 1, 2... 9), так чтобы цифры не повторялись?

Так как речь идет именно о восьмизначном числе, а не о последовательности из 8 знаков, то, следовательно, 1-ая цифра не может быть нулем.

Тогда множество - кандидатов на 1-ое место содержит 9 элементов (1, 2,..., 9);после выбора первой цифры множество содержит снова 9 элементов - те цифры, которые не равны первой; если первая цифра