BdMO National Secondary 2020 P6

[Mursalin]

$(1, 2, 3, \cdots , n)$ সংখ্যাগুলোর একটা বিন্যাস $(a_1, a_2, a_3, \cdots , a_n)$-কে বিন্যস্ত-প্রায় বলা হবে যদি ঠিক একটা $i \in \{1, 2, 3, \cdots , n-1\}$ থাকে যার জন্য $a_i > a_{i+1}$ হয়। $(1, 2, 3, ... , 13)$ সংখ্যাগুলোর কতগুলো বিন্যস্ত-প্রায় বিন্যাস আছে?

A permutation $\left(a_1, a_2, a_3, \cdots , a_n\right)$ of the numbers $(1, 2, 3, \cdots , n)$ is called almost-sorted if there exists exactly one $i \in \{1, 2, 3, \cdots , n-1\}$ such that $a_i > a_{i+1}$. What is the number of almost-sorted permutations of the numbers $(1, 2, 3, ... , 13)$?

[Anindya Biswas]

An almost sorted permutation would look like this: (a sorted permutaion)-(suddenly a number which is less than the previous)-(again a sorted permutation). For example : $(1,3,5,2,4,6)$. Here $(1,3,5)$ was increasing, then the number $2$ is a sudden drop in that increasing pattern. Then again $(2,4,6)$ is increasing. From here, we can observe that we just have to partition the whole set $S=\{1,2,3,\dots,n\}$ into two ordered subsets $A$ and $B$ such that elements of $A$ are increasing and elements $B$ are increasing. But minimum element of $B$ is less than maximum element of $A$. Now choosing $A$ automatically forces to $B=S-A$. So the number of ways we can choose $A$ is the number of almost sorted permutations. Now $A$ cannot be the following sets cause in this cases, $min(B)>min(A)$ which is not permitted:
$\emptyset$,
$\{1\}$,
$\{1,2\}$,
$\dots$,
$\{1,2,3,4,\dots,n\}$
So, number of ways we can choose $A$ is $2^n-(n+1)$. In case of $n=13$, the number of almost sorted permutations is $2^{13}-14=8178$

[Mursalin]

Great solution! Other than that one typo (you want \(\min(B)>\max(A)\) instead of \(\min(B)>\min(A)\)), everything looks great. What is somewhat interesting is that you do not have to separately treat the cases when either \(A\) or \(B\) is empty if you use the convention that the minimum and the maximum of the empty set are \(\infty\) and \(-\infty\) respectively. So, neither \(A\) nor \(B\) can be empty since \(\min(B)<\max(A)\) breaks down in both these cases.

We also had an alternate solution that used recurrences. Let \([n]=\{1, 2, \cdots , n\}\) and \(T_n\) be the number of almost sorted permutations of \([n]\). You can extend an almost-sorted permutation of \([n-1]\) in exactly two ways by inserting \(n\) either at the end of the permutation or in between the two numbers that "create the descent". In addition, you can also start with the identity permutation of \([n-1]\) and insert \(n\) into any of the positions except the last one to get almost sorted permutations of \([n]\). These are the only ways of obtaining almost-sorted permutations of \([n]\) and so
\[T_n=2T_{n-1}+n-1\]
You can solve this recurrence using any technique of your choice (the method of summation factors for example) to get \(T_n=2^n-n-1\).