The Cayley-Hamilton theorem states that every matrix $A$ satisfies its own characteristic polynomial; that is the polynomial for which the roots are the eigenvalues of the matrix:
$p(\lambda)=\det[A-\lambda\mathbb{I}]$.
If you view the polynomial:
$a^2-5a+6=0$,
as a characteristic polynomial with roots $a=2,3$, then any matrix with eigenvalues that are any combination of 2 or 3 will satisfy the matrix polynomial:
$A^2-5A+6\mathbb{I}=0$,
that is any matrix similar to:
$\begin{pmatrix}3 & 0\\ 0 & 3\end{pmatrix}$,$\begin{pmatrix}2 & 0\\ 0 & 2\end{pmatrix}$,$\begin{pmatrix}2 & 0\\ 0 & 3\end{pmatrix}$. Note:$\begin{pmatrix}3 & 0\\ 0 & 2\end{pmatrix}$ is similar to $\begin{pmatrix}2 & 0\\ 0 & 3\end{pmatrix}$.
To see why this is true, imagine $A$ is diagonalized by some matrix $S$ to give a diagonal matrix $D$ containing the eigenvalues $D_{i,i}=e_i$, $i=1..n$, that is:
$A=SDS^{-1}$, $SS^{-1}=\mathbb{I}$.
This implies:
$A^2-5A+6\mathbb{I}=0$,
$SDS^{-1}SDS^{-1}-5SDS^{-1}+6\mathbb{I}=0$,
$S^{-1}\left(SD^2S^{-1}-5SDS^{-1}+6\mathbb{I}\right)S=0$,
$D^2-5D+6\mathbb{I}=0$,
and because $D$ is diagonal, for this to hold each diagonal entry of $D$ must satisfy this polynomial:
$D_{i,i}^2-5D_{i,i}+6=0$,
but the diagonal entries are the eigenvalues of $A$ and thus it follows that the polynomial is satisfied by $A$ iff the polynomial is satisfied by the eigenvalues of $A$.
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$.
Best Answer
Let $A=[x_{i,j}]$ Then we get
$$x_{1,1} +2 x_{2,1} +4 x_{3,1} = 3$$
$$ x_{1,2} + 2x_{2,2} + 4 x_{3,2} = 2 $$
$$x_{1,3} + 2 x_{2,3} + 4 x_{3,3} = 1$$
We shall count the number of solutions for each equation.
First equation has 2 solutions: Since $4>3$ we have that $x_{3,1}=0$. Similarly $x_{2,1}<2$. If $x_{2,1}=1$ then $x_{1,1}=1$ and if $x_{2,1}=0$ then $x_{1,1}=3$. Therefore there are two solutions for the first equation.
Second equation has 2 solutions: As before, $x_{3,2}=0$. Also $x_{2,2}$ is at most $1$, hence if $x_{2,2}=1$ then $x_{1,2}=0$ and if not then $x_{2,2}=0$ and $x_{1,2}=1$.
Third equation has 1 solution: $4,2>1$ so $x_{2,3},x_{3,3}=0$ and so the only solution is $x_{1,3}=1$.
Therefore there is a total of $4$ solutions for all of the equations.
$$A_1 =\begin{bmatrix} 3 & 0 &1 \\ 0 & 1 & 0 \\ 0 & 0 & 0\end{bmatrix}, A_2=\begin{bmatrix} 1 & 0 &1 \\ 1 & 1 & 0 \\ 0 & 0 & 0\end{bmatrix}$$ $$A_3 =\begin{bmatrix} 3 & 2 &1 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{bmatrix}, A_4=\begin{bmatrix} 1 & 2 &1 \\ 1 & 0 & 0 \\ 0 & 0 & 0\end{bmatrix}$$