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

Author

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

Keywords

• nonn
• more

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)

Examples

			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.
		

Links

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

Crossrefs

Cf. A000166, A180632.

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