In combinatorial mathematics, a superpermutation on n symbols is a string that contains each permutation of n symbols as a sub-string. This note introduces a recursive method to generate superpermutations. Fragments of superpermutations are used to generate a recursive algorithm. They are called chains of  permutations. Starting from a chain of permutations (2.7) and proceeding with a nesting (2.12) operations using the recursive method, it will be possible to create a superpermutation of length . The algorithm that can be written with this recursive method is really short and simple.

permutations, combinatorics, applied mathematics.

Received: November 20, 2023;  Accepted: December 28, 2023; Published: January 9, 2023

How to cite this article: Giuseppe Guarino, A recursive method to generate a superpermutation of length  Universal Journal of Mathematics and Mathematical Sciences 19(2) (2023), 139-162. http://dx.doi.org/10.17654/2277141723021

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References
[1] L. Adleman, Short permutation strings, Discrete Math. 10(2) (1974), 197-200.
[2] M. H. Albert and J. West, Universal cycles for permutation classes, Discrete Math. Theor. Comput. Sci. Proc., AK, 2009, pp. 3950.
[3] M. Bona, Combinatorics of permutations, Discrete Mathematics and its Applications, 2nd ed., CRC Press, Boca Raton, Florida, 2012.
[4] E. Di Nardo and G. Guarino, On the generation of necklaces and bracelets in R, Comm. Statist. Simulation Comput. 52 (2023), 5727-5737. https://doi.org/10.1080/03610918.2023.2199180.
[5] Greg Egan, Superpermutations, 2018. gregegan.net.
[6] Michael Engen and Vincent Vatter, Containing all permutations, Amer. Math. Monthly 128(1) (2021), 4-24. arXiv:1810.08252, doi:10.1080/00029890.2021.1835384.
[7] Mary Beth Griggs, An anonymous 4chan post could help solve a 25-year-old math mystery, The Verge, 2018.
[8] Guarino Giuseppe, A recursive algorithm to generate a superpermutation of length Maplesoft: Mathematics-based Software and Services for Education, Engineering, and Research Application Center, 2023. https://www.maplesoft.com/applications/Detail.aspx?id=155124.
[9] A. E. Holroyd, F. Ruskey and A. Williams, Shorthand universal cycles for permutations, Algorithmica 64(2) (2012), 215-245.
[10] P. Honner, Unscrambling the hidden secrets of superpermutations, Quanta Mag. 2019.
[11] R. Houston, Tackling the minimal superpermutation problem, 2014. arXiv:1408.5108 [math.CO].
[12] Nathaniel Johnston, The minimal superpermutation problem.
http://www.njohnston.ca/2013/04/the-minimal-superpermutation-problem/.
[13] Nathaniel Johnston, Non-uniqueness of minimal superpermutations, Discrete Mathematics 313(14) (2013), 1553-1557.
ar-Xiv:1303.4150. Bibcode:2013arXiv1303.4150J Retrieved March 16, 2014.
[14] D. E. Knuth, The Art of Computer Programming, Vol. 4A, Wesley, Upper Saddle River, New Jersey, 2011.
[15] P. J. Koutas and T. C. Hu, Shortest string containing all permutations, Math. 11(2) (1975), 125132.
[16] Aaron Williams, Hamiltonicity of the Cayley Digraph on the symmetric group generated by and 2013. arXiv:1307.2549v3.