2
$\begingroup$

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?

  • 1
    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]2012-02-21
  • 0
    The sum of $0$ integers is always even...2012-02-21
  • 0
    @anon: $W$ is the number of ways of choosing $2A$ numbers from $\{0,..,2B\}$ with a sum of $2C$.2012-02-21
  • 0
    @ Robert Israel : Thank you. I ment the sum of integers from $\{0,1,...,2B\}$.2012-02-21
  • 0
    @anon: yes, correct2012-02-21

1 Answers 1

1

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