Take the 2-minute tour ×
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 $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 $σ$).

share|improve this question
    
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
1  
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

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.