4. Декартово произведение множеств. Размещения с повторениями.

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

Например, если то декартово произведение состоит из шести пар:

Декартово же произведение тоже состоит из шести пар, компоненты которых идут в ином порядке:

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

Найдем число элементов декартова произведения в случае, когда X является -множеством, -множеством. Пусть Декартово произведение состоит из пар Их можно расположить следующим образом:

Мы получили строк по пар в каждой строке. Отсюда следует, что общее число пар, входящих в равно т. е. Иными словами, имеет место следующая формула:

Она выражает правило произведения:

Число элементов в декартовом произведении конечных множеств равно произведению числа элементов множества X и числа элементов множества

С помощью метода математической индукции легко обобщить это правило на случай произведения нескольких множеств. Именно при любом верна формула

В самом деле, мы уже доказали эту формулу для Предположим, что ее справедливость уже доказана для

Возьмем теперь множества Любой кортеж длины из элементов этих множеств имеет вид:

Поставим в соответствие каждому такому кортежу пару состоящую из кортежа и элемента По правилу произведения для число таких пар равно Но по предположению

и потому число пар рассматриваемого вида равно

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

Но это и есть формула (2) для

Итак, мы доказали справедливость формулы (2) при и из ее справедливости при вывели, что она верна и при Отсюда следует, что эта формула верна для всех

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

Если элемент а можно выбрать способами, а элемент способами, то пару можно выбрать способами.

Иногда для решения задач приходится пользоваться обобщенным правилом произведения. А именно бывает, что различные варианты выбора элемента определяются уже сделанным выбором элемента а, но после каждого выбора элемента а элемент можно выбрать одним и тем же числом способов. И в этом случае число способов выбрать пару равно где число способов выбрать элемент число способов выбрать элемент после того, как элемент а выбран.

Пример. Найдем число слов длины 4, составленных из 33 букв русского алфавита, и таких, что любые две соседние буквы этих слов различны (допускается слово «хата», но не допускаются слова «веер» или «босс»). При этом мы наряду со словами, имеющими смысл, допускаем и такие бессмысленные сочетания букв, как «арнг», «тосо» и т. д. В этой задаче первую букву слова можно выбрать 33 способами. Но после того, как она выбрана, следующую букву можно выбрать лишь 32 способами (повторить выбранную букву уже нельзя). Третья буква должна быть отлична от второй (хотя и может совпадать с первой), а потому ее можно выбрать тоже 32 способами, равно как и четвертую. Поэтому общее число способов выбора равно

С помощью формулы (2) легко решить такую задачу:

Найти число всех кортежей длины составленных из элементов -множества X.

Искомое число равно числу кортежей в декартовом произведении , содержащем множителей. По формуле (2) получаем:

Но а потому

Итак, число кортеоюей длины составленных из элементов -множества X, равно

Например, из 33 букв русского алфавита можно составить слов длины слов длины слов длины 4 и т. д. Точно так же из 10 цифр 0, 1,2, 3, 4, 5, 6, 7, 8, 9 можно составить двузначных номеров (00, 01, ..., трехзначных номеров и т. д.

Кортежи длины составленные из элементов -множества, называют размещениями с повторениями из элементов по а их число обозначают (от французского слова arrangement - размещение; черта поставлена сверху, чтобы отличать эти размещения от размещений без повторений, которые мы рассмотрим позднее). Таким образом,