login
Number of permutations avoiding the patterns {2413,2431,4213,3412,3421,4231,4321,4312}; number of strong sorting class based on 2413.
1

%I #32 May 07 2021 19:41:45

%S 1,1,2,6,16,40,100,252,636,1604,4044,10196,25708,64820,163436,412084,

%T 1039020,2619764,6605420,16654772,41993004,105880308,266964460,

%U 673118772,1697188012,4279255412,10789627756,27204748468,68593500716,172950260724,436073277676

%N Number of permutations avoiding the patterns {2413,2431,4213,3412,3421,4231,4321,4312}; number of strong sorting class based on 2413.

%C a(n) = term (1,1) in M^n, M = the 4x4 matrix [1,1,1,1; 0,1,0,1; 0,0,1,1; 1,0,0,1]. - _Gary W. Adamson_, Apr 29 2009

%C Number of permutations of length n>0 avoiding the partially ordered pattern (POP) {1>2, 1>4} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the second and fourth elements. - _Sergey Kitaev_, Dec 09 2020

%H Michael De Vlieger, <a href="/A111281/b111281.txt">Table of n, a(n) for n = 0..2490</a>

%H M. Albert, R. Aldred, M. Atkinson, C Handley, D. Holton, D. McCaughan and H. van Ditmarsch, <a href="https://doi.org/10.37236/1928">Sorting Classes</a>, Elec. J. of Comb. 12 (2005) R31.

%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 Kai Ting Keshia Yap, David Wehlau, and Imed Zaguia, <a href="https://arxiv.org/abs/2101.12061">Permutations Avoiding Certain Partially-ordered Patterns</a>, arXiv:2101.12061 [math.CO], 2021.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,2).

%F a(n) = 3*a(n-1)-2*a(n-2)+2*a(n-3).

%F G.f.: 1+x*(1-x+2*x^2)/(1-3*x+2*x^2-2*x^3). - _Colin Barker_, Jan 16 2012

%t a[1] = 1; a[2] = 2; a[3] = 6; a[n_] := a[n] = 3a[n - 1] - 2a[n - 2] + 2a[n - 3]; Table[a[n], {n, 28}] (* _Robert G. Wilson v_ *)

%K nonn,easy

%O 0,3

%A _Len Smiley_, Nov 01 2005

%E More terms from _Robert G. Wilson v_, Nov 04 2005

%E a(0)=1 prepended by _Alois P. Heinz_, May 07 2021