|
Search: id:A111282
|
|
|
| A111282 |
|
Number of permutations avoiding the patterns {1432,2431,3412,3421,4132,4231,4312,4321}; number of strong sorting class based on 1432. |
|
+0
1
|
|
| 1, 2, 6, 16, 42, 110, 288, 754, 1974, 5168, 13530, 35422, 92736, 242786, 635622, 1664080, 4356618, 11405774, 29860704, 78176338, 204668310, 535828592, 1402817466, 3672623806, 9615053952, 25172538050, 65902560198, 172535142544
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
a(n-1) is the sum, over all Boolean n-strings, of the product of the lengths of the runs. For example, the Boolean 7-string (0,1,1,0,1,1,1) has four runs, whose lengths are 1,2,1 and 3, contributing a product of 6 to a(6). The 4 Boolean 2-strings contribute to a(3) as follows: 00 and 11 both contribute 2 and 01 and 10 both contribute 1. - David Callan (callan(AT)stat.wisc.edu), Jul 22 2008
|
|
REFERENCES
|
M. Albert, R. Aldred, M. Atkinson, C Handley, D. Holton, D. McCaughan and H. van Ditmarsch, Sorting Classes, Elec. J. of Comb. 12 (2005)
|
|
FORMULA
|
a(n)=3a(n-1)-a(n-2)
a(n)=A025169(n-2), n>1. [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Aug 18 2008]
Contribution from Paul Barry (pbarry(AT)wit.ie), Oct 13 2009: (Start)
G.f.: (1-x+x^2)/(1-3x+x^2).
a(n)=F(2n+1)+F(2n-2)+0^n. (End)
|
|
MATHEMATICA
|
a[1] = 1; a[2] = 2; a[3] = 6; a[n_] := a[n] = 3a[n - 1] - a[n - 2]; Table[a[n], {n, 28}] (* Robert G. Wilson v *)
|
|
CROSSREFS
|
Adjacent sequences: A111279 A111280 A111281 this_sequence A111283 A111284 A111285
Sequence in context: A102699 A156664 A025169 this_sequence A115730 A003142 A027994
|
|
KEYWORD
|
nonn,new
|
|
AUTHOR
|
Len Smiley ( smiley (at) math.uaa.alaska.edu ), Nov 01 2005
|
|
EXTENSIONS
|
More terms from Robert G. Wilson v (rgwv(at)rgwv.com), Nov 04 2005
|
|
|
Search completed in 0.002 seconds
|
