Обо­зна­чим числа нашей пе­ре­ста­нов­ки слева на­пра­во за a₁, a₂, ..., a_n.

Спо­соб I. Пойдём с конца. По­след­нее число a_n за­бав­ной пе­ре­ста­нов­ки либо боль­ше, либо мень­ше всех чисел мно­же­ства 1, 2, 3, ..., n, сле­до­ва­тель­но, оно равно 1 или n. Пред­по­след­нее число a_n–1 за­бав­ной пе­ре­ста­нов­ки либо боль­ше, либо мень­ше всех чисел мно­же­ства 1, 2, 3, ..., n, кроме a_n, то есть это наи­мень­ший или наи­боль­ший эле­мент во мно­же­стве 1, 2, 3, ..., n−1 или во мно­же­стве 2, 3, ..., n. В каж­дом из слу­ча­ев есть ровно две воз­мож­но­сти вы­бо­ра, ва­ри­ан­ты для двух по­след­них чисел пе­ре­ста­нов­ки вы­гля­дят так Не­слож­но убе­дить­ся, что при любом пер­вые k чисел a₁, a₂, ..., a_k пе­ре­ста­нов­ки об­ра­зу­ют ин­тер­вал из k под­ряд иду­щих чисел из мно­же­ства 1, 2, 3, ..., n, а число a_k яв­ля­ет­ся в этом ин­тер­ва­ле ми­ни­маль­ным или мак­си­маль­ным  — всего две воз­мож­но­сти, кроме са­мо­го пер­во­го числа a₁ для ко­то­ро­го остаётся един­ствен­ная воз­мож­ность. Всего по­лу­ча­ем ровно воз­мож­но­стей вы­бо­ра.

Ответ: 2^n − 1.

Спо­соб II. Пусть a₁  =  m, где m  — одно из чисел 1, 2, ..., n. Любое число a_k мень­шее m, будет по усло­вию также мень­ше и всех чисел, мень­ших m и сто­я­щих левее a_k, по­это­му все числа за­бав­ной пе­ре­ста­нов­ки, мень­шие m об­ра­зу­ют в ней убы­ва­ю­щую под­по­сле­до­ва­тель­ность. Ана­ло­гич­но, все числа, боль­шие m, об­ра­зу­ют в ней воз­рас­та­ю­щую под­по­сле­до­ва­тель­ность. При этом любое вза­им­ное рас­по­ло­же­ние этих под­по­сле­до­ва­тель­но­стей удо­вле­тво­ря­ет усло­вию и при­во­дит к за­бав­ной пе­ре­ста­нов­ке. Сле­до­ва­тель­но, любая за­бав­ная пе­ре­ста­нов­ка пол­но­стью задаётся зна­че­ни­ем её пер­во­го эле­мен­та и но­ме­ра­ми m − 1 мест, на ко­то­рых в убы­ва­ю­щем по­ряд­ке слева на­пра­во рас­по­ло­же­ны числа m – 1, m – 2, ..., 1 среди n − 1 всех чле­нов за­бав­ной пе­ре­ста­нов­ки, кроме пер­во­го. Осталь­ные места ав­то­ма­ти­че­ски за­пол­нят­ся чис­ла­ми m + 1, m + 2, ..., n в по­ряд­ке воз­рас­та­ния. Сле­до­ва­тель­но, при фик­си­ро­ван­ном ко­ли­че­ство за­бав­ных пе­ре­ста­но­вок равно числу со­че­та­ний а общее их ко­ли­че­ство равно сумме

Спо­соб III. Пойдём с на­ча­ла, рас­смот­рим, как ме­ня­ет­ся мно­же­ство пер­вых k чисел за­бав­ной пе­ре­ста­нов­ки при уве­ли­че­нии В ка­че­стве a₁ можно взять любое на­ту­раль­ное число из ин­тер­ва­ла 1, 2, 3, ..., n и Пусть на k-ом шаге уже вы­бра­ны числа a₁, a₂, ..., a_k, обо­зна­чим за m_k и M_k со­от­вет­ствен­но ми­ни­маль­ное и мак­си­маль­ное их них. До­ка­жем, что оче­ред­ное a_k+1 долж­но рав­нять­ся либо m_k − 1, либо m_k + 1. Дей­стви­тель­но, если сразу на­ру­ша­ет­ся усло­вие за­бав­но­сти, так как a_k+1 рас­по­ло­же­но пра­вее m_k и M_k но боль­ше од­но­го из них и мень­ше дру­го­го. Если то число m_k − 1 не вхо­дит в и ещё не ис­поль­зо­ва­но в пе­ре­ста­нов­ке, зна­чит, оно будет рас­по­ло­же­но в ней где-то пра­вее a_k+1 тогда трой­ка на­ру­ша­ет усло­вие за­бав­но­сти, так как при этом m_k − 1 мень­ше m_k, но боль­ше a_k+1, сто­я­щих левее него. Ана­ло­гич­но до­ка­зы­ва­ет­ся, что пред­по­ло­же­ние также на­ру­ша­ет усло­вие за­бав­но­сти. Остаётся толь­ко или

