# Types of generating functions (ordinary, exponential, ???) closed under substitution

A nice feature of ordinary and exponential generating functions is that they are closed under substitution: if $$F(z)$$ and $$G(z)$$ both have integer coefficients, then $$F(G(z))$$ also has integer coefficients.

So, for which sequences $$a_n$$ are the coefficients of $$F(G(z))$$ integer multiples of $$1/a_n$$, where $$F(z)=\sum f_n z^n/a_n$$, $$G(z)=\sum g_n z^n/a_n$$ and $$f_n$$ and $$g_n$$ are integer sequences?

I know of $$a_n = x^{n-1}$$ and $$a_n = x^{n-1} n!$$ (but I do not know of any applications of these either).

Update: thanks to Alexander Burstein's comment and Oleksandr Kulkov's answer, I now have a vast supply of such sequences, two of which I find particularly interesting:

• $$a_n = (n-1)!$$
• $$a_n = \phi(1)\dots\phi(n-1)$$, where $$\phi$$ is Euler's totient, the number of smaller integers coprime to the argument.

I'd be interested in applications of these, too.

• I think Fibotorials would work, too, and probably other factorial-like sequences similarly constructed. Commented Nov 28, 2023 at 7:09
• Indeed, $a_1=a_2=a_3=1, a_4=1\cdot 1\cdot 2 = 2, a_5=1\cdot 1\cdot 2\cdot 3=6$, seems to be a good sequence. Commented Nov 29, 2023 at 14:32
• Perhaps, it makes sense to look at sequences $\mathbf{b}=(b_n)_{n \ge 0}$ such that for any $m,n\ge 0$, $m\mid n$ implies $b_m\mid b_n$. Then we can let $a_n=n!_\mathbf{b}=\prod_{k=1}^{n}b_k$. Commented Nov 29, 2023 at 17:14
• @AlexanderBurstein, it seems that your construction almost works. First, apparently $a_n = (n-1)!$ (and $a_0 = 1$) also seems to work, however, for the Fibotorials we have to take $a_n = (n-1)!_{\bf F}$. Second, if we take $a_n = (n-1)!_{\bf b}$ for a sequence with $m\mid n$ implying $b_m\mid b_n$, it seems that many sequences work, but there are exceptions, for example ${\bf b} = (1, 2, 2, 2, 1, 2, 1, \dots)$, (so $a_1=a_2=1,\dots,a_7=a_8=16$) it fails for the partition $4,1,1,1,1$, where we would like to have $5a_8 / (a_5 a_4 a_1^4)$ being an integer. Commented Nov 30, 2023 at 10:34
• @AlexanderBurstein, I think that your idea works for those sequences where $\binom{a}{b}_{\bf b}$ is an integer. For ${\bf b} = (1,2,2,2,1,2,1,\dots)$ this is not the case fof $\binom{7}{3}_{\bf b} = \frac{1\cdot 2\cdot 1\cdot 2\cdot 2\cdot 2\cdot 1}{(2\cdot 2\cdot 1)\cdot(2\cdot 2\cdot 2\cdot 1)} = \frac{16}{4\cdot 8}$. Commented Nov 30, 2023 at 11:52

Not a definitive answer, but the question is stale, and this could be at least somewhat useful.

Note that we can rewrite the coefficient in the composition as $$\left[\frac{z^n}{a_n}\right] F(G(z)) = \sum\limits_{k=0}^\infty \frac{1}{a_k} \left[\frac{z^k}{a_k}\right] F(z)\left[\frac{z^n}{a_n}\right] G(z)^k,$$ and for majority of functions of interest we would rather want that groups of summands corresponding to the same partition make up an integer, rather than focusing on an integer total sum. In a very general case, this boils down to a requirement that for any $$n$$ and a partition $$i_1+\dots+i_k = n$$, it holds that, assuming $$j_t$$ is the number of blocks of size $$t$$, the number

$$A(i_1,\dots,i_k) = \frac{1}{a_k} \binom{k}{j_1,\dots,j_k} \frac{a_n}{a_{i_1} \dots a_{i_k}}$$ is an integer. I suppose, here are some useful properties about such sequences:

