# How many almost-perfect permutations are there?

A permutation $$\left(a_1, a_2, a_3, \cdots , a_n\right)$$ of the numbers $$(1, 2, 3, \cdots , n)$$ is called almost-perfect 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-perfect permutations of the numbers $$(1, 2, 3, ... , 11)$$?

The problem is from a mock contest. Here is my attempt in solving the problem:

I started by taking small values of $$i$$ and searched for a pattern. Here $$i$$ is a number for which $$a_i>a_{i+1}$$. For $$i=1$$, the first two numbers will be of the form $$(k,1)$$ where $$k\in \{2,3,\dots,n\}$$. Otherwise, there will be more than one pair $$(a_i,a_{i+1})$$ for which $$a_i>a_{i+1}$$. So, we have $$n-1$$ such permutations in this case.
For $$i=2$$, the first three numbers will be either of the form $$(1,k,2)$$ or of the form $$(2,k,1)$$ where $$k\in \{3,4,\dots,n\}$$. So, we have $$2(n-2)$$ almost-perfect permutations in this case.
For $$i=3$$, the first four numbers will be of the form $$(1,2,k,3)$$ or $$(1,3,k,2)$$ or $$(2,3,k,1)$$ where $$k\in\{4,5,\dots,n\}$$. So, we have $$3(n-3)$$ almost-perfect permutations in this case.
So, I claim that there are $$i(n-i)$$ almost-perfect permutations for each $$i$$. Thus, for $$n=11$$ we have a total of $$1(11-1)+2(11-2)+\dots+10(11-10)=220$$ almost-perfect permutations.

I'm not sure whether the above solution is correct or not. But I think this is not the best way to solve the problem. So, I'm looking for a better solution.

• Why (for $i=3$) they can't be in the form $(1,4,k,2)$? Commented Aug 7, 2021 at 18:50
• Wouldn't the set of numbers $(1, 2, 3, \cdots , n)$ be almost perfect if we just pick one of these $n$ numbers ($n$ ways) and misplace it from its initial position $(n-1)$ ways which can be done in total $n(n-1)$ ways. As such, there will be $110$ almost perfect permutations for the set of first $11$ natural numbers. Commented Aug 7, 2021 at 19:36

We assume $$i$$ is the term such that $$a_i > a_{i+1}$$.

Let $$A$$ be the set of numbers $$a_1,\dots,a_i$$. Note that $$A$$ completely determines the permutation, as it must be $$a_1 and then $$a_{i+1},\dots,a_{n}$$ must be the elements not in $$A$$ in increasing order.

The only thing that $$A$$ needs to satisfy is that its size is in the range $$[1,n-1]$$ and that its largest element is larger than the smallest element not in $$A$$, in other words we require that $$A$$ is not one of the $$n-1$$ intervals of the form $$\{1,\dots, i\}$$

Hence there are $$2^n-2 - (n-1)$$ options for $$A$$.