How many permutations of the numbers $1,2,3, \ldots, n$ are there in which exactly

a) once,

b) twice it occurs that the number on the left is larger than the number on the right?
Solution. a) In the case of such permutations, the sequence is monotonically increasing up to a certain number, then there is a decrease, followed by another monotonically increasing part.

Divide the numbers into two sets, let these be the $x$ and $y$ sets. Arrange both $x$ and $y$ in increasing order, and finally write down the elements of $x$ followed by those of $y$.

The numbers can be divided into two sets in $\left(2^{n}\right)$ ways. Among these, the arrangements that do not satisfy the condition are those that are monotonically increasing throughout. This happens either when one of the sets is empty, or when the largest element of $x$ is smaller than the smallest element of $y$, i.e., when all elements of $x$ are smaller than all elements of $y$. (There will definitely not be a left-pointing relation within the sets, as we have sorted them.) In this case, the numbers from 1 to $k$ go into $x$, and the numbers from $(k+1)$ to $n$ go into $y$, where the smallest value of $k$ is 1 and the largest value is $n-1$. This represents $n-1$ possibilities. (This can also be calculated more simply, since writing the numbers from 1 to $n$ in sequence, there are $n+1$ places in front of and behind them from which to choose 1. If, for example, the one in front is chosen, then $x$ will be an empty set.)

Each such arrangement corresponds to a good permutation and vice versa.

Thus, the number of good permutations is $2^{n}-2-(n-1)=2^{n}-n-1$.

b) In this case, divide the numbers into three sets, $x$, $y$, and $z$, and after arranging the elements within the sets, write down the elements of $x$, $y$, and finally $z$ in sequence. The three sets can be created in $3^{n}$ ways.

From this, we need to subtract the bad arrangements, i.e., those in which there are 0 or 1 left-pointing relations in the permutation. (If $x$, $y$, or $z$ is an empty set, then there are 0 or 1 left-pointing relations.)

This can happen if every element in $x$ is smaller than every element in $y$, or if every element in $y$ is smaller than every element in $z$. Both cases can be considered as if the numbers were divided into two sets, the $A=x \cup y$ and $B=z$, or the $A=x$ and $B=y \cup z$ sets. The elements can be placed into the $A$ and $B$ sets in $2^{n}$ ways, and the "inner" set boundary can be drawn in $n+1$ places. Therefore, we need to subtract $2^{n}(n+1)$ from $3^{n}$. However, we subtracted twice the cases where it is simultaneously true that every element in $x$ is smaller than every element in $y$, and every element in $y$ is smaller than every element in $z$. So, the number of these cases must be added back once. In this case, two must be chosen from $n+1$ places, which is $\binom{n+1}{2}=\frac{(n+1) n}{2}$ cases. Thus, the solution is:

$$
3^{n}-2^{n}(n+1)+\frac{n(n+1)}{2}
$$

Remarks. 1. This problem is related to Problem A. 671.

2. In the solution, several people referred to a theorem from which the solution could be derived in one step. Based on the current Competition Bulletin, this was accepted, but from the 2016-2017 academic year, this will change.