OFFSET
0,3
COMMENTS
Binomial transform of A093969 (n*Pell(n-2)).
For n>0, a(n) is the number of permutations of length n avoiding the partially ordered pattern (POP) {1>2, 1>3, 4>2, 4>3} of length 5. That is, the number of length n permutations having no subsequences of length 5 in which the elements in positions 1 and 4 are larger than the elements in positions 2 and 3. - Sergey Kitaev, Dec 11 2020
LINKS
Michael De Vlieger, Table of n, a(n) for n = 0..1871
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao and 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 (8,-20,16,-4).
FORMULA
a(n) = (n/4)*( (3+2*sqrt(2))*(2-sqrt(2))^n + (3-2*sqrt(2))*(2+sqrt(2))^n ).
From G. C. Greubel, Dec 27 2021: (Start)
a(2*n) = n*2^(n-1)*A002203(2*n-2).
a(2*n+1) = (2*n+1)*2^n*A000129(2*n-2). (End)
EXAMPLE
G.f. = x + 2*x^2 + 6*x^3 + 24*x^4 + 100*x^5 + 408*x^6 + ... - Michael Somos, Dec 30 2021
MATHEMATICA
LinearRecurrence[{8, -20, 16, -4}, {0, 1, 2, 6}, 25] (* Michael De Vlieger, May 01 2019 *)
a[ n_] := n 2^(Quotient[n-3, 2] + Mod[n, 2]) If[OddQ[n], Fibonacci, LucasL][n-2, 2]; (* Michael Somos, Dec 30 2021 *)
CoefficientList[Series[x (1-6x+10x^2)/(1-4x+2x^2)^2, {x, 0, 30}], x] (* Harvey P. Dale, Feb 18 2024 *)
PROG
(Magma) I:=[0, 1, 2, 6]; [n le 4 select I[n] else 8*Self(n-1) - 20*Self(n-2) +16*Self(n-3) -4*Self(n-4): n in [1..30]]; // G. C. Greubel, Dec 27 2021
(Sage)
def a(n):
if (n%2==0): return (n/2)*2^(n/2 -1)*lucas_number2(n-2, 2, -1)
else: return n*2^((n-1)/2)*lucas_number1(n-2, 2, -1)
[a(n) for n in range(30)] # G. C. Greubel, Dec 27 2021
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Paul Barry, Apr 21 2004
STATUS
approved