|
|
A116734
|
|
Number of permutations of length n which avoid the patterns 231, 1432, 4123.
|
|
1
|
|
|
1, 2, 5, 12, 25, 50, 97, 184, 345, 642, 1189, 2196, 4049, 7458, 13729, 25264, 46481, 85506, 157285, 289308, 532137, 978770, 1800257, 3311208, 6090281, 11201794, 20603333, 37895460, 69700641, 128199490, 235795649, 433695840, 797691041
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
G.f.: A(x) = -{x(x^2+x^3+1-x)}/{(x-1)^2(x^3+x^2+x-1)}
a(0)=0, a(1)=1, a(2)=2, then a(n) = a(n-1) + a(n-2) + a(n-3) + 2*n - 4. [From Gerald McGarvey, Oct 06 2009]
|
|
MATHEMATICA
|
LinearRecurrence[{3, -2, 0, -1, 1}, {1, 2, 5, 12, 25}, 40] (* Harvey P. Dale, Jan 21 2016 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|