0
$\begingroup$

I'm new to this generating series stuff and wondering if I could get some assistance.

The question goes something like this: Let S be the set of all binary strings with the same number of zeros and ones, and let the weight of the string be the number of ones it contains. I need to write ΦS(x) as an infinite sum.

  • 0
    Yes, you're correct. I'll edit that.2012-09-26

1 Answers 1

1

HINT: I’m going to guess that $\Phi S(x)=\sum_{n\ge 0}s_nx^n\;,$ where $s_n$ is the number of strings in $S$ of weight $n$. If this is correct, you’re really just being asked how many binary strings there are with $n$ zeroes and $n$ ones. Such strings have $2n$ bits, and you can choose any $n$ of them to be occupied by ones. How many ways are there to choose $n$ things out of a set of $2n$ things? That’s the number that you want for $s_n$.