I want to know, for an $n\times n$ permutation matrix, how many matrices are there such that there are exactly $3$ entries above the diagonal.
For example, there is only one $4\times 4$ matrix that satisfies the above condition:
$\begin{pmatrix} 0&\textbf{1}&0&0 \\ 0&0&\textbf{1}&0\\ 0&0&0&\textbf{1}\\ 1&0&0&0\end{pmatrix}$
If I didn't count wrongly, I think there are $22$ combinations for $5\times 5$ permutation matrices. Another example would be:
$\begin{pmatrix} 0&0&\textbf{1}&0&0 \\ 0&0&0&\textbf{1}&0\\ 1&0&0&0&0\\ 0&0&0&0&\textbf{1}\\ 0&1&0&0&0\end{pmatrix}$
I can't think of a way to do it because choosing different entry $a_{ij}$ to be $1$ will result in different number of choices left.
Extra question: how many combinations for $k$ entries above the diagonal for $n\times n$ permutation matrices? (For $n> k$)
Edit: Also someone suggested using recurrence relations, but I don't see a way to extend the $4\times 4$ case to $5\times 5$ case?
Best Answer
You're looking for the number of permutations $\pi$ in which $\pi(i)\gt i$ for $k$ values of $i$. Let's call such a value of $i$ a raise. I'll show that the number of permutations of $[n]$ with $k$ raises is equal to the number of permutations of $[n]$ with $k$ ascents, where an ascent is a value of $i$ for which $\pi(i+1)\gt\pi(i)$. This is the Eulerian number $A(n,k)$.
To show that these numbers are the same I'll exhibit a bijection between the permutations with $k$ raises and the permutations with $k$ ascents. Consider the cycle representation of a permutation with $k$ raises. Write each cycle with its greatest entry last, concatenate the cycles, ordered by decreasing greatest entry, and interpret the resulting sequence as the one-line notation of a permutation.
This permutation has as many ascents as the original permutation had raises, since there are no ascents or raises across the cycle borders, and within cycles ascents and raises coincide. Moreover, every one-line notation of a permutation can be decoded into a unique cycle representation by starting from the end and starting a new cycle if an entry is the greatest encountered so far.
The bijection shows that the numbers you want are the Eulerian numbers, OEIS sequence A008292 and in particular the numbers $A(n,3)$, OEIS sequence A000498, which gives a closed form:
$$ A(n,3)=4^n-(n+1)3^n+\frac12n(n+1)2^n-\frac16(n-1)n(n+1)\;. $$
It seems you miscounted for $n=5$, as $A(5,3)=26$.