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

1, 1, 1, 1, 2, 96, 8153726976, 320352637207127391364950814323398779319161580421120

Offset: 1

Author

Nathaniel Johnston, Apr 22 2013

Keywords

• nonn
• easy

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

Examples

			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).
		

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.

Crossrefs

Cf. A180632, A188428.

Programs

Maple

seq(product((n-k-2)!^(k*k!),k=1..max(n-4,0)),n=1..8);

PARI

apply( {A224986(n)=prod(k=1,n-4,(n-k-2)!^(k*k!))}, [1..8]) \\ M. F. Hasler, Jul 29 2020