1
$\begingroup$

Let $r \ge 2$ be an integer, and let $S(r)$ = $\{0, 1, \ldots, 2^r-1\}$. Find the generating series for $S(r)$ with respect to the weight function w. Prove your answer is correct.

I came up with this solution:

$\sum_{k=0}^r \binom{r}{k} x^k$

I feel like this is correct, but I don't know how to go about proving it.

Does the question suggest a combinatorics proof?

EDIT: I forgot to mention the weight function: $w(σ) =$ (the number of ones in the binary representation of $σ$).

  • 0
    Good! Now you can write it up as an answer to your question and, eventually, accept your answer. May seem like a weird thing to do, but it's actually encouraged around here.2012-09-19

1 Answers 1

1

We know that the coefficient of $x^k$ is the number of elements with k 1's.

Let's consider this for a smaller set, $\{0,1,2,3,4,5,6,7\}$, which is the case when $r=3$

Now, below are the binary representations of each element:

  • $0 = 000$
  • $1 = 001$
  • $2 = 010$
  • $3 = 011$
  • $4 = 100$
  • $5 = 101$
  • $6 = 110$
  • $7 = 111$

Notice each element is composed of 4 bits (and $r=3$).

If we were to expand this with the above formula, we would get

$x^0 + 3x^1 + 3x^2 + x^3$

To count the configurations with $k$ 1's in their binary representation we count the number of ways we can pick $k$ 1's from the total $r$ bits.

For example, to pick the configurations with with 2 1's then we use $\binom{3}{2}$

You can extend these findings to a set of any size, but the principle still holds.