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?
maybe generating function?
-
0@anon: yes, correct – 2012-02-21
1 Answers
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). $