# Better solution for an evaluation over a fully connected, symmetric tensor network graph?

I have a somewhat nice approach to the following symmetric network evaluation problem. However, since the result is a possibly elaborate combinatorial problem, that I can not yet solve (edit: which however has been answered now!), I am wondering if there may be an easier solution.

Problem:

Let $$G = (V,E)$$, $$V = \{1,\ldots,d\}$$, be the fully connected graph with $$d$$ vertices, whereby each the number of edges in $$E_v = \{ \{v,w\} \mid v \neq w \in V \} \subset E$$ is $$|E_v| = d - 1$$.

We want to evaluate $$x = \sum_{i_e \ : \ e \in E } \ \prod_{v \in V} \ T(\{i_e\}_{e \in E_v}), \quad T(a_1,\ldots,a_{d-1}) := \sum_{j = 1}^{d-1} a_j$$ where each the range of the indices is $$i_e = 1,\ldots,r$$ for a fixed $$r \in \mathbb{N}$$. There is also interest in more complicated functions (or tensors) $$T$$, that is, for approaches that might work more generally, but this is not explicitly considered in the following.

Solution:

Let $$m_j$$ for $$j = 1,\ldots,(d-1)^d$$ be the monomials of order $$d$$ that appear in the polynomial $$p := \prod_{v \in V} \ \sum_{e \in E_v} i_e \in \mathbb{R}([i_e]_{e \in E}).$$ Thus, we have $$x = \sum_{i_e \ : \ e \in E } p = \sum_{i_e \ : \ e \in E } \sum_{j = 1}^{(d-1)^d} m_j$$. As each $$m_j$$ results of the choices of $$e \in E_v$$ for $$v \in V$$, we can encode the monomials via all endofunctions $$f_j: V \rightarrow V$$ without fixed points. In explicit, we set $$m_j = \prod_{v \in V} i_{\{v,f_j(v)\}}.$$ For each $$j$$, let $$C_j := \{ v \in V \mid f_j^2(v) = v\}$$ denote the elements that form two-cycles of $$f_j$$. Then $$i_e^2$$ is a factor of $$m_j$$ iff $$e = \{v,w\}$$ for $$v,w \in C_j$$. Further, $$|E| - d + |C_j|/2$$ many different $$i_e$$ do not appear in $$m_j$$. Thus, we can simplify $$\sum_{i_e \ : \ e \in E } m_j = r^{|E| - d + |C_j|/2} \prod_{v \in C_j,\ v < f(v)} \sum_{i_{\{v,f(v)\}} = 1}^r i_{\{v,f(v)\}}^2 \prod_{v \in V \setminus C_j} \sum_{i_{\{v,f(v)\}} = 1}^r i_{\{v,f(v)\}} = r^{|E| - d + |C_j|/2} (\sum_{\ell = 1}^r \ell^2)^{|C_j|/2} (\sum_{\ell = 1}^r \ell)^{d-C_j}.$$ So the only thing that remains is to count each the number $$N_{d,k}$$ of endofunctions $$g: V \rightarrow V$$ without fixed points that have exactly $$k$$ two-cycles (that is, for which the according set $$C$$ were to have $$2k$$ elements). With $$s_2 := \sum_{\ell} \ell^2$$ and $$s_1 := \sum_{\ell} \ell$$, we then end up with $$x = \sum_{k \in \mathbb{N}_0 \ : \ 2k < d} |N_{d,k}| \cdot r^{|E| - d + k} s_2^k s_1^{d-2k}.$$ Should you happen to know the answer to the combinatorial problem, it would help me a lot if you took a look at the corresponding question.

Edit:

Fortunately, the combinatorial question was quickly answered (and its answer turned out to be shorter than I first thought)! So the solution above might still not be the best, but it is enough to provide an explicit, quite easily evaluable formula for the result $$x$$. This also allowed to numerically verify that the derivation is indeed correct.

