111111I 1 Iл

С2*1. Так как С2*1 = С. =2», то каж-

*=0к=\к=0к=1к=0

дая из сумм составляет половину числа 2".

Задача 4. Доказать тождествоf]к -С* = /j2"-1.

к-»

Решение. Воспользуемся формулой (1.12.1), из которой, пола-

и,.

гая а = 1 и Ъ = получим + = £ С *хк Дифференцирование

к=0

я

последнего равенства дает n(\ + x)"~l = ]T/tСхк~] Пусть = 1 ,

*»0

и

тогда л(1+1)"" = УЧ" - С* 1 * 1 что доказывает искомое тождество.

Jt=0

1.13. Инверсии

Перестановки особенно важны при изучении алгоритмов сортировки, так как они служат для представления неупорядоченных исходных данных. Чтобы исследовать эффективность различных методов сортировки, нужно уметь подсчитывать число перестановок, которые вынуждают повторять некоторый шаг алгоритма определенное число раз.

Пусть (flj ,а2,.... ап ) — перестановка элементов множества (1, 2,..., п}. Если i < j, a fl; > щ, то пара (а,-, а;)называется инверсией перестановки. Например, перестановка 3142 имеет три инверсии (3, 1), (3, 2), (4, 2). Каждая инверсия — это пара элементов, «нарушающих порядок»; следовательно, единственная перестановка, не содержащая инверсий, — это отсортированная перестановка (1, 2,..., л).

Таблицей инверсии перестановки (а{, а2,..., а„) называется последовательностигде d — число элементов, больших j и расположенных левее/Другими словами, ау — число инверсий, у которых второй элемент равен/ Например, таблица инверсий перестановки 591826473 будет 23640221 0, поскольку 5 и 9 расположены левее 1; 5, 9, 8 — левее 2 и т. д. Всего 20 инверсий. По определению

О <d{ < п - 1, 0<d2<n-2,О1, = 0.

1.14. Обратные перестановки

21

М. Холл установил, что таблица инверсий единственным образом определяет соответствующую перестановку. Из любой таблицы инверсийможно однозначно восстановить перестановку, которая порождает данную таблицу, путем последовательного определения относительного расположения элементов п — (в этом порядке). Например, перестановку, соответствующую таблице инверсий (2,3,6,4,0,2,2,1,0) = dddd-jd, можно построить следующим образом: выпишем число 9; так как d% = I, то 8 стоит правее Поскольку = то 7 стоит правее 8 и 9. Так как г/6 = 2, то 6 стоит правее двух уже выписанных чисел; таким образом, получили расположение 9,8,6,7. Припишем теперь 5 слева, потому что с/с = 0; помещаем 4 вслед за четырьмя из уже записанных чисел, 3 — после шести выписанных чисел (т. е. в правый конец) и получаем 5,9,8,6,4,7,3. Вставив аналогичным

образом 2 и 1, придем к перестановке (5,9,1,8,2,6,4,7,3).

Такое соответствие между перестановками и таблицами инверсий важно, потому что часто можно заменить задачу, сформулированную в терминах перестановок, эквивалентной ей задачей, сформулированной в терминах таблиц инверсий. Рассмотрим, например, еще раз вопрос: сколько существует перестановок множестваОтвет должен быть равен числу всевозмож-

ных таблиц инверсий, а их легко пересчитать, так как можно выбрать п различными способами, можно независимо от выбрать п - 1 способами и т.д., dn - одним способом. Тогда различных таблиц инверсий п(п — 1)...1 = п\ . Таблицы инверсий пересчитать легко, потому что все независимые, в то время какэлементы перестановки должны все быть различными.

1.14. Обратные перестановки

Не следует путать «инверсии» перестановок с обратными перестановками. Пусть «[. <ь..... ап — различные шары, индексы

которых свяжем с номерами шаров. Тогда исходное расположение шаров однозначно определяется тождественной перестановкойе = (1,2,..., и). Пустьп = (т, jt2,..., кп) — произвольная перестановка номеров 1, л, где лА — номер шара на fc-м месте. Такая перестановка отвечает расположению шаров ак ,ак ,...,ап . Вспомним (см. п. 1.5), что перестановка

л = ( 2 •••* и можетбытьзаписанавматричномвиде.Данная

форма записи позволяет рассматривать перестановку в качестве оператора, который заменяет старые номера шаров — верхняя строка матрицы — на новые номера — нижняя строка матрицы. Тогда результат двух последовательных изменений л = (я,,я2,..., л„) и ст = (щ, ст2,..., ст„) исходной последовательности 1,2,..., п номеров шаров можно рассматривать как операцию

умножения перестановок р = пс,=п :... п

Упорядочим столбцы перестановки а в соответствии с переста-новкойл = (я1,я2,...,я„),т.е.ст=Г 1 J «Ш - «„ \

Тогда можно записать, что р=яа= 1 9V % , 112 " П" 1 =

V4 2 "лу у я, стл2 стк„ j

с.

2-\ ... л [ ... п

Этой перестановке отвечает

расположение шаров ар , aPiаРп где значение рд =стя — это

номер шара на месте.

Обратной к перестановке я = и называется пере-

становкая-1 /I2 " " ,= , х которая получает-\ 1 2 ... п J {.щ л2 ... пп f г

ся, если в исходной перестановке поменять местами строки, а затем упорядочить столбцы в возрастающем порядке по верхним элементам, т.е. я1 =(яГ1, п~21 ,...,п~„1). Ясно, что последовательное

изменение порядка шаров согласно перестановкам л = (ль я2,..., л„) и обратной я-1 = (яГ1приводит к исходному их рас-

положению, т.е. к тождественной перестановке

перестановке (5,9,1,8,2,6,4,7,3) будет перестановка (3,5,9,7,

1 * 8 А 91 таккя/.г59 182647 3\ (12345678 9") 1,6,8,4,2), >к2 3 4 5 6 7 8 9J =з5 9 7 1 6 8 4 2/

Сортированную последовательность элементов перестановки л = (я1, я2,..., я„) можно получить, заполнив в цикле вектор еь е2,...,

far к =lto п do ея = пк или е[я J = я