How many permutations of $\{1,2,3,4,5,6\}$ are there, when the difference between the number and his position in the permutation can be 2 at max? for example: $213654$ is okay because
$2-1 = 1 \leq 2,$
$|1-2| = 1 \leq 2$
$ 3-3 = 0,$
$ 6-4 = 2\le2$ PS: repetition isn't allowed
The problem can be reformulated as the number of ways to place 6 non-attacking rooks on a restricted chessboard, shown above. There can be only one rook in each row and column, and no rook may be placed in a grey square. For example, $1$ may be placed in positions 1,2, or 3 of the permutation, but may not be placed in positions 4,5,or 6; the allowed positions correspond to the white squares in the first column of the board.
We apply the method of Rook Polynomials.
The rook polynomial of the six grey squares in the lower left is, by inspection, $$f(x) = 1 + 6x + 7 x^2 + x^3$$ What this polynomial denotes is that there are $6$ ways to place one rook on the grey squares, $7$ ways to place two non-attacking rooks, and $1$ way to place three non-attacking rooks.
Since the restricted squares in the lower left and the restricted squares in the upper right have no row or column in common, the rook polynomial of the restricted board is $$R(x) = (f(x))^2 = 1+12x+50x^2+86x^3+61x^4+14x^5+x^6$$ What this means is that there are $12$ ways to place one rook on the restricted board, $50$ ways to place two rooks, $86$ ways to place three rooks, ... , $1$ way to place $6$ rooks. By the principle of inclusion and exclusion, the number of ways to place 6 non-attacking rooks on the unrestricted board (the white squares) is $$1 \times 6! - 12 \times 5! + 50 \times 4! - 86 \times 3! + 61 \times 2! -14 \times 1! +1 \times 0! = \boxed{73}$$