Question

در چند جایگشت از اعداد ۱ تا $n$ هیچ عددی بیش از دو واحد از عدد بعدی خودش بزرگ تر نیست.

Answer 1

برای هر جایگشت $1$ تا $n$ عدد $n+1$ سه حالت دارد . یا قبل از $n$ یا قبل از $n-1$ یا در آخر ردیف .

پس تعداد حالات مورد نظر برای $n+1$ سه برابر تعداد حالات مورد نظر برای $n$ میباشد به جز حالتی که $n-1$ وجود نداشته باشد یعنی $n$ برابر 1 باشد که در این صورت دو برابر خواهد شد :

$n=1$ ، تعداد حالات = 1

پس برای $n>1$ تعداد حالات برابر = $2*3^{n-2}$