دنبالهیی از اعداد ۱ تا ۹ داده شده است. روی این دنباله الگوریتم زیر را انجام میدهیم. ابتدا ۳ عنصر اول دنباله را مرتب میکنیم. بعد از آن عناصر سوم و چهارم و پنجم را مرتب میکنیم. بعد عناصر پنجم و ششم و هفتم و در نهایت عناصر هفتم و هشتم و نهم را مرتب میکنیم. برای چه تعداد از جایگشتهای اعداد یک تا نه دنبالهای که با این روش بهدست میآید، مرتب است؟
پاسخ
گزینه (۴) درست است.
معلوم است که باید در مرحلهی اول دو خانه از سه خانهی $A$ اعداد ۱ و ۲ باشند که تعداد طرق جا دادن آن دو رقم در سه خانهی مورد اشاره $\binom{3}{2} \times2!$؛ یعنی ۶ میباشد. در مرحلهی دوم توجه داریم که در خانهی خالی $A$ و دو خانهی سمت راست $B$ باید دو عدد ۳ و ۴ موجود باشند که تعداد طرق جا دادن آ دو رقم در سه خانهی مورد اشاره نیز برابر ۶ میباشد. در مرحلهی سوم میفهمیم که در خانهی خالی باقیمانده از مراحل قبلی و دو خانهی سمت راست $C$ باید دو عدد ۵ و ۶ موجود باشند که تعداد طرق جا دادن آن دو رقم در سه خانهی مورد اشاره نیز برابر ۶ میباشد. در مرحلهی آخر سه خانهی خالی میماند که باید سه عدد ۸٬۷ و ۹ را در آن سه خانه قرار دهیم که این عمل نیز به ۶ طریق ممکن است. بنابراین تعداد کل حالات برابر $6^4$ یعنی ۱۲۹۶ میباشد.