Arrange $1$, $2$, ... $n$ in ascending order with constraints Define permutation of set ${1,2,3, ....., n}$ to be sortable if upon cancelling one appropriate term of such permutation remaining $n$ – $1$ terms are in increasing order. If $f(n)$ is the number of such sortable permutations then $\frac{f(5)}{f(4)}$ equals.
I don't understand what to do in this question kindly help.
Below given is the solution can anyone explain why to subtract $n$-$1$ and add $1$.

 A: Consider the sequence:
$$S=1,2,3,4,...,n$$ Note that there are n blanks in the sequence
A random number is chosen and dropped in any one of the $n-1$ blanks so that it doesn't fall onto its original blank(Creating the sequence $S$)
(Say we have 1,2,3,4. Take 1 and drop it at third index(or blank), so that the new sequence is 2,3,1,4)
So total cases =
$$n(n-1)$$

Let us say you pick a number $t$. When you insert $t$ after $t+1$, we obtain a sequence, which is the same when you pick the number $t+1$ and place it before $t$.
There are $(n-1)$ such ordered pairs of the form $(t,t+1)$,  $t \ne n$
So total number of cases =
$$n(n-1)-(n-1)$$
Hey! We haven't counted the sequence $S$, have we?
Therefore
$$f(n)=n(n-1)-(n-1)+1$$
A: Explaining $f(n)$
$f(n)$ is the number of permutations $a_1,...,a_n$ with the following property : there is some index $1 \leq i \leq n$ so that when I remove $a_i$ from the sequence $a_1,...,a_n$, the rest of the terms are in increasing order.
For example, let us calculate all such permutations with $n=3$.

*

*$1,2,3$ satisfies it : if I remove $1$ then $2,3$ are in ascending order (but I could remove $2,3$ also, and this would hold).


*$1,3,2$ satisfies it : if I remove $3$ then $1,2$ are in ascending order.


*$2,1,3$ satisfies it : if I remove $1$, then $2,3$ are in ascending order.


*$2,3,1$ satisfies it : if I remove $1$ then $2,3$ are in ascending order.


*$3,1,2$ satisfies it : if I remove $3$, then $1,2$ are in ascending order.


*$3,2,1$ does not satisfy it : if I remove any guy I still can't get an increasing sequence!
And so, $f(n) = 5$. Indeed, $n^2-2n+2 = 5$, so the formula fits.

The solution is saying this : imagine a sequence of $n$ numbers following the condition. So there is a number, which when you strike out, the remaining numbers are in ascending order.
We start counting $f(n)$, by breaking this into counting $f_k(n)$ for $1 \leq k \leq n$. What is $f_k(n)$? Note that we strike out some number to create the increasing sequence, so $f_k(n)$ counts those permutations which give an increasing sequence when I strike $k$ out. What is left when I strike $k$ out? It is $1,2,...,k-1,k+1,...,n$, which are the sequences listed in the given answer.
For technical reasons, no $f_k(n)$ includes the identity permutation. So I'm going to count the identity permutation separately as part of the "$+1$" in the formula, as we will see later.
Take an example from above. $f_1(3)$ is $2$, because you have $2,1,3$ and $2,3,1$, where striking $1$ out gives an increasing sequence (remember, I'm leaving out the identity).
Similarly, $f_2(3)$ is $2$ from $2,1,3$ then $1,3,2$.
Finally $f_3(3)$ is $2$ as well , since $1,3,2$ and $3,1,2$ all come in together.
By now you would have realized the pattern : they are all the same. But the problem is that $\sum_{k=1}^n f_k(n) +1$ (accounting for the identity permutation) is not $f(n)$ : you noticed there were overlaps in the above : some sequences were counted twice.

For example, $2,1,3$ comes in both $f_2$ and $f_1$. Important : If I swapped $2$ and $1$ I get $1,2,3$.
Next, $1,3,2$ comes in both $f_3$ and $f_2$. Important : If I swapped $2$ and $3$ I get $1,2,3$.
$3,1,2$ comes only in $f_3$ : we will remark on this later.
These observations give us a claim which is stated as obvious in the answer, but which needs to be explained.

$n(n-1)$ term
So we must count the $f_k(n)$ first. For each $1 \leq k \leq n$, we will prove that $f_k(n)$ has size $n-1$. Indeed, following deletion of $k$ from a permutation in $f_k(n)$, the sequence $1,2,...,k-1,k+1,...,n$ is left behind. $k$ can be added anywhere in between each of the positions except its own (we don't want the identity permutation back) : so we get $n-1$ positions for $k$. Thus, each $f_k(n)$ has size $n-1$. Putting together all the $k$ values, we get $\sum_{k=1}^n f_k(n) = n(n-1)$.
$-(n-1)$ term
Next, we see the overlaps between the $f_k(n)$. For example, putting $3$ between $1,2$ gives $1,3,2$ but putting $2$ after $1,3$ still gives $1,3,2$ as well. So, the overlaps ensure that certain permutation are double counted.
We will find which permutations are double counted. Fix $1\leq k  \neq l \leq n$. We will find which permutations are common between $f_k$ and $f_l$.
Consider a permutation $P$ which lies in both $f_k$ and $f_l$. Suppose that $k<n$ ($l$ can be anything). Then we know that if we remove $k$ from $P$, we get $1,2,...,k-1,k+1,...,n$. So what does this mean? It means that in $P$, either $l$ is in the $l$th position (if $k$ comes before $l$ in $P$) or $l$ is in the $l-1$th position (if $k$ comes after $l$ in $P$).
But we know that $P$ is in $f_l$ as well, so removing $l$ we should get $1,2,...,l-1,l+1,...,n$ (note : if $l=n$ we don't get the $l+1,...$ part of course). If $l$ is in the $l$th position, then putting it back gives the permutation $1,2,...,l-2,l-1,l,l+1,...,n$ which is the identity permutation which we don't count. Ignoring this, if $l$ is in the $l-1$th position, then we must get $1,2,...,l-2,l,l-1,l+1,...,n$. Therefore, $P$ equals $1,2,...,l-2,l,l-1,l+1,...,n$. When does this permutation belong to $f_k$ as well?
This belongs to $k$ only if , when we remove $k$ we end up with $1,2,...,k-1,k+1,...,n$. But as you can see, if I don't remove either $l$ or $l-1$ from that sequence, I will certainly not get $1,2,...,k-1,k+1,...,n$ because not removing either of these two will keep the sequence from being non-increasing. So either $k=l$ or $k=l-1$.
Now, $k=l$ is absurd (there's no point of counting overlaps between $f_k$ and $f_l$ if $k=l$) so we conclude that the only possible overlaps that can occur are between $k$ and $k+1$ for $k=1,2,...,n-1$. Furthermore, only one permutation is in each overlap, which is of the form $1,2,...,k-1,k+1,k,...,n$ for $1 \leq k \leq n-1$. Removing these gives an $n-1$ removed. These are the only permutations, which produce overlaps in the $f_k$ count.
That gives a total of $n-1$ permutations to remove.
$+1$ term
Now we add the identity permutation, and that gives the $+1$ term.
All that leads to $f(n) = n(n-1) - (n-1) + 1$, and the answer follows.
