|
%I #15 Aug 06 2020 22:11:49
%S 1,1,1,1,2,96,8153726976,
%T 320352637207127391364950814323398779319161580421120
%N a(n) = Product_{k=1..n-4} (n-k-2)!^(k*k!).
%C 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.
%C 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.
%C 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
%C The next term a(9) ~ 2.18e291 is too large to be displayed here. - _M. F. Hasler_, Jul 29 2020
%D D. Ashlock and J. Tillotson, Construction of small superpermutations and minimal injective superstrings. Congressus Numerantium, 93 (1993), 91-98.
%H Robin Houston, <a href="http://arxiv.org/abs/1408.5108">Tackling the Minimal Superpermutation Problem</a>, arXiv:1408.5108 [math.CO], 2014.
%H Nathaniel Johnston, <a href="http://arxiv.org/abs/1303.4150">Non-uniqueness of minimal superpermutations</a>, arXiv:1303.4150 [math.CO], 2013; Discrete Math., 313 (2013), 1553-1557.
%H Nathaniel Johnston, <a href="http://www.njohnston.ca/2013/04/the-minimal-superpermutation-problem/">The Minimal Superpermutation Problem</a>, 2013.
%e 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).
%p seq(product((n-k-2)!^(k*k!),k=1..max(n-4,0)),n=1..8);
%o (PARI) apply( {A224986(n)=prod(k=1,n-4,(n-k-2)!^(k*k!))}, [1..8]) \\ _M. F. Hasler_, Jul 29 2020
%Y Cf. A180632, A188428.
%K nonn,easy
%O 1,5
%A _Nathaniel Johnston_, Apr 22 2013
| 