1. For $$\left[\frac{z^n}{a_n}\right]G(z)=g_n$$ and $$\left[\frac{z^n}{a_n}\right]F(z)=f_n$$, the composition rewrites as $$\left[\frac{z^n}{a_n}\right] F(G(z)) = \sum\limits_{k=0}^\infty f_k \sum\limits_{\substack{i_1+\dots+i_k=n\\i_1\leq\dots\leq i_k}} A(i_1,\dots,i_k) g_{i_1}\dots g_{i_k},$$ meaning that $$A(i_1,\dots,i_k)$$ combinatorially stands for the weight with which the corresponding partition of $$n$$ into $$k$$ blocks of sizes $$i_1,\dots,i_k$$ is counted. Typically, this number represents the number of ways to distribute $$n$$ atoms among the $$k$$ blocks and/or build some structure on top of the blocks.
2. For $$a_n = n!$$, we have $$A(i_1,\dots,i_k) = \frac{1}{j_1!\dots j_k!} \binom{n}{i_1,\dots,i_k}$$, which has combinatorial meaning as the number of partitions of $$n$$ into blocks of size $$i_1,\dots,i_k$$, where order of blocks doesn't matter.
3. For $$a_n = x^{n-1}$$, we have $$A(i_1,\dots,i_k) = \binom{k}{j_1,\dots,j_k}\frac{1}{x^{k-1}} \frac{x^{n-1}}{x^{n-k}}=\binom{k}{j_1,\dots,j_k}$$.
4. For $$a_n = x^{\binom{n}{2}}$$, we have $$A(i_1,\dots,i_k) = \binom{k}{j_1,\dots,j_k}x^{\binom{n}{2} -\binom{i_1}{2}-\dots-\binom{i_k}{2}-\binom{k}{2}}.$$ At the same time, $$\binom{a+b}{2} - \binom{a}{2} - \binom{b}{2} = ab$$, from which we can rewrite $$A(i_1,\dots,i_k) = \binom{k}{j_1,\dots,j_k}\prod\limits_{a < b} x^{i_a i_b-1},$$ which is always integer if we only consider functions $$G(x)$$ with $$G(0)=0$$.
5. If $$A(i_1,\dots,i_k)$$ is always an integer multiple of $$\binom{k}{j_1,\dots,j_k}$$, and $$b_n$$ is a good sequence, then $$c_n = a_n b_n$$ is also a good sequence, as $$C(i_1,\dots,i_k)$$ is an integer: $$C(i_1,\dots,i_k)=\frac{A(i_1,\dots,i_k) B(i_1,\dots,i_k)}{\binom{k}{j_1,\dots,j_k}}$$ For example $$c_n = n! 2^{\binom{n}{2}}$$ is a good sequence, used to enumerate labeled graphs.

The variant $$a_n = x^{\binom{n}{2}}$$ is typically used in graphic generating functions, and have a nice combinatorial interpretation when considering direct products $$F(z) G(z)$$, but considering functional composition for them is uncommon, and exact meaning and interpretation for it remains to be seen, if it exists.

UPD. Generally, this criterion can be interpreted in such a way that we have some kind of baseline combinatorial structure, such that $$a_n$$ enumerates the number of way to build the structure on $$n$$ atoms.

For $$a_n=n!$$, the structure is permutations, while for $$a_n = 2^{\binom{n}{2}}$$ the structure is undirected graphs or tournaments on $$n$$ vertices. Then, the wholeness of $$A(i_1,\dots,i_k)$$ can be interpreted in such a way that by building the base structure on $$n$$ atoms, we also implicitly and independently from each other build

1. A sub-structure of the same kind on first $$i_1$$ atoms, second $$i_2$$ atoms, and so on;
2. A sub-structure of the same kind on the partition $$\{i_1,\dots,i_k\}$$ itself.

Then, $$A(i_1,\dots,i_k)$$ is the number of $$n$$-structures that are somehow equivalent to each other with regard to the sub-structures.

Then, we use these baseline structures to build an $$F$$-structure on top of the composition's base structure, and $$G$$-structures on top of each block of atoms base structure, and interpret whatever we obtained in the end as an $$(F \circ G)$$-structure on top of $$n$$ atoms as a whole.

• Thank you for starting this! I think in 1. you meant $[z^n/a_n]$, right? Also, $i_1 + \dots + i_k = n$ should be referred to as a composition of $n$, rather than a partition. Commented Nov 29, 2023 at 10:20
• $z_n / a_n$, yes, thanks for pointing out. And yes, $i_1+\dots+i_k=n$ is actually a composition. Thanks for pointing this out, I didn't think about it this way before, because for $a_n = n!$ we divide it by $k!$, thus accounting for the number of partitions of the atom set, rather than compositions. But in a more generic case it doesn't work like this. Commented Nov 29, 2023 at 12:28
• I think the criterion that $A(\alpha)$ is an integer is too strong, because it does not hold for $a_n = n!$: In this case, $A(1,2) = \frac{a_3}{a_2 a_1 a_2} = \frac{3!}{1! 2!^2} = \frac{3}{2}$. More precisely, $A(\alpha)$ needs an additional factor, namely the number of rearrangements of $\alpha$, (i.e, the multinomial of the multiplicities of the parts), right? Commented Nov 29, 2023 at 13:22
• In particular, I think that item 2. is incorrect: for example, $a_n = n!^2$ does not work. Commented Nov 29, 2023 at 13:43
• I amended the response. Hopefully it makes a bit more sense now. Commented Nov 29, 2023 at 14:05