Generating function formulation

Question

The question I am given is (I am not asking for this whole question to be solved, just posting it here as reference):

Let $S$ be the set of all non-empty subsets of $\{1,...,n\}$. Define the weight $w(B)$ of a set $B\in S$ to be the smallest element of $B$.

Prove that $Φ_{S}(x) = \frac{x^{n+1}-2^nx}{x-2}$

I believe the first step is algebraically defining the weight function so that I can use it to start formulating the generating function. I have been working on this for hours and can't figure out how to express this algebraically, especially when I don't have S expressed algebraically. Any help in correcting my thinking or starting off this question is much appreciated!

Potentially useful notes: I have determined that $\vert S\vert=2^n$ and each element of $\{1,...,n\}$ appears in $S$ a total of $2^{n-1}$ times (which I am still trying to prove).

The generating function, I couldn't find how to do the proper symbol. — mhlzzz, May 21 '17 at 01:53
The generating function of what? For example, what should the coefficient of $x^n$ in the expansion of $\Phi$ mean? — Tachyon, May 21 '17 at 01:58
$a_i$ in $a_{i}x^i$ is the number of elements of $S$ that have weight $i$. That is, the number of elements of $S$ that have $i$ as the smallest element in the set. — mhlzzz, May 21 '17 at 02:03

score 1 · Accepted Answer · answered May 21 '17 at 02:19

Fix $S=\{0,1,2,\dots,n-1\}$. For a subset of $S$ to have weight $i$, it cannot contain elements from $0$ to $i-1$. Then for $a_i$, we want to compute the number of subsets of $\{i,i+1,\dots, n-1\}$ which contain $i$.

The number of subsets of $\{i,i+1,\dots, n-1\}$ is $2^{n-i}$, and the number of subsets of $\{i,i+1,\dots, n-1\}$ not containing $i$ is $2^{n-i-1}$ (i.e. they are all the subsets of $\{i+1, i+2,\dots, n-1\}$). This gives that the number of subsets of $S$ of weight $i$ is $a_i=2^{n-i}-2^{n-i-1}$.

Then the polynomial you want is $(2^n-2^{n-1})+(2^{n-1}-2^{n-2})x+\cdots+(2^{n-(n-1)}-2^{n-n})x^{n-1}$. To get it into the form that you have, multiply top and bottom by $x-2$ to get: $\frac{x^n-2^n}{x-2}$.

(Note: I started with the set $S=\{0,1,\dots, n-1\}$, and you used the set $\{1,2, \dots, n\}$. If you want to use the second set, just multiply the polynomial above by $x$, since the second set shifts all the weights up by $1$.)

score 0 · Answer 2 · answered May 21 '17 at 02:22

0

Compare $n$ to $n+1$. You can either add $n+1$ to each set or not add it. There's also the extra singleton $\{n+1\}$.

So,

$$\Phi_{n+1}=2\Phi_n+x^{n+1}=\sum_{k=0}^n2^{k}x^{n+1-k}$$$

Can you finish it from here?

answered May 21 '17 at 02:22

Alex R.

32,771

Generating function formulation

2 Answers2