login
A111282
Number of permutations avoiding the patterns {1432,2431,3412,3421,4132,4231,4312,4321}; number of strong sorting class based on 1432.
3
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
OFFSET
1,2
COMMENTS
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, Jul 22 2008
a(n) = A025169(n-2) for n > 1. - Reinhard Zumkeller, Apr 08 2012
The sequence 0, 2, 0, 0, 1, 2, 6, 16, 42, 110, 288, 754, 1974, ... with g.f. H(x) = 2*x+(x^4-x^5+x^6)/(1-3*x+x^2) is the number of "splitted indecomposable weakly threshold graphs" on n nodes [Barrus, 2016]. - N. J. A. Sloane, Jul 25 2017
Number of permutations of length n>0 avoiding the partially ordered pattern (POP) {2>1, 2>4} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the second element is larger than the first and fourth elements. - Sergey Kitaev, Dec 09 2020
LINKS
M. Albert, R. Aldred, M. Atkinson, C. Handley, D. Holton, D. McCaughan and H. van Ditmarsch, Sorting Classes, Elec. J. of Comb. 12 (2005) #R31.
Michael D. Barrus, Weakly threshold graphs, arXiv preprint arXiv:1608.01358 [math.CO], 2016.
Hacène Belbachir, Soumeya Merwa Tebtoub, and László Németh, Ellipse Chains and Associated Sequences, J. Int. Seq., Vol. 23 (2020), Article 20.8.5.
Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
FORMULA
a(n) = 3a(n-1) - a(n-2), n > 3.
a(n) = A025169(n-2), n > 1. - R. J. Mathar, Aug 18 2008
From Paul Barry, 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)
EXAMPLE
x + 2*x^2 + 6*x^3 + 16*x^4 + 42*x^5 + 110*x^6 + 288*x^7 + ...
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 *)
PROG
(Haskell)
a111282 n = a111282_list !! (n-1)
a111282_list = 1 : a025169_list
-- Reinhard Zumkeller, Apr 08 2012
CROSSREFS
Sequence in context: A296625 A156664 A025169 * A358464 A115730 A191694
KEYWORD
nonn,easy
AUTHOR
Len Smiley, Nov 01 2005
STATUS
approved