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

Question

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.

Answer 1

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