# Combinatorial Proof of a Generating Series Involving Binary Strings

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 $σ$).

-
What does it mean, "with respect to the weight function $w$"? What does it mean to find a generating series for a sequence of sets? – Gerry Myerson Sep 18 '12 at 23:29
Good point, updated the question. – Overload119 Sep 18 '12 at 23:33
Ah. So you want the coefficient of $x^k$ to be the number of elements of the set $S(r)$ with $k$ ones in the binary representation. Each such element is a string of $r$ bits, and the number with $k$ ones is the number of ways of choosing the $k$ one-bits from the total $r$ bits. – Gerry Myerson Sep 18 '12 at 23:39
I understand that! Thanks. – Overload119 Sep 18 '12 at 23:48
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. – Gerry Myerson Sep 19 '12 at 0:02

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.

-