How many combinations of permutation matrices are there?

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?

• There may be a recurrence relation you can find. – Soham Chowdhury Mar 19 '16 at 5:59
• This should be the disjoint union of the following, the number of ways to build 3 strictly increasing orderings of size at least 2, or the number of ways to make one of size at least 2, and two whose total size is at least 3, or 3 whose total size is at least 4. This can be seen by recognizing that permutations must have cycles, and those cycles must loop back in one place, so split into possible double backings. The EGF for an increasing ordering should be just e^x – Jason Carr Mar 19 '16 at 6:34
• @JasonCarr im sorry I dont understand what you mean by "strictly increasing orderings"? I also don't know much about generating functions. Mind explaining? – lEm Mar 19 '16 at 6:44
• In effect I mainly just mean a set. Imagine we have our elements as numbers, 12345. What i mean is we have an ordering of some elements like 145, but not 142. It's not really an ordering and I think it was bad wording on my part. It's basically a set of elements, which we can then order naturally. Generating functions are hard to explain in a short space here, but basically we have an infinite sum of x^n s times coefficients, and they compose and multiply nicely – Jason Carr Mar 19 '16 at 7:02
• @JasonCarr Thanks for the reply, I see what you mean there. In fact the original question is about how many functions $f:A\to A$, where $A$ is the set of the first $n$ positive integers such that, the cardinality of the set of $k$ such that $k>f(k)$ is exactly $3$. But I think it would be hard to generalize it for the $n$ case – lEm Mar 19 '16 at 7:17

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$.

• Thank you a lot! I understand it now – lEm Mar 20 '16 at 3:55