برای هر جایگشت $1$ تا $n$ عدد $n+1$ سه حالت دارد . یا قبل از $n$ یا قبل از $n-1$ یا در آخر ردیف .
پس تعداد حالات مورد نظر برای $n+1$ سه برابر تعداد حالات مورد نظر برای $n$ میباشد به جز حالتی که $n-1$ وجود نداشته باشد یعنی $n$ برابر 1 باشد که در این صورت دو برابر خواهد شد :
$n=1$ ، تعداد حالات = 1
پس برای $n>1$ تعداد حالات برابر = $2*3^{n-2} $
