2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ cross-posted $\endgroup$
    – Kaveh
    Commented Jul 9, 2013 at 8:33
  • $\begingroup$ You did this to all of my posts Kaveh! Now I could not get any help! Please guide me what to do! $\endgroup$ Commented Jul 9, 2013 at 9:02
  • $\begingroup$ The comment above is only for information, so this post here remains answerable. A quick enumeration of values shows the numbers you are after to be those from oeis.org/A103441/table but unfortunately this does not come with a closed formula which you could use to compute these values. $\endgroup$
    – MvG
    Commented Jul 9, 2013 at 9:06
  • $\begingroup$ I didn't get anything from the tables in the link you suggested! Would you mind guiding how they are related to my question ? $\endgroup$ Commented Jul 9, 2013 at 9:08
  • 2
    $\begingroup$ @Mahdi, this is the usual practice. You should have provided the links between copies yourself and should not have posted questions on multiple sites at the same time. $\endgroup$
    – Kaveh
    Commented Jul 9, 2013 at 9:43

1 Answer 1

7
$\begingroup$

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\}$$

$\endgroup$
5
  • $\begingroup$ I'm not familiar with Python but I wrote the code in Matlab and I've got different answers! The simple algorithm I've used is as follows: build all possible sets and calculate difference multiset of each one and store all of them. Then count number of distinct stored multisets. for $K=4$ and different $N$'s it outputs these : $$N=4 \rightarrow 1$$ $$N=5 \rightarrow 1$$ $$N=6 \rightarrow 3$$ $$N=7 \rightarrow 4$$ $$N=8 \rightarrow 5$$ $$N=9 \rightarrow 9$$ $$N=10 \rightarrow 13$$ Would you mind giving me algorithm of your Python code ? $\endgroup$ Commented Jul 9, 2013 at 10:32
  • $\begingroup$ @MahdiKhosravi: I updated my answer to include both a detailed description of my algorithm (which is pretty straight-forward) and details on the $N=8,K=4$ case. $\endgroup$
    – MvG
    Commented Jul 9, 2013 at 12:37
  • $\begingroup$ Yes You are right. My code was wrong and I corrected it. Thank you for your kind answers. How much time did you take on this field? Are you hopeful to find a formula instead of this table? In what context you faced this problem? $\endgroup$ Commented Jul 9, 2013 at 13:34
  • $\begingroup$ @MahdiKhosravi: I have never before thought about this problem. I just read your question, decided to have a closer look, wrote that piece of code and fed the result into the OEIS search. I originally would have left it as a comment, but since you asked for details, I elaborated. I doubt I'll find a closed formula soon, and I won't have much time to spend on finding one. Perhaps someone else will. $\endgroup$
    – MvG
    Commented Jul 9, 2013 at 14:09
  • $\begingroup$ Nice coding. I am working to find the closed formula which may be out of reach. Also I propose combining charm bracelets with energy charges. (Histograms for charm bracelets). 12C6 charm bracelets = 34, but 26 different histograms. Also, 80 necklaces, 50 Dihedral, 35 histograms (15 isomeric pairs) $\endgroup$ Commented May 18, 2021 at 16:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .