What is the closed form of $\dfrac{1}{s!}\text{trace}(\mathbf{A}_n^s)$?
Where $\mathbf{A}_n\in\{0,1\}^{n\times n}$ is a generic adjacency matrix of an undirected graph and $s\in\mathbb{N}$
$\mathbf{A}_n=(a_{ij})_{ij}=\begin{cases}0&\text{if }i=j\\1\text{ or }0&\text{if }i\neq j\end{cases}\qquad$ and $\mathbf{A}_n^{\top}=\mathbf{A}_n$
I found this pattern for $s=3$: $$\mathbf{A}_3=\begin{pmatrix} 0&a_{12}&a_{13}\\ a_{12}&0&a_{23}\\ a_{13}&a_{23}&0\\ \end{pmatrix}$$
$$\frac{1}{6}\text{trace}(\mathbf{A}_3^3)=a_{12} a_{13} a_{23}$$
$$\mathbf{A}_4=\begin{pmatrix} 0&a_{12}&a_{13}&a_{14}\\ a_{12}&0&a_{23}&a_{24}\\ a_{13}&a_{23}&0&a_{34}\\ a_{14}&a_{24}&a_{34}&0 \end{pmatrix}$$ $$\frac{1}{6}\text{trace}(\mathbf{A}_4^3)=a_{12} a_{13} a_{23} + a_{12} a_{14} a_{24} + a_{13} a_{14} a_{34} + a_{23} a_{24} a_{34}=\frac{1}{6}\text{trace}(\mathbf{A}_3^3)+ a_{12} a_{14} a_{24} + a_{13} a_{14} a_{34} + a_{23} a_{24} a_{34}$$
$$\mathbf{A}_5=\begin{pmatrix} 0&a_{12}&a_{13}&a_{14}&a_{15}\\ a_{12}&0&a_{23}&a_{24}&a_{25}\\ a_{13}&a_{23}&0&a_{34}&a_{35}\\ a_{14}&a_{24}&a_{34}&0&a_{45}\\ a_{15}&a_{25}&a_{35}&a_{45}&0 \end{pmatrix}$$
$$\frac{1}{6}\text{trace}(\mathbf{A}_5^3)=a_{12} a_{13} a_{23} + a_{12} a_{14} a_{24} + a_{12} a_{15} a_{25} + a_{13} a_{14} a_{34} + a_{13} a_{15} a_{35}+...\\ a_{14}a_{15}a_{45}+a_{23} a_{24} a_{34} + a_{23} a_{25} a_{35} + a_{24} a_{25} a_{45} + a_{34} a_{35} a_{45}$$ $$\frac{1}{6}\text{trace}(\mathbf{A}_5^3)=\frac{1}{6}\text{trace}(\mathbf{A}_4^3)+ a_{12} a_{15} a_{25} + a_{13} a_{15} a_{35}+ a_{14}a_{15}a_{45} + a_{23} a_{25} a_{35} + a_{24} a_{25} a_{45}+ a_{34} a_{35} a_{45}$$
So in general
$$\frac{1}{6}\text{trace}(\mathbf{A}_{n}^{3})=\frac{1}{6}\text{trace}(\mathbf{A}_{n-1}^{3})+\sum_{1\leq i< j<n}a_{ij}a_{in}a_{jn}$$
I concluded that:
$$\frac{1}{6}\text{trace}(\mathbf{A}_n^3)=\sum_{k=3}^{n}\sum_{1\leq i< j<k}a_{ij}a_{ik}a_{jk}$$
Is it correct?
Note that $k=3,...,n$ because $\dfrac{1}{6}\text{trace}(\mathbf{A}_1^3)=\dfrac{1}{6}\text{trace}(\mathbf{A}_2^3)=0$
Easier to notice was the case for $s=2$:
$$\frac{1}{2}\text{trace}(\mathbf{A}_n^2)=\sum_{1\leq i<j\leq n}a_{ij}^2$$
The problems start for $s\geq 4$, is there any formula to calculate it in an "efficient" way (I have to apply it to a program in C++ language)
Technically for $s=2$ I have the number of edges, for $s=3$ I have the number of triangles
Is it correct that for $s=N$ I have the number of $N$-gon?