A116849 Number of permutations of length n which avoid the patterns 213, 51432.

1, 2, 5, 14, 41, 121, 356, 1044, 3057, 8948, 26192, 76674, 224465, 657137, 1923817, 5632105, 16488346, 48270655, 141315320, 413709331, 1211159679, 3545745012, 10380388294, 30389230117, 88966354626, 260454516946, 762496740130

Offset: 1

Author

Lara Pudwell, Feb 26 2006

Keywords

• nonn
• easy

Comments

a(n) is the binomial transform of the tetranacci numbers (A007318 transform of A000078). For example: a(6) = 121 = 1*1 + 5*1 + 10*2 + 10*4 + 5*8 + 1*15. - Bob Selcoe, Jun 28 2014

From Bob Selcoe, Jul 06 2014: (Start)

In general, the equation for the binomial transform of m-nacci numbers is: a(n) = 2*a(n-1) + sum_({i=0..n-2}, {j=0..m-2}) a(n-i-2)*sum_(i!/(j!*(i-j)!), where i>=j and a(0)=1. So in this sequence, where m=4 (therefore m-2=2) and the offset is 1 (rather than 0): a(n) = 2*a(n-1) + sum_{i=0..n-3} a(n-i-2)*[(i*(i+1)/2)+1].

Another general equation for the binomial transform of m-nacci numbers (when a(0)=1) is: a(n) = 2*a(n-1) + sum_{i=2..m} a(n-i)*2^(i-2) + sum_({i=m+1..n}, {j=0..i-m-1}) a(n-i)*(2^(i-2) - sum_((i-2)!/(j!*(i-2-j)!). Thus, when m=4 and offset is 1: a(n) = 2*a(n-1) + sum_{i=2..4} a(n-i)*2^(i-2) + sum_({i=5..n-1}, {j=0..i-5}) a(n-i)*(2^(i-2) - sum_[(i-2)!/(j!*(i-2-j)!)]). (End)

Examples

			From _Bob Selcoe_, Jul 06 2014: (Start)
a(7) = 356 = 2*121 + 41*(0*1/2 + 1) + 14*(1*2/2 + 1) + 5*(2*3/2 + 1) + 2*(3*4/2 + 1) + 1*(4*5/2 + 1)
a(8) = 1044 = 2*356 + 121*2^0 + 41*2^1 + 14*2^2 + 5*(2^3 - 3!/(0!*3!)) + 2*(2^4 - [4!/(0!*4!) + 4!/(1!*3!)]) + 1*(2^5 - [5!/(0!*5!) + 5!/(1!*4!) + 5!/(2!*3!)]). (End)
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.
• Index entries for linear recurrences with constant coefficients, signature (5,-8,6,-1).

Programs

Maple

A116849 := proc(n) coeftayl( -(x*(x-1)^3)/(-6*x^3+x^4+8*x^2-5*x+1), x=0, n); end proc: seq(A116849(n), n=1..30); # Wesley Ivan Hurt, Jul 06 2014

Mathematica

Rest[CoefficientList[Series[-(x (x - 1)^3)/(- 6 x^3 + x^4 + 8 x^2 - 5 x + 1), {x, 0, 40}], x] ](* Vincenzo Librandi, Jun 29 2014 *)

Formula

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

a(n) = 5*a(n-1) -8*a(n-2) +6*a(n-3) -a(n-4) for n>3. - Vincenzo Librandi, Jun 29 2014

From Bob Selcoe, Jul 06 2014: (Start)

a(n) = 2*a(n-1) + sum_{i=1..n-3} a(n-i-2)*[(i*(i+1)/2)+1].

a(n) = 2*a(n-1) + sum_{i=2..4} a(n-i)*2^(i-2) + sum_({i=5..n-1}, {j=0..i-5}) a(n-i)*(2^(i-2) - sum_[(i-2)!/(j!*(i-2-j)!)]). (End)