Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:


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

share|cite|improve this question

1 Answer 1

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


  • 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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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