Перестановки (стр. 1 из 2)

Описываются понятия r-перестановок множества, r-сочетания, перестановки с повторениями.

п.1. r- перестановки.

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

Если (a

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

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

Теорема 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).

Следствие 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).

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

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

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

= n(n-1)...(n-n+1) =

= n!.

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

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

п.2. r -элементные подмножества (r - сочетания).

Определение. Пусть A- конечное множество. r- сочетанием множества A называется любое r- элементное подмножество множества A.

Теорема 1. Пусть A есть n- элементное множество, n, rÎN

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

1. Число всех r- сочетаний n- элементного множества равно

.

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

.

Доказательство. Обозначим K- число всех r- сочетаний n- элементного множества A. Каждое r- элементное подмножество n- элементного множества A определяет r! перестановок множества A, при этом разные подмножества определяют разные перестановки. Поэтому K×r! - число всех r- перестановок множества A, равное n

. Отсюда следует, что K = n / r! = = .

Пример 1. Каждый кортеж

N , где , кодируется k-элементным подмножеством множества . Поэтому, при фиксированном k, число всех кортежей N , где , равно .

Пример 2. Перечисление беспорядков степени n. Обозначим U- множество всех перестановок степени n,

. Будем считать, что элементами перестановок являются числа . Перестановка степени n называется беспорядком, если для всех .

Существует только один беспорядок

степени 2.

Существует только два беспорядка

степени 3.

Для

обозначим множество всех перестановок степени n таких, что . Число всех беспорядков степени n равно числу всех перестановок степени n не принадлежащих множеству . Обозначим число всех беспорядков степени n. По формуле включения- исключения

, (1)

где суммирование ведётся по всем кортежам

N таким, что

. Легко видеть, что для любого кортежа N , где справедливо равенство

.

При фиксированном k число всех кортежей

N , где , равно . Из равенства (1) следует, что

.

Поэтому

.

п.3. Перестановки с повторениями.

Определение. Кортеж t = (b

, ..., b ) называется перестановкой с повторениями состава (n , ..., n ) множества {a , ..., a }, если элемент a входит в t n раз, ..., a входит в t n раз, где n , ..., n ÎN , .

Обозначение. Обозначим P(n

, ..., n ) число всех перестановок с повторениями состава (n , ..., n ) некоторого k - элементного множества, где n = = n +...+n .

Теорема 1. Для любого (n

, ..., n )ÎN