3

Is there a nice way to use generating functions to represent the formal sum of all size-$k$ subsets of a set $S$? Here I want to represent a subset by the product of its elements.

For example, if $S = \{a,b,c\}$ and $k = 2$ then then the formal sum is $ab + ac + bc$. Is there a nice way for arbitrary $k$ and $S = \{a_1,a_2,\dots,a_n\}$?

I'm trying to solve a more general problem, but my difficulty has boiled down to this.

Thanks for the help!

user160371
  • 179
  • Here is a similar question: http://math.stackexchange.com/questions/786183/sum-of-multiplication-of-all-combination-of-m-element-from-an-array-of-n-element/788655#788655 – Rus May Mar 10 '15 at 10:45
  • You are looking for the combinations of $n$ different objects with $k$ elements. You could write your sum as $\sum_{i_1}\sum_{i_2}...\sum_{i_n}a_1^{i_1}a_2^{i_2}...a_n^{i_{n}}$. Your sums are the elementary symmetric polynomials in $n$ variables. – IV_ Aug 24 '19 at 16:56

1 Answers1

1

Let say that $$[t^k]P(t) = \mbox{ coefficient with } t^k \mbox { in polynomial } P$$

For simplicity, let name element from our set by some index: $$ S = \left\{a_1, a_2, a_3, ..., a_n \right\} $$

Your generating formula would be: $$ F(S,t) = [t^k](1+a_1 t)(1+a_2 t)(1+a_3 t) \cdots (1+a_n t) $$ where $\forall_i a_i \in S$

For your example you get: $$ F(\left\{a,b,c \right\},2) = \\ [t^2](1+a t)(1+b t)(1+c t) = \\ [t^2] \left(a b c t^3+t^2 (a b+a c+b c)+t (a+b+c)+1 \right) = \\ a b+a c+b c$$ A bit more explanation:

One term $(1+et)$ means that if you choose $1$ you don't take element $e$ from set, if you choose $e\cdot t$ you take element $e$ and increment your counting variable so you can control product by size with $t^{k}$ which you want.

mvxxx
  • 286
  • 1
    I know that question has some years but it is really interesting and worth for next searchers. – mvxxx Aug 24 '19 at 15:39