login
A324145
Minimal length of a string over the alphabet A = {1,2,...,n} that contains every derangement of A as a substring exactly once.
1
0, 2, 4, 22, 102, 662, 4678
OFFSET
1,2
COMMENTS
Such strings could be called superderangements (compare A180632).
From Rob Pratt, Feb 22 2019: (Start)
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.
For n = 2 and 3, the optimal solution is unique.
For n = 4, there are exactly four optimal solutions:
4321431241314234123421
4312413142341234214321
4312341231424134214321
4321431234123142413421
(End)
EXAMPLE
Examples of minimal superderangements for 2,3,4 symbols:
For n = 2: 21, length 2.
For n = 3: 2312, length = 4 (For n=3 there are just two derangements, 231 and 312, so 2312 is clearly optimal.)
For n = 4: 4312413142341234214321, length = 22 (optimality established by Rob Pratt, Feb 21 2019).
For examples for n = 5, 6, and 7 that were discovered and proved optimal by Rob Pratt using SAS, see the link.
Strings for n = 4,5,6,7 were earlier found by Sigurd Kittilsen and Lars Tveito, although they did not prove they were optimal.
CROSSREFS
Sequence in context: A047035 A080042 A364643 * A366732 A165588 A289191
KEYWORD
nonn,more
EXTENSIONS
a(4) confirmed and a(5)-a(7) found by Rob Pratt, Feb 21 2019
Edited by N. J. A. Sloane, Feb 21 2019
STATUS
approved