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

Author

Len Smiley, Nov 01 2005

Keywords

• nonn
• easy

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

Examples

			x + 2*x^2 + 6*x^3 + 16*x^4 + 42*x^5 + 110*x^6 + 288*x^7 + ...
		

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).

Programs

Haskell

a111282 n = a111282_list !! (n-1)
a111282_list = 1 : a025169_list
-- Reinhard Zumkeller, Apr 08 2012

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 *)

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)