تعریف: یک جای‌گشت از اعداد ۱ تا $n$ ترتیبی از اعداد ۱ تا $n$ است که هرکدام از این اعداد دقیقاً یک بار در این ترتیب ظاهر شده است. ( مثلاً <۴٫۳٫۱٫۲> یک جای‌گشت از اعداد ۱ تا ۴ است).

بر روی جای‌گشت $P= <p_1,p_2,...,p_{2k},p_{2k+1>}$ از اعداد ۱ تا $2k+1$ تنها دو عمل زیر را می‌توانیم انجام دهیم:

چرخش سر: با حرف $s$ نمایش داده می‌شود که جای‌گشت $P$ را به جای‌گشت $<p_{2k},p_1,p_2,...,p_{2k-1},p_{2k+1>}$ تبدیل می‌کند.

چرخش دُم: با حرف $d$ نمایش داده می‌شود که جای‌گشت $P$ را به جای‌گشت $< p_1,p_{2k+1},p_2,p_3,...,p_{2k>}$ تبدیل می‌کند.

می‌خواهیم بدانیم با دو عمل بالا٬ چند تا از جای‌گشت‌های اعداد ۱ تا $2k+1$ را می‌توان مرتب کرد. برای مثال جای‌گشت <۴٫۲٫۱٫۳٫۵> (در این حالت $k$=۲ است) به صورت زیر مرتب می‌شود:

$$<۴٫۲٫۱٫۳٫۵> \underrightarrow{d} <۴٫۵٫۲٫۱٫۳> \underrightarrow{s} <۱٫۴٫۵٫۲٫۳> \underrightarrow{d} <۱٫۳٫۴٫۵٬۲> \underrightarrow{d} <۱٫۲٫۳٫۴٫۵>$$

تعداد جای‌گشت‌های قابل‌مرتب‌شدن را به صورت یک فرمول بر حسب $k$ به دست آورید. این فرمول را در بالای برگه‌ی جواب به صورت واضح بنویسید و سپس گفته‌ی خود را اثبات کنید.

• سوال بعد
• سوال قبل