A295873 Number of permutations of length n which avoid the patterns 1342, 2413, 3124 and 3142.
1, 1, 2, 6, 20, 68, 231, 781, 2629, 8821, 29530, 98706, 329592, 1099792, 3668127, 12230505, 40771337, 135895689, 452914658, 1509385902, 5029980252, 16761785436, 55855539047, 186125915029, 620217261197, 2066704787645, 6886704234970, 22947920663130, 76467083518464
Offset: 0
Links
- Colin Barker, Table of n, a(n) for n = 0..1000
- Christian Bean, Bjarki Gudmundsson, Henning Ulfarsson, Automatic discovery of structural rules of permutation classes, arXiv:1705.04109 [math.CO], 2017.
- Index entries for linear recurrences with constant coefficients, signature (7,-16,14,-5,1).
Programs
-
PARI
Vec((1 - 3*x + x^2)^2 / ((1 - x)*(1 - 6*x + 10*x^2 - 4*x^3 + x^4)) + O(x^40)) \\ Colin Barker, Dec 27 2017
Formula
G.f.: (1-6*x+11*x^2-6*x^3+x^4)/(1-7*x+16*x^2-14*x^3+5*x^4-x^5).
From Colin Barker, Dec 27 2017: (Start)
G.f.: (1 - 3*x + x^2)^2 / ((1 - x)*(1 - 6*x + 10*x^2 - 4*x^3 + x^4)).
a(n) = 7*a(n-1) - 16*a(n-2) + 14*a(n-3) - 5*a(n-4) + a(n-5) for n>4.
(End)