Определение.Кортеж (a ,...,a )Î A называется k- выборкой из множества A. Иногда k- выборки называют размещениями с повторениями. n

Пример 1. Пусть A ={ a , a , a }. Выпишем все 2- выборки из множества A:

(a , a ), (a , a ), (a , a ),

(a , a ), (a , a ), (a , a ),

(a , a ), (a , a ), (a , a ). n

Обозначение. Символ обозначает число всех k - выборок из n - элементного множества.

Обозначение. Пусть C и D - конечные множества, C - множество, число элементов которого перечисляются (подсчитываются), D - множество, число элементов которого мы умеем перечислить. Тогда биекция f: C ® D называется кодированием множества C, говорим, что элементы множества D кодируют элементы множества C, элементы множества C кодируются элементами множества D.

Число элементов в множестве C равно числу элементов в множестве D.

Следствие 2. Справедливы утверждения:

1. = n .

2. Если A и B - конечные множества, то число функций f: B ® A равно

| A | .

Доказательство. 1. Множество всех k - выборок из n - элементного множества A равно A . Поэтому = | A | = | A | = n .

2. Пусть B = { b ,..., b } - k - элементное множество, функция f: B ® A. Функцию f можно записать в табличном виде

,

где есть k - выборка из множества A. Поэтому число всех функций f: B ® A равно | A |= | A | = | A | . n

Следствие 3. Число всех подмножеств n- элементного множества равно 2 .

Доказательство. Пусть A ={ a ,..., a } есть n - элементное множество. Каждое подмножество множества A кодируется кортежем (s ,..., s ), где s = 1, если a принадлежит подмножеству, s = 0, если a не принадлежит подмножеству. Число таких кортежей равно n

Теорема 2. Если первую координату кортежа длины k можно выбрать n способами, при любом выборе первой вторая координата может быть выбрана n способами, при любом выборе первых двух координат третья может быть n способами и т.д. до k - ой координаты включительно, то общее число полученных таким образом кортежей равно n n ... n .

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

Для k = 1 утверждение очевидно выполнено.

Предположим, что утверждение справедливо для числа k и докажем его для числа k +1. Подсчитаем число построенных таким образом кортежей (a ₁,..., a , a ) c фиксированной последней координатой a . Число таких кортежей равно числу кортежей (a ,..., a ), по индукционному предположению оно равно n ... n . Т.к. элемент a может быть выбран n способами, то число всех кортежей (a ,..., a , a ) равно n ... n n .

Теорема доказана по индукции. n

Пример 2. Пусть | A | = n. Сколько существует кортежей из k элементов множества A, не содержащих рядом расположенных одинаковых элементов? Первая координата кортежа может быть выбрана n способами, если первая координата выбрана, то вторая может быть выбрана n -1 способом, если первые две координаты выбраны, то третья координата может быть выбрана n -1 способом и т.д. до k - ой координаты включительно. По теореме 2 искомое число равно n (n -1) . n

Теоремы и следствия этого пункта обычно называют правилами произведения.