3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ (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? $\endgroup$
    – esg
    Commented Mar 8, 2022 at 19:12
  • $\begingroup$ 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? $\endgroup$ Commented Mar 9, 2022 at 13:13
  • $\begingroup$ 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. $\endgroup$
    – esg
    Commented Mar 9, 2022 at 18:02
  • $\begingroup$ 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. $\endgroup$ Commented Mar 10, 2022 at 12:56
  • $\begingroup$ 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. $\endgroup$
    – esg
    Commented Mar 10, 2022 at 20:39

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.