Holmes–Plummer enumeration conjecture for cds-sortable permutations

At least 11 years old · documented by

Let Sn\mathfrak{S}_n denote the symmetric group on nn elements, and let a permutation be cds-sortable if it can be sorted using the context-directed reversal operations described in the paper. For every integer k≥0k\geq 0, the number of cds-sortable elements of S2k+1\mathfrak{S}_{2k+1} is

#{cds-sortable elements in S2k+1}=(k+1)(2k)!.\#\{\text{cds-sortable elements in }\mathfrak{S}_{2k+1}\}=(k+1)(2k)!.

Holmes–Plummer conjecture. The number of cds-sortable elements in S2k+1\mathfrak{S}_{2k+1} equals (k+1)(2k)!(k+1)(2k)!. This conjecture proposes a closed formula for the odd-degree terms in the enumeration of cds-sortable permutations; the paper states that a general formula was not known and attributes this conjecture to E. Holmes and P. A. Plummer.

References

Primary source

K. L. M. Adamyk, E. Holmes, G. R. Mayfield, D. J. Moritz, M. Scheepers, B. E. Tenner and H. C. Wauck, “Sorting Permutations: Games, Genomes, and Cycles”, arXiv:1410.2353 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.