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

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)

Links

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

Rob Pratt, Solutions for n = 5, 6, 7

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

Cf. A000166, A180632.

Sequence in context: A047035 A080042 A364643 * A366732 A165588 A289191

Adjacent sequences: A324142 A324143 A324144 * A324146 A324147 A324148

Keyword

nonn,more

Author

José Eduardo Castrejón González, Feb 17 2019

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