2-surprising sequences

[John Layman]

Neil (Nov 14, 2003):
the latest issue of Scientific American (Dec 2003), page 122,
has a column by D E Shasha about surprising sequences

Me:
I have just submitted the following two sequences.  I am quite surprised by the 
rapid jump in the second sequence, A089973, from a(4)=48 to a(5)=25440.  Can 
anyone confirm my values for these terms?

John 


%I A089972
%S A089972 2,4,7,10,12,15
%N A089972 Maximum length of a 2-surprising sequence in n symbols.
%C A089972 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.
%D A089972 Dennis E. Shasha, Puzzling Adventures, Scientific American 289(Dec 2003),1
22.
%e A089972 {0,1,1,2,0,3,2,3,1,0}, {0,0,1,2,3,2,4,1,0,4,3,1}, and {0,0,1,2,3,1,4,5,2,5
,0,3,4,1,0} are 2-surprising sequences of 4, 5 and 6 symbols, respectively, and no lo
nger sequences of 4,5, or 6 symbols exist, so a(4)=10, a(5)=12, and a(6)=15.  A 2-sur
prising sequence of 7 symbols is {0,0,1,2,3,1,4,5,6,2,6,4,0,3,5,1,0,2}, showing that 
a(7) is at least 18.
%Y A089972 A089973
%O A089972 1
%K A089972 ,nonn,
%A A089972 John W. Layman (layman at math.vt.edu), Nov 17 2003
RH 
RA 128.173.42.69
RU 
RI 


%I A089973
%S A089973 1,6,24,48,25440,554400
%N A089973 Number of maximum-length 2-surprising sequences in n symbols.
%C A089973 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 A0899
72.
%D A089973 Dennis E. Shasha, Puzzling Adventures, Scientific American 289(Dec 2003),1
22.
%e A089973 The 2-surprising sequences in 3 symbols are:
(2012100) (1021200) (1120210) (2011210) (1202210) (2210120) (2101120) (1022120)
(2100201) (0021201) (0212201) (2102011) (0120211) (2010021) (2201021) (0122021)
(1200102) (0121102) (0012102) (1020012) (0211012) (1102012) (1201022) (0210122)
Thus a(3)=24.
%Y A089973 A089972
%O A089973 1
%K A089973 ,nonn,
%A A089973 John W. Layman (layman at math.vt.edu), Nov 17 2003
RH 
RA 128.173.42.69
RU 
RI