login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A116717 Number of permutations of length n which avoid the patterns 231, 1423, 3214. 1
1, 2, 5, 12, 26, 52, 98, 177, 310, 531, 895, 1491, 2463, 4044, 6611, 10774, 17520, 28446, 46136, 74771, 121116, 196117, 317485, 513877, 831661, 1345862, 2177873, 3524112, 5702390, 9226936, 14929790, 24157221, 39087538, 63245319, 102333451, 165579399, 267913515 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

LINKS

Colin Barker, Table of n, a(n) for n = 1..1000

Michael Dairyko, Lara Pudwell, Samantha Tyner, Casey Wynn, Non-contiguous pattern avoidance in binary trees. Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227.

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

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

FORMULA

G.f.: -x*(x^4-x^3-2*x^2+2*x-1) / ((x^2+x-1)*(x-1)^3).

a(n) = A000045(n+5) - A000124(n+2). - Charlie Marion and Lara Pudwell, Jan 15 2014

From Colin Barker, Oct 20 2017: (Start)

a(n) = -3 + (2^(-1- n)*((1-sqrt(5))^n*(-11+5*sqrt(5)) + (1+sqrt(5))^n*(11+5*sqrt(5)))) / sqrt(5) - n - (1 + n)*(2 + n)/2.

a(n) = 4*a(n-1) - 5*a(n-2) + a(n-3) + 2*a(n-4) - a(n-5) for n>5.

(End)

a(n) = 1 + Sum_{k=1..n} Sum_{j=1..k} Sum_{i=1..j-1} Fibonacci(i). - Ehren Metcalfe, Oct 22 2017

MATHEMATICA

LinearRecurrence[{4, -5, 1, 2, -1}, {1, 2, 5, 12, 26}, 40] (* Vincenzo Librandi, Oct 22 2017 *)

PROG

(PARI) Vec(x*(1 - 2*x + 2*x^2 + x^3 - x^4) / ((1 - x)^3*(1 - x - x^2)) + O(x^40)) \\ Colin Barker, Oct 20 2017

(MAGMA) I:=[1, 2, 5, 12, 26]; [n le 5 select I[n] else 4*Self(n-1)-5*Self(n-2)+Self(n-3)+2*Self(n-4)-Self(n-5): n in [1..40]]; // Vincenzo Librandi, Oct 22 2017

CROSSREFS

Sequence in context: A132977 A027927 A221948 * A116725 A193263 A221949

Adjacent sequences:  A116714 A116715 A116716 * A116718 A116719 A116720

KEYWORD

nonn,easy

AUTHOR

Lara Pudwell, Feb 26 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 11 23:53 EDT 2020. Contains 335654 sequences. (Running on oeis4.)