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

нении ни одна перестановка не будет получена дважды. На основании проведенного построения подсчитаем число перестановок («,/). Для добавления элементов i,,i\ по типу а имеется /(/?— I,/-)- 1) перестановок (я- 1, I -+- 1). В каждой из них добавление можно произвести 2( / - f l ) способом. Следова­ тельно, это добавление даст нам 2(1+ 1)/ (л— 1, I -f 1) пе­ рестановок (л, /). Пара it, i, может быть выбрана я спосо­ бами, поэтому общее количество перестановок (я,/) этого типа равно 2(/-Ь1)л/(л— 1 , /+1 ) . Случаем, когда образование перестановок ( п,1 ) по типу а йсключается, является 1> п — 1. Но, как легко видеть, в этом случае /(я — 1 , 1 + 1) = 0 и, следовательно, найден­ ное выражение имеет место и для него. Для добавления элементов iu it по типу б имеется /(л— 1,1) перестановок (я—1,/)- В каждой из них добавле­ ние можно произвести 2 (2л— / 2) способами. Следователь­ но, это добавление дает 2 (2л— /—2)/(я—1,/) перестановок {п,1). Пара г'и/2 может быть выбрана «способами, поэтому общее число перестановок (л,/) по этому типу равно 2 (2л— I— 2) я (п - 1,1). Случаем, когда образование пере­ становок по этому типу исключается, является I > я. Но, как легко видеть, в этом случае j (п— 1, /) = 0 и, следова­ тельно, найденное выражение имеет место и для него. Для добавления элементов iL, i2 по типу в имеется /(я—1, / —1) перестановок (я —1, I —1). В каждой из них добавление можно произвести 2 способами. Следовательно, это добавление даст 2/(л — 1,1 —1) перестановок (л,/). Пара iu г2 может быть выбрана л способами, поэтому об­ щее число перестановок (л,/) поэтому типу равно 2лу(я—1, L —1). Случаем, когда образование перестановок по этому типу исключается, является 0>/. Но в этом случае /(л—1, I —1) = 0и , следовательно, найденное выражение имеет место и для него. Общее число перестановок (я, /) найдется как сумма /(л, /) —2 (/ + 1) л / (л— 1,1 f 1) -f 2 (2я — I —2) я / (я - 1 , / ) + 2 л / ( я - 1 , / - 1 ) . (2) Исходя из этой формулы, подсчитаем /(я, я). На основании (1) уравнение (2) запишется в виде у(я, л) —2яу (я — 1, л— 1). (3) Понижая последовательно аргументы, получим: /(я , л) = 2я- 1л (я— 1)... 2t (1, 1). (4) 191