I have encountered a problem that I suspect has been thoroughly studied but I have not been able to find references. Can anyone point me to a published reference dealing with this or a closely related problem?


Here is the problem:


Let $A$ and $B$ be disjoint $k$-subsets of $\mathbb{Z}/n\mathbb{Z}$. Consider $S(A,B)=\sum\_{x\in A}x - \sum\_{y\in B}y$. As $(A,B)$ ranges over all possible ordered pairs of disjoint $k$-subsets of $\mathbb{Z}/n\mathbb{Z}$, how are the sums $S(A,B)$ distributed over the elements of $\mathbb{Z}/n\mathbb{Z}$? More precisely, for how many of the $\binom{n}{k}\binom{n-k}{k}$ choices of $(A,B)$ is $S(A,B)$ equal to each of the elements of $\mathbb{Z}/n\mathbb{Z}$?


Again I am just looking for references. I actually have a solution in the case that n is prime, but I assume the result is known for more general n. I would be interested in any leads.



Sums of subsets of $\mathbb{Z}/n\mathbb{Z}$
For convenience I will first consider how many sums $S(A,B)$ are equal
to 0. I might have made some computational errors, but I think that
the method is correct. Regard $n$ as fixed. Let $f\_k$ be the number of
pairs $(A,B)$ of $k$-element subsets (not necessarily disjoint) of
$\mathbb{Z}/n\mathbb{Z}$ such that $\sum\_{x\in A}x-\sum\_{y\in
B}y=0$. Let $g\_k$ be the same, except that $A$ and $B$ must be
disjoint. It is easy to see that
 $$ f\_k = g\_k+{n-2(k-1)\choose 1}g\_{k-1}+{n-2(k-2)\choose
 2}g\_{k-2}+\cdots. $$
These equations for $0\leq k\leq n$ can be inverted to express
the $g$'s in terms of the $f$'s, so it suffices to find $f\_k$.


Let $[x^iy^j]P(x,y)$ denote the coefficient of $x^iy^j$ in the
polynomial $P(x,y)$. By standard properties of roots of unity, we have
 \begin{eqnarray\*} f\_k & = & [x^ky^k] \frac 1n \sum\_{\zeta^n=1}
 \prod\_{j=0}^{n-1} (1+x\zeta^j) (1+y\zeta^{-j})\\ & = &
 \frac 1n\sum\_{d|n}\phi(d)(1-(-x)^{n/d})^d (1-(-y)^{n/d})^d.
 \end{eqnarray\*}
It is routine to extract the coefficient of $x^ky^k$,


Completely analogous reasoning works for sums equal to any $m\in
\mathbb{Z}/n\mathbb{Z}$, though the computation becomes messier. A
related computation appears in
<http://math.mit.edu/~rstan/pubs/pubfiles/8g.pdf>. See also *Enumerative
Combinatorics*, vol. 1, Exercise 1.105.


