cp's OEIS Frontend

A324145 Minimal length of a string over the alphabet A = {1,2,...,n} that contains every derangement of A as a substring exactly once.

%I A324145 #37 Jan 11 2020 03:08:05
%S A324145 0,2,4,22,102,662,4678
%N A324145 Minimal length of a string over the alphabet A = {1,2,...,n} that contains every derangement of A as a substring exactly once.
%C A324145 Such strings could be called superderangements (compare A180632).
%C A324145 From _Rob Pratt_, Feb 22 2019: (Start)
%C A324145 I used the TSP (Traveling Salesman) solver in SAS, which discovered the values reported for n = 4 through 7 and proved that they are optimal.
%C A324145 For n = 2 and 3, the optimal solution is unique.
%C A324145 For n = 4, there are exactly four optimal solutions:
%C A324145 4321431241314234123421
%C A324145 4312413142341234214321
%C A324145 4312341231424134214321
%C A324145 4321431234123142413421
%C A324145 (End)
%H A324145 Rob Pratt, <a href="/A324145/a324145.txt">Solutions for n = 5, 6, 7</a>
%e A324145 Examples of minimal superderangements for 2,3,4 symbols:
%e A324145 For n = 2: 21, length 2.
%e A324145 For n = 3: 2312, length = 4 (For n=3 there are just two derangements, 231 and 312, so 2312 is clearly optimal.)
%e A324145 For n = 4: 4312413142341234214321, length = 22 (optimality established by _Rob Pratt_, Feb 21 2019).
%e A324145 For examples for n = 5, 6, and 7 that were discovered and proved optimal by _Rob Pratt_ using SAS, see the link.
%e A324145 Strings for n = 4,5,6,7 were earlier found by _Sigurd Kittilsen_ and _Lars Tveito_, although they did not prove they were optimal.
%Y A324145 Cf. A000166, A180632.
%K A324145 nonn,more
%O A324145 1,2
%A A324145 _José Eduardo Castrejón González_, Feb 17 2019
%E A324145 a(4) confirmed and a(5)-a(7) found by _Rob Pratt_, Feb 21 2019
%E A324145 Edited by _N. J. A. Sloane_, Feb 21 2019