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

Возьмем несколько конечных множеств , состоЯщих соответственно из ЭЛементов, и Найдем, Сколько кортежей длины K можно составить из ЭлЕментов Этих Множеств. Способ, которым мы решим эту Задачу, По сути дела будет тем же самыМ, каким было НайдЕно чисЛо трехзначных номеров без восьмерок. Сначала найдем число кортежей длины 1, составленных из ЭлементоВ Множества . ЯсНО, что их число равно . ВозьмеМ тЕПерь один из этих кортежей и припишем к элемеНТу Справа по очереди все элементы мНОжества . ПолуЧится Кортежей длины 2, у которых Первая коордиНАтА Равна . Но вместо можно было бы взять любой ДруГой ЭлеМент из . Поэтому получается раз по Кортежа, А всего кортежей длины 2 или, как чаще говоРят, Пар. Из каждой такой, пары получим троек, Приписав По очереди все ЭЛементы множества , а всего Троек. Продолжая этот процесс, получим в конце концов кортежей длины K, составленных Из элементов наших множеств.

Полученный результат является одним из ваЖнейших В комбинаторике. На нем основан вывод многих формул этой науки. Есть лишь одна тонкость. Иногда Множество бывает не задано, а определяется после выбора элемента , множество определяется после выборА элементов и и т. д. Но при этом, как бы мы ни Выбрали Элемент , выбор элемента возможен способами, при любом выборе элементов и на третье место имеется кандидатов и т. Д. И в этом случае ответ получится тот же самый: общее число различных кортежей Оказывается Равным .

Так как для подсчета числа всевозможных кортежей прИХодится перемножать числа , то ВывеДенный результат называют «правилом Произведения». Сформулируем, это правило так.

Если Элемент можно ВЫбратЬ способами, После Каждого выбора ЭТоГО элемента следующий за ним Элемент Можно выбрать способами... после выбора ЭЛЕмЕНтов элемент ВЫбирается способами, то Кортеж Можно ВЫбратЬ сПОсобАми.

Подсчитаем, НАпример, сколько слов, Содержащих 6 Букв, можно составить из 33 букв русского алфавИТа при УсловиИ, что любыЕ две стоящие рядом буквы разлИЧНы (напРИмер, слово «корова» допускается, а слово «колосс» Нет). При этом, разумеется, мы будем писать не только Слова, имеющие смысл, по и такие, например, бессмысленные, как «трнаук» и т. п.

В этом случае на первое место у нас 33 кандидата. НО Пocлe того как первая буква выбрана, вторую можно выбрать лишь 32 способами — ведь повторять первую букву Нельзя. На третье место тоже 32 кандидата — первую буквУ уже можно повторить, а вторую — нельзя. Также убеЖДАЕмся, что на все места, кроме первого, имеется 32 Кандидата. А так как число этих мест равно 5, то получаем ОТвет

< Предыдущая		Следующая >