Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A question asking for the number of ways of choosing $2A$ numbers from $\{0,1,..,2B\}$ with a sum of $2C$ can be answered with the help of generating function $$ F(x,t)=\frac{1}{\prod_{i=0}^{2B}(1-t^ix)}. $$ The number of ways $$ W=\frac{1}{(2A)!(2C)!}\frac{\partial^{2A+2C}F}{\partial x^{2C}\partial t^{2A}} $$ I am wodering if there is a generating function (or some other function) with the help of which we can find in how many of those ways $W$ the sum of any $0\leq D \leq A$ integers from {0,...,2B} is odd?

share|cite|improve this question
Wodering-I am afraid that's not something you'd like to share with a whole community. :-) [Just joking; No offense intended. Look up Wodering for what I mean] – user21436 Feb 21 '12 at 2:44
The sum of $0$ integers is always even... – Robert Israel Feb 21 '12 at 2:45
@anon: $W$ is the number of ways of choosing $2A$ numbers from $\{0,..,2B\}$ with a sum of $2C$. – David Feb 21 '12 at 3:00
@ Robert Israel : Thank you. I ment the sum of integers from $\{0,1,...,2B\}$. – David Feb 21 '12 at 3:04
@anon: yes, correct – David Feb 21 '12 at 3:32
up vote 1 down vote accepted

Sure. Define the $n$th coefficient operator

$$[x^n]\big(a_0+a_1x+a_2x^2+\cdots\big)=a_n = \frac{1}{n!}\frac{\partial^{\,n}}{\partial x^n}\big|_{x=0}. $$

We have

$$F_b(x,t)=\prod_{k=0}^b \frac{1}{1-t^kx}=\prod_{k=0}^b \left(1+t^kx+t^{2k}x^2+\cdots\right)=\sum_{n=0}^\infty \sum_{m=0}^\infty \ell_b(n,m) t^n x^m.$$

Above $\ell_b(n,m)$ counts the number of ways we can select $m$ elements out of $\{0,1,\cdots, b\}$ with replacement and obtain the number $n$. As you mention, this gives

$$\ell_b(n,m)=[t^n][x^m] F_b(x,t). \tag{*}$$

In order to find out the number of ways to sum $m$ elements of $\{0,\cdots,b\}$ to an odd number, we can simply sum $\ell_b(n,m)$ over all odd numbers $n$. Of course, $\ell=0$ for $n>mb$ so this is a finite sum. If we put the above formula into the answer we obtain

$$\square_{\,b}(m) =\left(\sum_{n=0}^{b-1} [t^{2n+1}]\right)[x^m] F(x,t).$$

And if you want this in the form of a generating function, we have

$$G(x)=\sum_{m=0}^\infty \square_{\,b}(m) x^m = \left(\sum_{n=0}^{b-1} [t^{2n+1}]\right) F(x,t). $$

share|cite|improve this answer

Your Answer


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.