|
%I #38 Jan 05 2021 19:05:55
%S 1,2,6,16,42,110,288,754,1974,5168,13530,35422,92736,242786,635622,
%T 1664080,4356618,11405774,29860704,78176338,204668310,535828592,
%U 1402817466,3672623806,9615053952,25172538050,65902560198,172535142544
%N Number of permutations avoiding the patterns {1432,2431,3412,3421,4132,4231,4312,4321}; number of strong sorting class based on 1432.
%C 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
%C a(n) = A025169(n-2) for n > 1. - _Reinhard Zumkeller_, Apr 08 2012
%C 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
%C 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
%H Reinhard Zumkeller, <a href="/A111282/b111282.txt">Table of n, a(n) for n = 1..1000</a>
%H M. Albert, R. Aldred, M. Atkinson, C. Handley, D. Holton, D. McCaughan and H. van Ditmarsch, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r31">Sorting Classes</a>, Elec. J. of Comb. 12 (2005) #R31.
%H Michael D. Barrus, <a href="https://arxiv.org/abs/1608.01358">Weakly threshold graphs</a>, arXiv preprint arXiv:1608.01358 [math.CO], 2016.
%H Hacène Belbachir, Soumeya Merwa Tebtoub, and László Németh, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Nemeth/nemeth7.html">Ellipse Chains and Associated Sequences</a>, J. Int. Seq., Vol. 23 (2020), Article 20.8.5.
%H Alice L. L. Gao, Sergey Kitaev, <a href="https://arxiv.org/abs/1903.08946">On partially ordered patterns of length 4 and 5 in permutations</a>, arXiv:1903.08946 [math.CO], 2019.
%H Alice L. L. Gao, Sergey Kitaev, <a href="https://doi.org/10.37236/8605">On partially ordered patterns of length 4 and 5 in permutations</a>, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3, -1).
%F a(n) = 3a(n-1) - a(n-2), n > 3.
%F a(n) = A025169(n-2), n > 1. - _R. J. Mathar_, Aug 18 2008
%F From _Paul Barry_, Oct 13 2009: (Start)
%F G.f.: (1 - x + x^2)/(1 - 3x + x^2).
%F a(n) = F(2n+1) + F(2n-2) + 0^n. (End)
%e x + 2*x^2 + 6*x^3 + 16*x^4 + 42*x^5 + 110*x^6 + 288*x^7 + ...
%t 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_ *)
%o (Haskell)
%o a111282 n = a111282_list !! (n-1)
%o a111282_list = 1 : a025169_list
%o -- _Reinhard Zumkeller_, Apr 08 2012
%K nonn,easy
%O 1,2
%A _Len Smiley_, Nov 01 2005
|
