Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

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

Например, при 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 и р (не обязательно стоящие рядом), то получится новая перестановка. Такое преобразование называется транспозицией.


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.005 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал