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?

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