Обратите внимание, что, в отличие от упр. 2, получен алгоритм решения задачи Иосифа, который требует времени, пропорционального O(nlogn), вместо 0{тп). Таким образом, мы частично ответили на вопрос, поставленный в упр. 1.3.2-22.

Другое решение этой задачи {0{nlogn), которое потребует только оперативной памяти), очевидно, следует из методики сбалансированного дерева.

6. Начать с bi = Ьг = • = Ьп = 0. При к = [IgnJ, [IgnJ -1,... ,0 выполнить следующее: установить <- О для О < s < п/г*"*"; затем для j - 1, 2,...,п установить г <- [а>/2*] mod 2, s <- [aj/2>+\ (это, по существу, выделение отдельных разрядов); если г = О, установить Ьа <- baj + Xs, а если г = 1, установить ж <- -t- 1.

Другое решение будет продемонстрировано в упр. 5.2.4-21.

7. Bj < j и Cj <n - j, поскольку aj имеет j-1 элементов слева от него и п - j элементов справа. Для того чтобы восстановить oi ог .. .Оп по Bi в2 - Вп, начните с элемента 1; затем Для к = 2,... ,п добавляйте по 1 к каждому элементу, большему или равному к - Bic, и справа приписывайте элементы к - Bk (см. метод 2 в разделе 1.2.5). Аналогичная процедура годится и для таблицы Ск Альтернативный метод предполагает использование результатов следующего упражнения. [Таблица инверсий Ск была рассмотрена Родригесом (В. О. Rodrigues) в J. de Math. 4 (1839), 236-240; впервые таблица инверсий Ск появилась в книге Netto Lehrbuch der Combinatorik (1901), §5.]

8. 6 = С, с = В, В = с, С = Ь, поэтому каждой инверсии {ai,aj) таблицы а\...ап соответствует инверсия (j, г) перестановки al ...aJ,. Справедливы и другие соотношения: (а) Cj = j - I тогда и только тогда, когда (6; > bj для всех i < j); (b) bj = n - j тогда и только тогда, когда (с, > Cj для всех г > j); (с) bj = О тогда и только тогда, когда (с; - i < Cj - j для всех i > j); (d) Cj = 0 тогда и только тогда, когда {bi+i < bj +j для всех i < j); (е) bi < bi+i тогда и только тогда, когда aJ < aj+i и с; > a+i; (f) Oj = j + Cj - Bj; 4 = J+bj - Cj.

9. Равенство bk = Ск - b. эквивалентно равенству ак = at

10. \/iO. (Один из способов ввести систему координат для усеченного октаэдра - поставить в соответствие взаимным обменам соседних элементов 21, 43, 41, 31, 42, 32 векторы (1,0,0), (0,1,0), (1,1,ч/2), (1,-1,ч/2), (-1,1,ч/2), (-1,-1,ч/2). Сумма этих векторов равна (1,1, 2\/2) и представляет собой разность между вершинами 4321 и 1234.)

Существует решение, имеющее более симметричный вид - представить вершину тг в четырехмерном пространстве следующим образом:

{е„ - вг, I (ы, v) инверсия перестановки тг},

где ei = (1,0,0,0), ег = (0,1,0,0), ез = (0,0,1,0), е4 = (0,0,0,1). Таким образом, 1 234-( (0,0,0,0); 1 243-( (0,0,-1,1); ...; 43 2 1-( (-3,-1,1,3). Все точки лежат на трехмерном подпространстве {{w,x,y,z) \ w + x+ y + z = Q}; расстояние между соседними вершинами равно \/2. Так же (см. ответ 8, (f)) можно представить тг = oi оз оз 04 вектором (al,02,03,04), где о 1 020304 - обратная перестановка. (Такое 4-D представление усеченного октаэдра перестановками в качестве координат было рассмотрено вместе с обобщением на п-мерное пространство С. Говардом Хинтоном (С. Howard Hinton) в книге The Fourth Dimension (London, 1904), глава 10. Много лет спустя другие свойства были найдены Гилбодом (Guilbaud) и Розентилем (Rosenstiehl), которые назвали объект, изображенный на рис. 1, пермутаэдром (permutahedron); см. упр. 12.)

Копии усеченного октаэдра заполняют трехмерное пространство способом, который принято называть простейшим [см. Н. Steinhaus, MatiematicaJ Snapshots (Oxford, 1960), 200-203; С. S. Smith, Scientific American 190,1 (January, 1954), 58-64]. В книге V из СоЛес-tion Паппюса (300 г. н. э.) усеченный октаэдр упоминается как одно из тринадцати особых

тел, исследованных Архимедом. Примером архимедова тела является непризматический многогранник, любая вершина которого симметрична по отношению к любой другой, а любая грань является правильным многоугольником, но не все они идентичны. Его можно найти, например, в книге W. W. Rouse Ball, MatiematicaJ Recreations and Essays, revised by H. S. M. Coxeter (Macmillan, 1939), глава 5, или Н. Martyn Cundy, A. P. Rollett Mathematical JVfodels (Oxford, 1952), 94-109.

11. (a) Очевидно, (b) Постройте ориентированный граф с вершинами {1, 2,..., п} и дугами ж у, если либо X > у и {х,у) € Е, либо х < у к {у,х) € Е. Если этот граф не содержит ориентированных циклов, его вершины можно топологически рассортировать; полученное линейное упорядочение и есть требуемая перестановка. Если же ориентированные циклы присутствуют, то длина кратчайшего из них равна 3, потому что не бывает циклов длиной 1 или 2 и потому что более длинный цикл ai -> а2 -> аз ai можно сократить (либо ai - Оз, либо Оз oi). Но ориентированный цикл длиной 3 содержит две дуги либо из Е, либо из Е, и, таким образом, доказано, что либо Е, либо Е не транзитивно.

12. [G. Т. Guilbaud, Р. Rosenstiehl, Matli. et Sciences Humaines 4 (1963), 9-33.] Предположим, что (а, 6) 6 Е, (6, с) 6 Е, (а, с) Е. Тогда при некотором к > 1 имеем а = жо > Ж1 > • > жд; = с, где {xi,Xi+i) 6 Е{тг1) U E{it2) при О < г < к. Рассмотрим следующий контрпример при минимальном к. Поскольку (а,Ь) E{iti) и (6,с) E{in), то (а,с) E{ni); аналогично (а,с) Е(п2); следовательно, к > 1. Но если xi > b, то (ж1,6) 6 Е противоречило бы минимальности к, а из того, что {xi,b) 6 Е, следовало бы (а, 6) 6 Е. Аналогично, если xi < b, получится, что и (Ь, xi) е Е,и {b,xi) € Е невозможны.

13. Для любого фиксированного выбора 6i,... ,6m-i,6m+i, • • ,Ь„ в таблице инверсий в сумме 53, 6; предполагается, что каждый остаток по модулю т встречается точно один раз по мере того, как Ьт пробегает все возможные значения О, 1, ..., m - 1.

14. Конструкция, предложенная в указании, переводит пары разбиений на различные части одно в другое во всех случаях, кроме двух: j - к = рк и j = к = pk - l- В этих особых

случаях п равно соответственно (2 j-1)-I-----f-j = (3j-j)/2 и (2j)------f-(j4-l) = (3j+j)/2h

существует единственное непарное разбиение на j частей. [Первоначальное доказательство Эйлера в JVovi Comment. Acad. Sci. Pet. 5 (1754), 75-83, также очень интересно. С помощью простых преобразований он показал, что бесконечное произведение равно si, если мы определим Sn в виде степенного ряда 1 - г"" - z"~sn+i для п > 1. Конечная версия бесконечной эйлеровой суммы рассмотрена Кнутом и Патерсоном (Paterson) в Fibonacci Quarterly 16 (1978), 198-212.]

15. Транспонируйте точечную диаграмму с тем, чтобы перейти от р к Р. Производящая функция для Р получается довольно легко, так как сначала можно выбрать любое число единиц (производящая функция 1/(1 - г)), затем независимо выбрать любое число двоек (производящая функция 1/(1 - г)), ... и, наконец, любое количество чисел п.

16. Коэффициент при в первом тождестве равен количеству разбиений числа т на не более чем п частей. Во втором тождестве он равен количеству разбиений числа m на n различных неотрицательных частей, т. е. представляет собой сумму т = р\ + р2 ¥+ Рп, где pi > Р2 > > Рп > 0. Это то же самое, что и разбиения m - (j) = gi + дг + • + 5n, где 51 > 52 > • • • > 5n > О, так как можно установить взаимно однозначное соответствие Qi = Pi - п + i. [Commentaiii Academias Scientiarum Petropolitanae 13 (1741), 64-93.]

Замечание. Второе тождество получаем предельным переходом п - оо вследствие q-номиальной теоремы (см. упр. 1.2.6-58). Аналогично и первое тождество получаем предельным переходом г - оо в дуальной форме этой теоремы, доказанной в ответе к тому же упражнению.

Пусть п!, = n!fc=i(l + 9 Н----+ 9*") и ехр(г) = Yl,=o •2"/"!<?- Из первого тождества

следует, что ехр,(г) равно 1/Yl-o{i-qz{l - q)) при д < 1; из второго следует, что это же

выражение равно ПП=о(1 +9 ( ~ Я )) "Р" \ч\ > 1- Полученное в результате тождество ехр(г) ехр,-1 (-г) = 1 эквивалентно формуле

> 7i-N-тг-ГГГл--Л-ГТТ = «"О- целые числа п > О,

(1 - д)... (1 - д*) (1 - д)... (1 - д"-*)

которая является следствием из д-номиальной теоремы при х = -1.

17. 0000 0100 0010 0001 1101 1201 1021 1012

1010 0110 0120 0102

1011 0111 0121 0112 1001 0101 0011 0012 2012 0212 0122 0123

18. Пусть g = 1 - р. Сумму Рг(а) по всем случаям а инверсий можно вычислить суммированием по к, где О < fc < п - точное число крайних битовых позиций, в которых соблюдается равенство между г и j и между Xi и Xj в инверсии, Xi Ф i > Xj Ф j при i < j. Таким образом будет получена формула Ylo<k<n(P + g2)*(p22"-*-i2"~*~ + 2pg2"~*~(2"~~ - 1)). После суммирования и упрощения она преобразуется в 2"~(р(2 - р)(2" - (р2 + д))/(2 - р - д2) + (р + д)" - 1).

19. Число инверсий равно

([mj/nj - [mi/nj - [m(j - J)/nJ) = [mji mod n<mi mod n] -

0<i<j<ii 0<t<j<n

[mr/nj(r - (n - r) - (n - r - 1)),

0<r<n

что можно привести к виду (ti- 1)(ti- 2) - \п(г{т, п, 0). [См. CreJJe, 198 (1957), 162-166.]

20. См. Е. М. Wright, J. London Math. Soc. 40 (1965), 55-57; и .1. Zolnowsky, Discrete Math. 9 (1974), 293-298.

Тождество Якоби можно быстро доказать следующим образом. Так как П(1 - «*=/-) = (-1)" J"n„(5) fl(l- u-v-),

fc = l k = l

вследствие g-номиальной теоремы, рассмотренной в упр. 1.2.6-58, при q = uv имеем

llil-uv-)il-u-v) = i-iru(r)v(") П (1-«"V)

к=1 к=-п+1

= (-1)%ГГ)„(3) 2«) (,„)()( ,-"„-)«=

= е(л",)..(-).<-"-.

Для фиксированных j после умножения обеих частей на ПГ=1(1 ~ и*г;*) = Пк=1(1 ~ 9*) патучим {1 nr=i(l - 9*) = 1 + 0(g"""~-). При п - оо отсюда следует тождество Якоби.

21. Интерпретируйте Cj как число элементов в стеке после j-ro вывода. (Характеристики Ьк и Вк таблиц перестановок в стеке рассмотрены в упр. 2.3.3-19.)