OFFSET
0,3
COMMENTS
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
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
LINKS
Michael De Vlieger, Table of n, a(n) for n = 0..2490
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.
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.
Kai Ting Keshia Yap, David Wehlau, and Imed Zaguia, Permutations Avoiding Certain Partially-ordered Patterns, arXiv:2101.12061 [math.CO], 2021.
Index entries for linear recurrences with constant coefficients, signature (3,-2,2).
FORMULA
a(n) = 3*a(n-1)-2*a(n-2)+2*a(n-3).
G.f.: 1+x*(1-x+2*x^2)/(1-3*x+2*x^2-2*x^3). - Colin Barker, Jan 16 2012
MATHEMATICA
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 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Len Smiley, Nov 01 2005
EXTENSIONS
More terms from Robert G. Wilson v, Nov 04 2005
a(0)=1 prepended by Alois P. Heinz, May 07 2021
STATUS
approved