====== مرتب‌سازی ======


یک جدول $1\times (n+1)$ را در نظر بگیرید که در آن اعداد ۱ تا $n$‌هرکدام یک بار آمده است و یک خانه از آن هم خالی است. در هر جابه‌جایی می‌توانیم یک عدد جدول را به خانه‌ی خالی ببریم.  هدف این است که با تکرار عمل جابه‌جایی در نهایت جدول مرتب شود. یک جدول مرتب شده است اگر در آن، برای هر $i<j$، عدد $i$ قبل از $j$‌آمده باشد و خانه‌ی خالی هم در مکان $n+1$ ام قرار گرفته باشد (در حقیقت عدد $i$ در خانه‌ی $i$ قرار می‌گیرد). مثلا در شکل زیر، پس از ۲ بار جابه‌جایی جدول مرتب شده است.


{{ :سوالات_المپیاد:مرحله‌ی_دوم:دوره‌ی_۱۰:7.png |}}


حداکثر تعداد عمل جابه‌جایی که لازم است تا بتوان هر حالت ممکن از جدول $1\times (n+1)$ را مرتب کرد را بر حسب $n$‌به‌دست آورید و ادعای خود را ثابت کنید. برای مثال اگر $n=2$، هر حالت ممکن را می‌توان با حداکثر ۲ بار جابه‌جایی مرتب کرد.

  * [[سوال ۸|سوال بعد]]
  * [[سوال ۶|سوال قبل]]