login
A224986
a(n) = Product_{k=1..n-4} (n-k-2)!^(k*k!).
4
1, 1, 1, 1, 2, 96, 8153726976, 320352637207127391364950814323398779319161580421120
OFFSET
1,5
COMMENTS
Consider words on n symbols that contain every permutation of those n symbols as contiguous substrings. The minimal length of such a string was conjectured to equal A007489(n) (see A180632). This sequence is a lower bound on the number of distinct (up to relabeling the symbols) such strings of the conjectured minimal length.
It was conjectured in the Ashlock paper that, for all n, there is only one string of length A007489(n) containing all permutations. This sequence shows that this conjecture fails as n grows.
In 2014 Houston has shown that the first conjecture about the minimal length is also false for all n > 5. In particular, A180632(6) <= 872 = A007489(n). - M. F. Hasler, Jul 28 2020
The next term a(9) ~ 2.18e291 is too large to be displayed here. - M. F. Hasler, Jul 29 2020
REFERENCES
D. Ashlock and J. Tillotson, Construction of small superpermutations and minimal injective superstrings. Congressus Numerantium, 93 (1993), 91-98.
LINKS
Robin Houston, Tackling the Minimal Superpermutation Problem, arXiv:1408.5108 [math.CO], 2014.
Nathaniel Johnston, Non-uniqueness of minimal superpermutations, arXiv:1303.4150 [math.CO], 2013; Discrete Math., 313 (2013), 1553-1557.
Nathaniel Johnston, The Minimal Superpermutation Problem, 2013.
EXAMPLE
a(n) = 1 for n <= 4, which agrees with the fact that the minimal strings containing all permutations in these cases are unique (see A180632).
MAPLE
seq(product((n-k-2)!^(k*k!), k=1..max(n-4, 0)), n=1..8);
PROG
(PARI) apply( {A224986(n)=prod(k=1, n-4, (n-k-2)!^(k*k!))}, [1..8]) \\ M. F. Hasler, Jul 29 2020
CROSSREFS
Sequence in context: A165642 A057528 A346565 * A164335 A132206 A139884
KEYWORD
nonn,easy
AUTHOR
Nathaniel Johnston, Apr 22 2013
STATUS
approved