This follows from the inverse Girard-Waring formula and Cayley-Hamilton theorem.
Consider a polynomial $x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n$. Let $\lambda_1,\ldots,\lambda_n$ be its zeroes and $s_k=\lambda_1^k+\cdots+\lambda_n^k$ be their $k$-th power sum. There are three well-known sets of identities relating the elementary symmetric polynomials to the power sums, namely, Newton’s identities, Girard-Waring formula, and the inverse Girard-Waring formula. In particular, the inverse Girard-Waring formula expresses each $a_j$ in terms of the $s_i$s:
$$
a_j=\sum_{\substack{k_1,\ldots,k_j\ge0\\ k_1+2k_2+\cdots+jk_j=j}}(-1)^{k_1+\cdots+k_j}\frac{1}{k_1!\cdots k_n!}\left(\frac{s_1}{1}\right)^{k_1}\cdots \left(\frac{s_j}{j}\right)^{k_j}.\tag{1}
$$
In case the polynomial is the characteristic polynomial of an $n\times n$ matrix $A$, Cayley-Hamilton theorem states that $A^n+a_1A^{n-1}+\cdots+a_{n-1}A+a_nI=0$. Therefore $A(A^{n-1}+a_1A^{n-2}+\cdots+a_{n-1}I)=-a_nI$ and
$$
A^{-1}=-\frac{1}{a_n}(A^{n-1}+a_1A^{n-2}+\cdots+a_{n-1}I).\tag{2}
$$
Substitute the RHS of $(1)$ into $(2)$ with $s_i=\operatorname{tr}(A^i)$, we obtain the inversion formula in your question.
E.g. when $n=3$, the constraint $s+\sum_{l=1}^{n-1}lk_{l}=n-1$ becomes $k_1+2k_2=n-1-s=2-s$. That is,
\begin{cases}
s=0: k_1+2k_2=2 \implies (k_1,k_2)=(0,1),(2,0);\\
s=1: k_1+2k_2=1 \implies (k_1,k_2)=(1,0);\\
s=2: k_1=k_2=0.
\end{cases}
In particular, for $s=0$, we have
\begin{align*}
&\sum_{\substack{k_1,\ldots,k_{n-1}\ge0\\ s+\sum_{l=1}^{n-1}lk_{l}=n-1}} \prod_{l=1}^{n-1} \frac{(-1)^{k_{l}+1}}{l^{k_{l}} k_{l}!}\operatorname{tr}(A^{l})^{k_{l}}
=\sum_{(k_1,k_2)\in\{(0,1),(2,0)\}} \prod_{l=1}^{n-1} \frac{(-1)^{k_{l}+1}}{l^{k_{l}} k_{l}!}\operatorname{tr}(A^{l})^{k_{l}}\\
&=
\left(\frac{(-1)^{0+1}}{1^{0} 0!}\operatorname{tr}(A^{1})^{0}\right)
\left(\frac{(-1)^{1+1}}{2^{1} 1!}\operatorname{tr}(A^{2})^{1}\right)
+
\left(\frac{(-1)^{2+1}}{1^{2} 2!}\operatorname{tr}(A^{1})^{2}\right)
\left(\frac{(-1)^{0+1}}{2^{0} 0!}\operatorname{tr}(A^{2})^{0}\right)\\
&=\frac{\operatorname{tr}(A)^2-\operatorname{tr}(A^2)}{2}.
\end{align*}
Ultimately, we get
$$
A^{-1}=\frac{1}{\det A}\left(
A^2-\operatorname{tr}(A)A+\frac{\operatorname{tr}(A)^2-\operatorname{tr}(A^2)}{2}I
\right).
$$
In your case,
$$
A=\begin{bmatrix}1 & 0 & 4\\0 & 1 & 2\\0 & -3 & -4\end{bmatrix}
\implies
A^{-1}=\frac{1}{2}\left(A^2+2A-I\right)
=\begin{bmatrix}1&-6&-2\\ 0&-2&-1\\ 0&\frac32&\frac12\end{bmatrix}.
$$
