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

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

Теорема 1. Пусть A ,..., A - конечные множества, k Î N. Тогда

| A ´...´ A |=| A |×...×| A |. (1)

Доказательство. Доказательство производится индукцией по k.

При k = 1 равенство (1) выполнено.

Предположим, что равенство (1) доказано для числа k.

Докажем равенство (1) для числа k + 1. Число | A ´...´ A | равно числу кортежей (a ,..., a , a ), где a ÎA ,..., a ÎA , a ÎA . Подсчитаем число таких кортежей с фиксированным a . Это число равно числу кортежей (a ,..., a ), где a ÎA ,..., a ÎA , т.е. равно |A ´...´A | равному, по индукционному предположению, |A |×...×|A |. Т.к. a может быть выбран |A | способами, то

|A ´...´A | = |A |×...×|A |×|A |.

Равенство (1) доказано индукцией для всех k Î N. n

Следствие 1. Пусть A - конечное множество, k Î N. Тогда

| A | = | A | . n