|
|
A116702
|
|
Number of permutations of length n which avoid the patterns 123, 3241.
|
|
2
|
|
|
1, 2, 5, 13, 32, 74, 163, 347, 722, 1480, 3005, 6065, 12196, 24470, 49031, 98167, 196454, 393044, 786241, 1572653, 3145496, 6291202, 12582635, 25165523, 50331322, 100662944, 201326213, 402652777, 805305932, 1610612270, 3221224975, 6442450415, 12884901326
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Also number of permutations of length n which avoid the patterns 321, 2314, 2431; or avoid the patterns 123, 2314, 2431, etc.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: x*(1 - 3*x + 4*x^2 - x^3) / ((1 - x)^3*(1 - 2*x)).
Binomial transform of [1, 1, 2, 3, 3, 3, 3, ...]. - Gary W. Adamson, Oct 23 2007
a(n) = 3*2^(n-1) + n - (n+1)*(2+n)/2.
a(n) = 5*a(n-1) - 9*a(n-2) + 7*a(n-3) - 2*a(n-4) for n > 4.
(End)
|
|
MATHEMATICA
|
|
|
PROG
|
(PARI) Vec(x*(1 - 3*x + 4*x^2 - x^3) / ((1 - x)^3*(1 - 2*x)) + O(x^40)) \\ Colin Barker, Oct 19 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|