# Ordering sets of integers based on their elements: can we always achieve the perfect balance?

Consider a family $$\{S_i\}_{i=1}^n$$ of finite, pairwise disjoint sets of positive integers, i.e., $$S_i\subset \mathbb{N}$$ and $$S_i\cap S_j=\emptyset$$, for any $$1\le i,j \le n$$ and $$i\neq j$$. Denote by $$\succ$$ a linear order over $$\{S_i\}_{i=1}^n$$ and, if $$\overline{s} = (s_1, \dots, s_n)$$ is a tuple with $$s_i\in S_i$$, say that $$\overline{s}$$ induces $$\succ$$ if it holds that $$s_i > s_j$$ if and only if $$S_i \succ S_j$$.

Example ($$n=2$$). If $$S_1 = \{0,3\}$$ and $$S_2 = \{1,2\}$$, the tuple $$(3,1)$$ induces the order $$S_1\succ S_2$$, whereas the tuple $$(0,1)$$ induces the order $$S_2 \succ S_1$$. Note that different tuples of integers can induce the same ordering, e.g., the tuples $$(3,1)$$ and $$(3,2)$$ both induce the order $$S_1\succ S_2$$.

Intuitively, I am drawing a number $$s_i$$ from each $$S_i$$ and using the ordered sequence thus obtained to determine the ordering over the $$S_i$$'s.

The question I am interested in is whether, for any $$n\geq 2$$, we can choose the sets $$\{S_i\}_{i=1}^n$$ such that every possible linear order over $$\{S_i\}_{i=1}^n$$ is induced equally often.

Example ($$n=2$$, continued). With $$S_1$$ and $$S_2$$ as above, there are two possible linear orders over $$\{S_1, S_2\}$$, i.e., $$S_1 \succ S_2$$ and $$S_2\succ S_1$$, and four possible tuples, i.e., $$(0,1)$$, $$(0,2)$$, $$(3,1)$$, $$(3,2)$$. Note that $$(0,1)$$, $$(0,2)$$ induce $$S_2\succ S_1$$ and $$(3,1)$$, $$(3,2)$$ induce $$S_1 \succ S_2$$, so in this case each of the two possible linear orders over $$\{S_1,S_2\}$$ appears exactly twice.

Example ($$n=3$$). The following assignment works: $$S_1 = \{2, 5, 7, 12, 15, 16\}$$, $$S_2 = \{1, 6, 8, 11, 14, 17\}$$, and $$S_3 = \{3, 4, 9, 10, 13, 18\}$$. There are $$3!=6$$ linear orders over $$\{S_1,S_2,S_3\}$$, the sets $$S_1$$, $$S_2$$ and $$S_3$$ each have $$6$$ elements, there are $$6^3=216$$ triples consisting of one element from each, and each linear order over $$\{S_1,S_2,S_3\}$$ is induced exactly $$\frac{216}{6}=36$$ times by these triples.

The example for $$n=3$$ was found with the help of a computer, and it is not unique, but for $$n \ge 4$$ the search space already gets too big to handle and the code timed out before finding any solution. Of course, the $$S_i$$'s do not need to have the same cardinality.

I am not necessarily looking for a solution, but would appreciate any insight that could help me think about the general case. Has the problem been studied before? Does it ring any bells?

I believe your question is answered affirmatively by Wen Chean Teh in “Parikh-friendly permutations and uniformly Parikh-friendly words,” in the Australasian Journal of Combinatorics. link

In order to see this, it helps to recast your question this way:

Given an alphabet $$\{a,b,\dots, x\}$$ of $$n$$ letters, does there exist a word $$w$$ using all of those letters so that among the ways of underlining one of each letter within the word, every permutation of the $$n$$ letters appears equally often? Alternatively, does there exist a word $$w$$ for which each permutation of $$ab\dots x$$ appears equally often as a subword of $$w$$?

Such words correspond to solutions to your question via the following correspondence. A word $$w$$ over $$\{a,b,\dots, x\}$$ determines $$n$$ sets of integers $$S_a\dots S_x$$, where $$S_\ell$$ is the set of positions where the letter $$\ell$$ appears in $$w$$.

For $$n=2$$, and alphabet $$\{a,b\}$$, the word corresponding to your solution is $$abba$$. For $$n=3$$, $$w=baccababccbacbaabc$$. (Your sets are the positions of the letters $$a$$, $$b$$, and $$c$$ in $$w$$.)

Teh enumerates the $$66$$ minimal ($$|w|=18$$) solutions for the case $$n=3$$ in the paper’s appendix. Teh further gives solutions for $$n=4$$ with $$|w|=96$$. Specifically, the concatenation of these four words (in any order) is a solution:

$$w_1=abcddcba\ dbaccabd\ cbaddabc\\ w_2=dcabbacd\ acbddbca\ bcdaadcb\\ w_3=cdbaabdc\ bdcaacdb\ adbccbda\\ w_4=badccdab\ cadbbdac\ dacbbcad$$

Finally, Teh gives a constructive proof that solutions exist for all $$n$$, but the sets of integers they would determine are of size $${\left(n!\right)^{n-1}}$$. It seems likely to me (from Teh’s paper and comments below) there might be solutions with sets of size $$n!$$.

Remarks from an earlier version of my answer, before discovering that the problem was solved by Teh.

First, a conjecture: If $$\mathcal S\{S_i\}_{i=1}^n$$ has the property you describe, must it be the case that every proper subcollection of $$\mathcal S$$ has the same property?

At a glance, I think each of the three pairs $$\{S_i,S_j\}$$ in your example for $$n=3$$ induces each of the two orders $$S_i\succ S_j$$ and $$S_j\succ S_i$$ equally often. If this is true in general, perhaps it helps to look for a way to locate elements of a new set $$S_{n+1}$$ relative to a solution to a smaller problem.

Given $$abba$$, there appears to be no way to place $$c$$’s to get a solution for $$n=3$$. (I didn’t prove this, but I assume you searched for smaller solutions than the one you found, and it just seemed impossible...)

However, the idea of building a solution from a previous one isn’t necessarily a dead end. In your solution for $$n=3$$, If you look at your pairs $$\{S_i,S_j\}$$ in your solution for $$n=3$$, the words describing those pairs as solutions for $$n=2$$ are (with spaces added to highlight an observation) either $$abba\ abba\ baab$$ or $$baab\ abba\ baab$$, that is, repetitions of shorter $$n=2$$ solution words. The locations of the $$c$$’s has some nice symmetry: $$ba\color{red}c\color{red}cab\ ab\color{red}c\color{red}cba\ \color{red}cbaab\color{red}c$$

Naively, since your example for $$n=2$$ uses $$2!$$ copies of each letter $$a$$ and $$b$$, and your example for $$n=3$$ uses $$3!$$ copies of each letter, a solution for $$n=4$$ might exist with $$24=4!$$ of each letter.

While possibly still intractable, that suggests looking for an $$n=4$$ solution by starting with four repetitions of $$baccababccbacbaabc$$ (possibly with some permutations of the alphabet) and then trying to insert $$24$$ $$d$$’s to make things work ($$6$$ of them within or next to each of the four repetitions), perhaps with some symmetry.