Утверждение 1.1

Число различных перестановок равно (, читается: «n факториал»).

Доказательство. Число перестановок совпадает с числом способов, которыми можно составить различные перестановки. При составлении перестановок в качестве j ₁ можно взять любое из чисел 1, 2, …, n, что дает n возможностей. Если j ₁ уже выбрано, то в качестве j ₂ можно взять одно из оставшихся n – 1 чисел, и число способов, которыми можно выбрать j ₁ и j ₂ будет равно и т.д. Последнее число в перестановке можно выбрать только одним способом, что дает способов, а значит, и перестановок.

Например, при n = 2 (n! = 2) можно образовать две перестановки: (12), (21); при
n = 3 (n! = 6) можно образовать шесть перестановок: (123), (132), (213), (231), (312), (321).

Числа k и р в перестановке составляют инверсию (беспорядок), если k > р, но k стоит в этой перестановке перед р.

Перестановка называется четной, если ее элементы составляют четное число инверсий, и нечетной в противном случае.

Например, перестановка (1, 2,..., n) при любом n является четной, так как число инверсий равно 0; (34125) – четная перестановка, так как число инверсий равно 4, здесь 31, 41 – две инверсии, 32, 42 еще две инверсии; (132) нечетная перестановка, так как число инверсий равно 1, эту инверсию составляют числа 3, 2.

Если в перестановке поменять местами два числа k и р (не обязательно стоящие рядом), то получится новая перестановка. Такое преобразование называется транспозицией.

Дата добавления: 2015-07-15