login
Number of maximum-length 2-surprising sequences in n symbols.
1

%I #9 Feb 05 2018 15:00:07

%S 1,6,24,48,25440,554400

%N Number of maximum-length 2-surprising sequences in n symbols.

%C A sequence of symbols is 2-surprising if, for every pair of symbols X and Y, not necessarily distinct and every distance D, there is at most one position in t he sequence where X precedes Y by distance D. The maximum lengths are given in A008062.

%D Dennis E. Shasha, Puzzling Adventures, Scientific American 289(#12, 2003), 22.

%e The 2-surprising sequences in 3 symbols are:

%e (2012100) (1021200) (1120210) (2011210) (1202210) (2210120) (2101120) (1022120)

%e (2100201) (0021201) (0212201) (2102011) (0120211) (2010021) (2201021) (0122021)

%e (1200102) (0121102) (0012102) (1020012) (0211012) (1102012) (1201022) (0210122)

%e Thus a(3)=24.

%Y Cf. A008062.

%K nonn

%O 1,2

%A _John W. Layman_, Nov 17 2003