# Sum-Product Generating Functions

Let $A_n$ be a family of sequences $\{a_i\}_{i=1}^n$ of length $n$. I'll refer to sequence elements of $A_n$ as $a$. Then define

$$G(z):=\sum_{a\in A_n}\prod_{i=1}^n(z+a_i).$$

Here's one possible concrete example. Let $A_n=S_n$, the permutation group on $n$ elements. This is a rather easy example because the product term is the same for all elements of $S_n$ and we get the nice expression $G(z)=n!z^{[n]}$ where $z^{[n]}:=(z+1)\cdots (z+n)$.

I'm interested in what information can be extracted from $G(z)$ about $A_n$. In particular, is there a common name or reference for the family of such generating functions of this sum-product form?

For example:

$$\lim_{r\rightarrow\infty}\frac{G(r)}{r^n}=|A_n|.$$

In other words we can extract the size of $A_n$.

-

Let's answer this question (even if it's not a very useful answer), the answer discuss the part how many information we can get from $G(z)$

We can use sets instead of sequences, given a set $A$ of sets $I$ such that :$|A|=m$ and $\forall I\in A |I|=n$ (The question imposes $n=m$ but the answer will be more general) we define: $$G_A(z)=\sum_{I\in A}\prod_{a\in I}(z+a)$$

Knowing $G_A$ the only information we can obtain are the value of the sums $0\leq i\leq n$: $$S_i=\sum_{I\in A}f_i(I)$$ with $$f_i(I)=\sum_{J\subset I,|J|=i}\prod_{a\in J}a$$

e.g

• For $i=0$ we have $f_i(I)=1$ so $S_0=|A|$
• For $i=1$ we have $f_i(I)=\sum_{a\in I}A$ so we can know the sum of all elements of all subsets of $A$
• $\cdots\cdots$
• For $i=n$ we have $f_i(I)=\prod_{a\in I}a$ so we can know the sum of the product of all elements of all sets $\in A$

The sums $S_i$ are exactly the coefficients of $G_A$ which makes this result obvious, but they represent also the only amount of information we can know about $A$ knowing $G_A$, this means that if we have given two sets $A$ and $B$ having the same values for all sums $S_i$ then $G_A=G_B$. e.g $n=2$ we will have: \begin{align}G_A(z)&=(z+a_1)(z+b_1)+(z+a_2)(z+b_2)+\cdots+(z+a_m)(z+b_m)\\&=mz^2+(a_1+b_1+a_2+b_2+\cdots+a_m+b_m)z+(a_1b_1+\cdots+a_mb_m)\end{align} now it's obvious that the only values we can deduce are $m,a_1+b_1+\cdots+a_m+b_m$ and $a_1b_1+\cdots+a_mb_m$ and if another sets $B$ has the same values of this coefficients then $G_A,G_B$. Another question would be how many sets $A$ for which the values of $S_i$ are the same, if we are working in real numbers we will set all elements of $A$ to variables, so we will have $nm$ variables with $n$ equation which very likely have an infinity number of solutions, rising this question for natural numbers will be not easy to tackle

-