How many distinct pairwise difference multisets exists?

Question

For all $K$-point integer-valued sets whose elements are between $1$ and $N$ and also distinct, how many distinct pairwise difference multiset exists?
Note that the difference is evaluated modulu N.
for example: for $(N,K)=(5,3)$ we have:

$\color{green}{\{1,2,3\} \rightarrow \{1,1,2,3,4,4\}}$
$\color{red}{\{1,2,4\} \rightarrow \{1,2,2,3,3,4\}}$
$\color{green}{\{1,2,5\} \rightarrow \{1,1,2,3,4,4\}}$
$\color{red}{\{1,3,4\} \rightarrow \{1,2,2,3,3,4\}}$
$\color{red}{\{1,3,5\} \rightarrow \{1,2,2,3,3,4\}}$
$\color{green}{\{1,4,5\} \rightarrow \{1,1,2,3,4,4\}}$

Note that other possible 3-point sets are shifted or reversed version of shown sets and lead to same pairwise difference multisets. So we can assume that the first element of set is $1$, without loss of anything. So for $(N,K)=(5,3)$ we have only 2 distinct pairwise difference multisets.
I'm looking for a formula which computes all distinct possible pairwise difference multisets for any pair $(N,K)$ ?
As I didn't know what is the most preferable site for this question, I posted in on these sites too: mathoverflow, Theoretical Computer Science

Answer 1

I used the following Python code to tabulate some numbers:

import sys, itertools
for n in range(1, 25):
    sys.stdout.write("{:3}:".format(n))
    for k in range(1, n + 1):
        r = set()
        for c in itertools.combinations(range(n), k):
            d = [0]*n
            for i, c1 in enumerate(c):
                for c2 in c[(i + 1):]:
                    d[c2 - c1] += 1
                    d[n + c1 - c2] += 1
            d = tuple(d)
            r.add(d)
        sys.stdout.write(" {:4}".format(len(r)))
    sys.stdout.write("\n")

Demo run of that code is also available at http://ideone.com/R0z3dg. Since you requested an explanation in a comment, here is how this works: The outer two loops iterate over reasonable values for $N$ and $K$, i.e. all the (non-empty) cells of the table. The choice of $0<K\leq N$ is somewhat arbitrary; I might as well have included $0$ or excluded $N$, since both of these will always lead to $1$. c then iterates over all possible combinations of $K$ elements taken from the set range(n) $=\{0,1,\dots,(N-1)\}$. These are your point sets. The combinations will be already sorted. The next two loops choose c1 and c2 from that combination such that c1 < c2. For each such pair, you have two differences. The difference c2 - c1 will already be in the range $[0, N)$. The other difference will be negative, so you add $N$ as part of your modulo semantics. For both of these differences, you increment the associated count in the multiset. So d[i] will indicate the number of times the difference i (mod $N$) has already been seen in the current combination c. Once this count is complete (i.e. the loops over c1 and c2 are done), you turn the mutable list into an immutable tuple which can be used as an element of the set r. The result for a given $N$ and $K$ is simply the size of that set r once all combinations c have been processed.

The resulting table looks like this:

  N↓ K→ 1    2    3    4    5    6    7    8    9   10 …
  1:    1
  2:    1    1
  3:    1    1    1
  4:    1    2    1    1
  5:    1    2    2    1    1
  6:    1    3    3    3    1    1
  7:    1    3    4    4    3    1    1
  8:    1    4    5    7    5    4    1    1
  9:    1    4    7   10   10    7    4    1    1
 10:    1    5    8   16   13   16    8    5    1    1
 11:    1    5   10   20   26   26   20   10    5    1    1
 12:    1    6   12   28   35   35   35   28   12    6    1    1
 13:    1    6   14   34   57   74   74   57   34   14    6    1    1
 14:    1    7   16   47   73  120   85  120   73   47   16    7    1 …
 15:    1    7   19   56  106  160  222  222  160  106   56   19    7 …
 16:    1    8   21   70  137  246  327  254  327  246  137   70   21 …
 17:    1    8   24   84  196  376  576  698  698  576  376  196   84 …
 18:    1    9   27  104  237  493  762 1121  701 1121  762  493  237 …
 19:    1    9   30  120  324  735 1311 1962 2338 2338 1962 1311  735 …
 20:    1   10   33  143  384  932 1778 2649 3651 2377 3651 2649 1778 …
 21:    1   10   37  165  507 1257 2609 4662 6006 7866 7866 6006 4662 …
 22:    1   11   40  195  601 1717 3576 6830 9860 13268 7944 13268 9860 …
 23:    1   11   44  220  759 2244 5302 10395 17105 23958 28216 28216 …
 24:    1   12   48  253  881 2635 6574 12844 21499 32342 42389 25220 …
 25:    1   12   52  286 1086 3622 9574 21389 39582 59132 85754 99638 …

The case from your example, $T(5, 2)=2$, can be read from row 5 column 2 of this table. If you omit the diagonal where $N=K$, i.e. drop the trailing 1 from each row, then the resulting triangle is exactly the one you find as the triangular array representation of OEIS sequence A103441. The statement of this sequence sounds a lot like your question, too:

$T(n,k) =$ number of bracelets of $n$ beads (necklaces that can be flipped over) with exactly two colors and $k$ white beads for which the set of distances among the white beads are different.

Unfortunately, there is no closed forula to accompany that sequence. So at least that encyclopedia does not know the formula you are looking for. There is some Mathematica code, but I guess that this does something as brute-force as what I did in Python above. If anyone here does find a closed formula, please make sure that OEIS gets updated with this information as well.

Since your comment below indicates different results on your part, and the first difference is for $N=8,K=4$, here are some details for that case, using the same notation you used in your original question. As you can see, I got $T(8,4)=7$ with the following point sets as wittnesses:

$$\{1,2,3,4\}\to\{1,1,1,2,2,3,5,6,6,7,7,7\}\\ \{1,2,3,5\}\to\{1,1,2,2,3,4,4,5,6,6,7,7\}\\ \{1,2,3,6\}\to\{1,1,2,3,3,4,4,5,5,6,7,7\}\\ \{1,2,4,6\}\to\{1,2,2,3,3,4,4,5,5,6,6,7\}\\ \{1,2,4,7\}\to\{1,2,2,3,3,3,5,5,5,6,6,7\}\\ \{1,2,5,6\}\to\{1,1,3,3,4,4,4,4,5,5,7,7\}\\ \{1,3,5,7\}\to\{2,2,2,2,4,4,4,4,6,6,6,6\}$$