Из до­ка­зан­но­го сле­ду­ет, что для каж­до­го мно­же­ство A_k со­сто­ит из не­ко­то­рых k по­сле­до­ва­тель­ных чисел из ин­тер­ва­ла 1, 2, 3, ..., n и A_k+1 по­лу­ча­ет­ся из него до­бав­ле­ни­ем числа, со­сед­не­го с этим ин­тер­ва­лом слева или спра­ва. Зна­чит, за­бав­ная пе­ре­ста­нов­ка при дан­ном под­хо­де од­но­знач­но задаётся пер­вым чис­лом m, и по­сле­до­ва­тель­но­стью n − 1 до­бав­ле­ния но­во­го числа слева и спра­ва от уже ис­поль­зо­ван­ных, из ко­то­рых m − 1 будут до­бав­ле­ни­ем чисел слева и n − m  — до­бав­ле­ни­ем чисел спра­ва. По­сле­до­ва­тель­ность же до­бав­ле­ний од­но­знач­но опре­де­ля­ет­ся m − 1 но­ме­ра­ми до­бав­ле­ний слева. Сле­до­ва­тель­но, при фик­си­ро­ван­ном пер­вом числе m ко­ли­че­ство за­бав­ных пе­ре­ста­но­вок равно числу со­че­та­ний a общее их ко­ли­че­ство равно сумме

За­ме­ча­ние.

Воз­мо­жен сле­ду­ю­щий ва­ри­ант этого ре­ше­ния. До­ка­зы­ва­ет­ся, что или по­это­му на каж­дом шаге раз­ность между M_k и m_k уве­ли­чи­ва­ет­ся не мень­ше, чем на 1. Ко­ли­че­ство шагов равно n − 1, а ито­го­вая раз­ность между M_n и m_n не пре­вос­хо­дит n − 1, зна­чит, на каж­дом шаге она растёт ровно на 1. От­сю­да сразу по­лу­ча­ет­ся, что для каж­до­го мно­же­ство со­сто­ит из не­ко­то­рых k по­сле­до­ва­тель­ных чисел из ин­тер­ва­ла 1, 2, 3, ..., n и A_k+1 по­лу­ча­ет­ся из него до­бав­ле­ни­ем числа, со­сед­не­го с этим ин­тер­ва­лом слева или спра­ва. Далее окон­ча­ние до­ка­за­тель­ства такое же, как в толь­ко что рас­смот­рен­ном.

Спо­соб IV. Ин­дук­ци­ей по n до­ка­жем, что для про­из­воль­но­го n ко­ли­че­ство за­бав­ных пе­ре­ста­но­вок равно 2ⁿ. База ин­дук­ции  — при n  =  1 и n  =  2 оно, оче­вид­но, равно 1  =  2⁰ и 2  =  2¹. Пусть для n чисел утвер­жде­ние верно, рас­смот­рим про­из­воль­ную за­бав­ную пе­ре­ста­нов­ку чисел 1, 2, 3, ..., n, n + 1. Пусть число n + 1 стоит на k-ом слева месте. Если спра­ва от n + 1 стоит не­ко­то­рое число m, то любое число l < m стоит пра­вее m, иначе m будет од­но­вре­мен­но мень­ше n + 1 и боль­ше l, сто­я­щих левее него, что на­ру­ша­ет усло­вие за­бав­но­сти. Пра­вее n + 1 стоят n − k + 1 чисел, мак­си­маль­ное из ко­то­рых не мень­ше n − k + 1, сле­до­ва­тель­но, пра­вее n + 1 стоят в точ­но­сти числа ..., 2, 1 в убы­ва­ю­щем по­ряд­ке. Тогда левее n + 1 в не­ко­то­ром по­ряд­ке рас­по­ло­же­но k − 1 число Оче­вид­но, что усло­вие за­бав­но­сти для них вы­пол­не­но, по­это­му они пред­став­ля­ют собой за­бав­ную пе­ре­ста­нов­ку k − 1 чисел. По пред­по­ло­же­нию ин­дук­ции, при число таких пе­ре­ста­но­вок равно 2^k − 2 числа пра­вее n + 1 рас­по­ла­га­ют­ся един­ствен­ным об­ра­зом, сле­до­ва­тель­но, ко­ли­че­ство за­бав­ных пе­ре­ста­но­вок n + 1 числа, в ко­то­рых n + 1 стоит на месте равно 2^k − 2 Кроме того, если в за­бав­ной пе­ре­ста­нов­ке число n + 1 стоит на пер­вом месте, то, как было по­ка­за­но, она равна Зна­чит, общее ко­ли­че­ство за­бав­ных пе­ре­ста­но­вок n + 1 числа равно сумме

что за­вер­ша­ет до­ка­за­тель­ство шага ин­дук­ции.