A111586 G.f.: -x*(1+x+x^2+2*x^3+3*x^4+3*x^5+x^6-x^7-x^9)/((1+x)*(-1+2*x+x^3)).

0, 1, 2, 5, 12, 28, 62, 136, 299, 661, 1456, 3213, 7085, 15628, 34467, 76021, 167668, 369805, 815629, 1798928, 3967659, 8750949, 19300824, 42569309, 93889565, 207079956, 456729219, 1007348005, 2221775964, 4900281149, 10807910301, 23837596568, 52575474283, 115958858869

Offset

0,3

References

V. Vatter, The Enumeration and Structure of Permutation Classes, Ph. D. Dissertation, Rutgers Univ., Math. Dept., 2006.

Links

Paolo Xausa, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (1,2,1,1).

Formula

a(n) = 2*a(n-1) + a(n-3) - 2*(-1)^n for n >= 10. - Greg Dresden, May 18 2020

Mathematica

LinearRecurrence[{1, 2, 1, 1}, {0, 1, 2, 5, 12, 28, 62, 136, 299, 661, 1456}, 35] (* Paolo Xausa, Jun 04 2026 *)

Prog

(PARI) a(n)=if(n>6, ([0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0, 1; 1, 1, 2, 1]^(n-7)*[136; 299; 661; 1456])[1, 1], [0, 1, 2, 5, 12, 28, 62][n+1]) \\ Charles R Greathouse IV, Jun 03 2026

Crossrefs

Sequence in context: A202604 A391051 A118898 * A192657 A320590 A006979

Adjacent sequences: A111583 A111584 A111585 * A111587 A111588 A111589

Keyword

nonn,easy

Author

N. J. A. Sloane, Nov 17 2005

Status

approved