6

This is a quick follow up on R. Stanley's interesting post on MO in a different direction, which might be easier.

For positive integers $a$, define the family of functions (infinite series) given by $$F_a(x)=\sum_{n\geq0}a^{\binom{n+1}2}\frac{x^n}{n!}.$$ Then, $F_2(x)$ becomes Stanley's $F(x)$.

QUESTION. Is it true that the coefficients of $\sqrt[a]{F_a(x)}$ are all positive integers, as an exponential generating function?

T. Amdeberhan
  • 41,802
  • 8
    In fact, we can let $a$ be an indeterminate, and the coefficient of $x^n/n!$ in $\sqrt[a]{F_a(x)}$ will be a polynomial with integer coefficients. This is because $a^{{n+1\choose 2}}$ counts graphs with edges colored with $a$ colors (including the color 0, which denotes no edge). Thus the number $c_a(n)$ of connected such graphs on $n\geq 1$ vertices is a polynomial in $a$ with integer coefficients and is divisible by $a$. Thus the coefficient of $\frac{x^n}{n!}$ in $\exp \frac{1}{a}c_a(n)\frac{x^n}{n!}=\sqrt[a]{F_a(x)}$ is a polynomial in $a$ with integer coefficients. – Richard Stanley Mar 01 '21 at 23:57
  • @RichardStanley: It would be nice if you could put this as an answer so that your cute argument won't be buried here. It is instructional to readers. – T. Amdeberhan Mar 02 '21 at 15:18
  • I have done as you suggested. – Richard Stanley Mar 03 '21 at 00:50

1 Answers1

7

In fact, we can let $a$ be an indeterminate, and the coefficient of $x^n/n!$ in $\sqrt[a]{F_a(x)}$ will be a polynomial with integer coefficients. This is because $a^{{n+1\choose 2}}$ counts graphs with edges colored with $a$ colors (including the color 0, which denotes no edge). Thus the number $c_a(n)$ of connected such graphs on $n≥1$ vertices is a polynomial in $a$ with integer coefficients and is divisible by $a$. Hence the coefficient of $\frac{x^n}{n!}$ in $\exp \frac 1a\sum_{n\geq 1}c_a(n)\frac{x^n}{n!}$ is a polynomial in $a$ with integer coefficients.

Addendum. Let me explain why $c_a(n)$ is divisible by $a$. Let $G$ be a connected graph on $n$ vertices with no loops. If $G$ has $q$ edges, then there are $(a-1)^q$ ways to color them. (The nonedges, corresponding to the color 0, are already determined by $G$.) At each vertex we are free to add a loop or not without affecting connectedness. If we add a loop, we can color it in $a-1$ ways, so $a$ possibilities in all for each vertex. Hence the total number of coloring of all graphs obtained from $G$ by adding loops is $(a-1)^q a^n$. This is divisible by $a$ (since $n\geq 1$), and summing over all $G$ without loops will therefore give a polynomial divisible by $a$, as claimed.

Now note that if $n\geq 2$, then $q\geq 1$ so $(a-1)^q a^n$ is divisible by $a^2(a-1)$. Hence $$ \exp \frac 1a\sum_{n\geq 1}c_a(n)\frac{x^n}{n!} = \exp\left( x+\sum_{n\geq 2}a(a-1)d_a(n)\frac{x^n}{n!}\right), $$ for some $d_a(n)\in\mathbb{Z}[a]$. Taking this modulo $a(a-1)$ gives $e^x=\sum_{m\geq 0}\frac{x^m}{m!}$. It follows that the conjecture in OEIS A178319 mentioned in the comment by Max Alekseyev is true.

Richard Stanley
  • 49,238
  • 1
    There is a conjecture in OEIS A178319 that the coefficient of $\frac{x^n}{n!}$ in $\exp \frac 1a\sum_{n\geq 1}c_a(n)\frac{x^n}{n!}$ is congruent to $1$ modulo $a(a-1)$ for all $n\geq 0$. Can it be seen from the given interpretation? – Max Alekseyev Mar 14 '21 at 18:49
  • You can get $(a-1)^q a^n$ more easily by starting with the $(a-1)^q$ colorings without loops and then at each of the $n$ vertices adding a loop in any of the $a$ colors, where color $0$ corresponds to no loop. – Ira Gessel Mar 15 '21 at 06:04
  • @IraGessel: yes, I also realized this after posting my answer. I have revised the text accordingly. – Richard Stanley Mar 15 '21 at 16:04