A224986 a(n) = Product_{k=1..n-4} (n-k-2)!^(k*k!).

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

Table of n, a(n) for n=1..8.

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

Cf. A180632, A188428.

Sequence in context: A165642 A057528 A346565 * A164335 A132206 A139884

Adjacent sequences: A224983 A224984 A224985 * A224987 A224988 A224989

Keyword

nonn,easy

Author

Nathaniel Johnston, Apr 22 2013

Status

approved