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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.