A111282 Number of permutations avoiding the patterns {1432,2431,3412,3421,4132,4231,4312,4321}; number of strong sorting class based on 1432.

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

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

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.

Index entries for linear recurrences with constant coefficients, signature (3, -1).

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

Adjacent sequences: A111279 A111280 A111281 * A111283 A111284 A111285

Keyword

nonn,easy

Author

Len Smiley, Nov 01 2005

Status

approved