УЧЕНЫЕ ЗАПИСКИ ВЫПУСК 5

М. Н. ДОБРОВОЛЬСКИЙ РЕШЕНИЕ ОДНОЙ КОМБИНАТОРНОЙ ЗАДАЧИ Исследуемая задача возникла в ходе работы спецсеми­ нара, которым руководил в 1949-50 гг. В. Д. Подсыпа­ нии. Задача формулируется следующим образом: Определить число перестановок элементов л пар: аи a.lt bv Ьг, ... к1Ук2, в которых элементы / пар попарно стоят рядом. Будем называть перестановку элементов л пар, в кото­ рой элементы / пар попарно стоят рядом, перестановкой (л, /). Обозначим число перестановок (л, /) через /(л, /). Функция /(л,/) определена для 0 I п. Пр и / < 0 или / > л положим /(п,1) = 0. (1) I. Для определения числа перестановок (л, I) заметим, что любая перестановка (л,/) может быть получена одним из трех способов: а) добавлением в перестановку (п — 1, /-(-1) элементов недостающей пары в конец перестановки и в промежуток между стоящими рядом элементами одной пары; б) добавлением в перестановку (ft—1,1) элементов недо­ стающей пары вконец перестановки и в промежуток меж­ ду элементами разных пар или в начало перестановки; в) добавлением в перестановку (л—1 ,/—1) недостающей пары элементов в конец перестановки. При этом построении ни одна перестановка (л, I) не бу­ дет пропущена, так как при исключении из перестановки (л, /) элемента, стоящего в ее конце, вместе с парным ему образуется либо перестановка (л— 1, / -j- 1), либо переста­ новка (it—1,1), либо перестановка (п— 1,1 —1). С другой стороны, построение перестановок (л,/), как легко видеть, сохраняет различие исходных перестановок в порядке следования элементов и потому при его выпол­ 190