П.4. r- перестановки, перестановки

Определение. r - перестановкой множества A называется кортеж из r попарно различных элементов множества A. Иногда r - перестановки называют размещениями без повторения.

Если (a ,..., a ) есть r - перестановка n - элементного множества, то r £ n.

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

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

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

Обозначение. Обозначим P (n, r) число всех r - перестановок n - элементного множества, где n, r Î N. Положим P (n,0) = 1 для n Î N ₀.

Теорема 1. Число всех r - перестановок n - элементного множества, где

n, r Î N, вычисляется по формуле

P (n, r) = n = n (n -1)...(n - r + 1). (1)

Доказательство. Первая координата r - перестановки n - элементного множества может быть выбрана n способами, если первая координата выбрана, то вторая координата может быть выбрана n -1 способами, если выбраны первые две координаты, то третья координата может быть выбрана n -2 способами и т.д. до r - ой координаты включительно, которая может быть выбрана n - r +1 способами. Из теоремы 2, п.3, следует равенство (1). n

Следствие 1. Пусть A и B - конечные множества, | A | = n, | B | = r, где

n, r Î N. Тогда число всех инъекций f: B ® A равно P (n, r) = n .

Доказательство. Обозначим B ={ b ,..., b }, инъекция f: B ® A может быть записана в табличной форме

,

где кортеж есть r - перестановка множества A. Поэтому искомое число равно P (n, r). n

Определение. Пусть A есть n - элементное множество. Перестановкой множества A называется n - перестановка множества A. Другими словами, перестановка множества A это кортеж содержащий все элементы множества A по одному разу.

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

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

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

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

Доказательство. Искомое число равно P (n, n) = n = n (n -1)...(n - n +1) =

= n!. n

Следствие 3. Пусть A и B - конечные множества, | A | = | B | = n, n Î N. Тогда число всех биекций f: B ® A равно n!.

Доказательство. Т.к. | A | = | B |, то каждая биекция f: B ® A является инъекцией и наоборот. По следствию 1, искомое число равно P (n, n) = n!. n