• (I think) your sum can be simplified using generating functions. It can be shown that $N_{d,k}=d! [y^dt^k] e^{(d-1)y+(t-1)\frac{y^2}{2}}$ and that consequently your $x$ can be expressed as $$x=r^{|E|} d! [y^d] e^{(d-1)\frac{s_1}{r}y+\big(\frac{s_2}{r}-\frac{s_1^2}{r^2}\big)\frac{y^2}{2}}$$ (essentially a Hermite polynomial evaluated at an imaginary argument). Is that of interest or are you content with what you have?
– esg
Commented Mar 8, 2022 at 19:12
• The sought coefficient is the one of $y^d t^k$? So $[a^i b^j] a^i b^j = 1$? (I am not familiar with the notation). Would be interesting to see the derivation of this way to write $N_{d,k}$. Does the formula for $x$ then follow directly? Commented Mar 9, 2022 at 13:13
• Your interpretation of the "coefficient operator" is correct. The first formula follows in a (more or less) routine way from the known generating function of the cycle type of (uniform) self mappings of $[n]$, the formula for $x$ then only needs basic properties of coefficient extraction.
– esg
Commented Mar 9, 2022 at 18:02
• This may be much to ask (and I have yet to look into it myself), but do you see any indication that generating functions might yield an easier approach for, say, $T(a_1,\ldots,a_{d-1}) = (\sum_{j=1}^{d-1} a_j)^2$? Just in case you are interested. Its nothing urgent. Commented Mar 10, 2022 at 12:56
• It is quite conceivable that similar structures as above appear also for more complicate $T$ -functions (but that is only a guess). If the final sums can be expressed via cycle counts generating functions might simplify a lot.
– esg
Commented Mar 10, 2022 at 20:39

Here is a (formal) generating function treatment of $$N_{d,k}$$, resp. of your final sum above. Let $$T(z)$$ (the tree function'') denote the (formal) power series $$T(z)=\sum_{n\geq 1}\frac{n^{n-1}}{n!}z^n$$.
The joint generating function for the cycle counts in a (uniform) self-mapping of $$[n]$$ is known: \begin{align*} g(t_1,\ldots,t_n)=n![z^n]\exp\Big(\sum_{i=1}^n t_i\frac{T(z)^i}{i}\Big) \end{align*} (that is, the coefficient $$[t^{k_1}\ldots t^{k_n}]$$ of $$g(t_1,\ldots,t_n)$$ is the number of self-mappings whose functional digraph has $$k_i$$ cycles of length $$i$$, $$i=1,\ldots, n$$ ). Hence the generating function $$h_n(t)=\sum_{k\geq 0} N_{n,k}t^k$$ of the numbers $$N_{n,k}$$ is \begin{align*} h_n(t)&=n![z^n] \exp\Big(t\frac{T(z)^2}{2}+\sum_{i=3}^n \frac{T(z)^i}{i}\Big)\\ &=n![z^n]\exp\Big(-T(z) +(t-1)\frac{T(z)^2}{2}+\sum_{i\geq 1}\frac{T(z)^i}{i}\Big)\\ &=n![z^n]\frac{\exp\Big(-T(z) +(t-1)\frac{T(z)^2}{2}\Big)}{1-T(z)} \end{align*}
Now, it is well known that $$T(z)$$ is the formal power series satisfying $$T(z)=z\,e^{T(z)}$$, and that for a formal power series $$F$$ the coefficients of $$G(z):=F(T(z))$$ are given by (Lagrange inversion)
$$[z^0]G(z)=[z^0] F(z) \mbox{ , } [z^k]G(z)=\tfrac{1}{k} [y^{k-1}] F^\prime(y)\,e^{ky} =[y^k](1-y)F(y)\,e^{ky}\mbox{ for } k\geq 1\;.$$
Thus \begin{align*} h_n(t)=n! [y^n] \exp\Big((n-1)y+(t-1)\frac{y^2}{2}\Big) \end{align*} Note that $$h_n(t)$$ is a polynomial of degree $$\lfloor \frac{n}{2}\rfloor$$.
Now $$x=r^{|E|}\frac{s_1^d}{r^d}\,h_d(\frac{rs_2}{s_1^2})$$ and the representation \begin{align*} x=r^{|E|} d! [y^d] \exp\Big({(d-1)\frac{s_1}{r}y+\big(\frac{s_2}{r}-\frac{s_1^2}{r^2}\big)\frac{y^2}{2}}\Big) \end{align*} follows easily. From a combinatorial view this gives essentially all you want to know about $$x$$.