nt.number theory - How many pairs (M, N) of sets of size n have M + N = {0, 1, ..., n^2-1}?

Let $a$, $b$ be divisors of $n$. Convince yourself that the sets

$M = {0,1,ldots,a-1} + ab cdot {0,1,ldots,n/a-1}$

$N = {0,a,ldots,(b-1)a} + bn cdot {0,1,ldots,n/b-1}$

have the desired property. These pairs $(M,N)$ are all distinct as $a$, $b$ vary over divisors other than $1$, $n$. On the other hand the pairs coming from choosing $a=n$ or $b=1$ or $(a,b)=(1,n)$ all coincide with the obvious ("base $n$") pair, while the pair coming from $(a,n)$ coincides with the pair coming from $(1,a)$. So if $sigma$ is the number of divisors of $n$, this gives you at least $sigma^2 - 3 sigma + 3$ such pairs. For $n=10$ you can check (e.g. using the generating function method that you described) that this gives all the possibilities.

In general there will be more, because you can iterate the construction: you have pairs of the form

$M = {0,1,ldots,d_1-1} + d_1 d_2 {0,1,ldots,d_3-1} + d_1 d_2 d_3 d_4 {0,1,ldots,d_5-1} + cdots$

$N = d_1 { 0,1,ldots,d_2-1} + d_1 d_2 d_3 {0,1,ldots,d_4-1} + cdots$

for divisors $d_1,d_2,ldots$ of $n$ with $d_2 d_4 cdots d_{2k} = n$ and similarly for the product of the odd-indexed $d$'s. Now collisions between the various pairs should happen precisely whenever any of the $d_i$'s happens to be $1$, and so distinct pairs should come from distinct sequences $d_1,ldots,d_{ell}$ of divisors of $n$ other than $1$ such that the odd terms multiply to $n$ and the even terms also multiply to $n$. For instance we find that we've correctly re-counted the $sigma^2-3sigma +3$ possibilities that we found and counted before: the sequences of $d$'s of length at most $4$ are

$n,n$

$a,n,n/a$

$a,b,n/a,n/b$

as $a,b$ range over nontrivial divisors of $n$. But of course if $n$ has more than two prime factors, you get longer sequences as well. I'll leave it to someone else to do the enumeration of the sequences.

I think I've convinced myself that this construction gives you everything, but it might be a pain to write down. (Suppose $M$ is the set containing $1$. Take $d_1$ to be the smallest nonzero integer contained in $N$. Then the smallest integers in $N$ have to consist of multiples of $d_1$ up to some $d_1(d_2-1)$, and the next integer contained in $M$ is $d_1 d_2$. But then $d_1 d_2 + 1,ldots,d_1 d_2 + (d_1-1)$ each have to be in one or the other of the sets, and in fact they have to be in $M$ or else you could form the sum $d_1 (d_2+1)$ in two ways. And so forth.)

• Next conformal geometry - Intuition behind moduli space of curves
• Previous co.combinatorics - Generating functions for certain statistics on Coxeter groups of type B