# A problem on counting k-subsets of {-n,-n+1,…,n-1,n} satisfying that sum of elements equal to 0

I'll use another way to give the question besides the title.

Define $$A_k(n) = \frac{1}{2 \pi \mathrm{i}} \int_{|q|=1} \left( \frac{1}{2 \pi \mathrm{i}}\int_{|z|=1}\prod_{j=-n}^{n}(1+qz^j) \frac{dz}{z} \right) \frac{1}{q^k} \frac{dq}{q}.$$

By some numeral calculation buy a simple program, I note that if we freeze $k$, then $A_k(n)$ always satisfies a linear recurrence relations.

How to make a proof? Or anyone could give a counterexample? (A "appropriate" counterexample may be a sequence $A_l(1), A_l(2), \cdots, A_l(m)$ for large enough $m$.)

Thanks for reading my problem. : )

• Residue formula seems the way to go, did you try it? It is difficult to give a counterexample to a recurrence relation that you did not state! – Benoît Kloeckner Jan 3 '14 at 13:43
• Any sequence satisfies some recurrence relation. To make a meaningful question, specify what sort of recurrence relations you seek. – Andreas Blass Jan 3 '14 at 13:44
• To Andreas, thanks for your comment, I've re-edited it. – Lwins Jan 3 '14 at 13:52
• To Benoît, if changing $(1+qz^j)$ to $(1-qz^j)^{-1}$, I thought I could do it by residue formula. But if not, it seems to be too hard for me. – Lwins Jan 3 '14 at 13:56
• Maybe the combinatorial interpretation is a better way to justify a recurrence. $A_k(n)$ is something like the number of $k$-subsets of $\lbrace -n,\ldots,n\rbrace$ that sum to 0, isn't it? – Brendan McKay Jan 3 '14 at 15:17

Here is a sketch of a proof. First I'll switch $q$ and $z$, since this is more consistent with standard “$q$-series” notation.
Let $C_k(n)$ be the coefficient of $z^k$ in $\prod_{j=-n}^n (1+q^jz)$, so that $A_k(n)$ is the constant term in $q$ in $C_k(n)$. By the $q$-binomial theorem $$\prod_{j=0}^{m-1} (1+q^iz) = \sum_{k=0}^m {m \atopwithdelims[] k} q^{\binom k2}z^k,$$ where $${m \atopwithdelims[] k} = \frac{(q^m-1)(q^{m-1}-1)\cdots (q^{m-k+1}-1)}{(q^k-1)\cdots (q-1)}.$$ It follows that $$C_k(n)={2n+1 \atopwithdelims[] k} q^{\binom k2 -kn}$$ Expanding the $q$-binomial coefficients, we see that $$C_k(n)=\sum_{l=-k}^k R_l(q) q^{ln},$$ where each $R_l(q)$ is a rational function of $q$.
Now let $$G_k=\sum_{n=0}^\infty C_k(n) t^n.$$ Then $$G_k=\sum_{l}\frac{R_l(q)}{1-tq^l}.$$ Expanding $G_k$ in partial fractions in $q$, we see that the constant term in $q$, which is $\sum_n A_k(n)t^n$, is a rational function of $t$, so $A_k(n)$ satisfies a linear recurrence with constant coefficients.
For example, $$G_2 = \frac{(1+q)t}{(1-t)^2(1-q^2t)} + \frac{t(q+t)}{(1-t)^2(q^2-t)}.$$ The second term, when expanded as a power series in $t$, has only negative powers of $q$, so it contributes nothing to the constant term in $q$. The first term, when expanded as a power series in $t$, has only nonnegative powers of $q$, so we obtain the constant term in $q$ by setting $q=0$ in the first term and we find that $$\sum_{n=0}^\infty A_2(n) t^n = t/(1-t)^2 =\sum_{n=0}^\infty nt^n.$$
• Why $G_k = \sum_m {\dfrac{R_m(q)}{1-tq^m}}$? – Lwins Jan 3 '14 at 17:38
• Thanks for your detailed answer. Last problem: Why $C_k(n) = \exp (\cdots) \Longrightarrow C_k(n)$ is a linear combination of products... ? (Though that by $q$-binomial theorem it's trivial.) – Lwins Jan 3 '14 at 18:29