Number of ways to pick N numbers from 0,1,...,N-1, with possible duplication, with sum equal 0 mod N

Question

We have the numbers $0,1,2,....,N-1$ in $\mathbb Z_N.$ I want to pick $N$ numbers from these. These are the rules:

• Duplication may occur
• We don't care about ordering, $00041$ is equivalent to $40010$
• If you add $1$ to all the numbers you picked, what you get will be equivalent to what you just had. In other words, if $N = 5, 00343$ is eqivalent to $11404.$

Question: How many equivalence classes are there s.t. the sum of the numbers in the class is $0$ mod$N$?

Answer 1

I cannot give an exact answer to your question right now, and my general feeling is that this might be quite hard.

Instead, I will develop some lower bound.

Let $$X = \{(a_1,\ldots,a_N) \in\mathbb Z_N^N\mid a_1 + \ldots + a_N = 0 \}$$ be the set of all solutions over $\mathbb Z_N$ (without any symmetry). Its size is $N^{N-1}$, since the first $N-1$ numbers $a_1,\ldots,a_{N-1}$ can be chosen arbitrarily and the last number $a_N$ is then determined as $a_N = -(a_1 + \ldots + a_{N+1})$.

Your the identification of solutions which differ by a permutation and/or a translation can be restated in terms of group actions:

Let $G$ be the group of bijections on $\mathbb Z_N^N$ generated by $$\{ (a_1,\ldots,a_N) \mapsto (a_{\sigma(1)},\ldots,a_{\sigma(N)}) \mid \sigma\in S_N\}$$ and $$\{ (a_1,\ldots,a_N) \mapsto (a_1 + t,\ldots,a_N + t) \mid t\in\mathbb Z_N\}$$

Now your question asks for the number $f(N)$ of orbits of the action of $G$ on $X$.

In this context, you may try to apply techniques from the theory of group actions like Cauchy-Frobenius. However, it's not obvious at all how to start, since the job of counting the number of fixed points of every group element is not exactly straightforward.

We can use the above setting to get a lower bound on $f(N)$. Since $X$ is of size $N^{N-1}$ and the orbits have length at most $\# G = N\cdot N!$, we get $$f(N) \geq \left\lceil \frac{N^{N-1}}{N \cdot N!} \right\rceil = \left\lceil\frac{N^{N-3}}{(N-1)!}\right\rceil$$ So the number $f(N)$ will grow exponentially.

Lets improve that bound a little bit: We see that

• The orbit of $(0,...,0)\in X$ has only length $N$.
• Orbit length $N\cdot N!$ is not possible for $N \geq 2$: In this case, the stabilizer of any orbit element $v\in X$ would be trivial, so all $N$ entries in $v$ must be distinct. Thus, the entries of $v$ consist of all elements of $\mathbb Z_N$ showing up exactly once. This implies that for every translation mapping there is a permutation nullifying that translation, which induces a nontrivial group element in the stabilizer. Thus, the orbit lengths are bounded by $N\cdot N! /2$ (note that the orbit length must divide the group order).

So for $N\geq 2$ $$f(N) \geq \left\lceil \frac{N^{N-1}-N}{N\cdot N!/2} + 1\right\rceil = \left\lceil\frac{2(N^{N-2} - 1)}{N!}\right\rceil + 1$$

I guess it shoudn't be too hard to further improve that bound by a more detailed analysis.