%I #31 Oct 05 2015 11:30:44
%S 1,2,5,14,41,121,356,1044,3057,8948,26192,76674,224465,657137,1923817,
%T 5632105,16488346,48270655,141315320,413709331,1211159679,3545745012,
%U 10380388294,30389230117,88966354626,260454516946,762496740130
%N Number of permutations of length n which avoid the patterns 213, 51432.
%C 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
%C From _Bob Selcoe_, Jul 06 2014: (Start)
%C 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].
%C 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)
%H Vincenzo Librandi, <a href="/A116849/b116849.txt">Table of n, a(n) for n = 1..1000</a>
%H Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/maple/webbook/bookmain.html">Systematic Studies in Pattern Avoidance</a>, 2005.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (5,-8,6,-1).
%F G.f.: -(x*(x-1)^3)/(-6*x^3+x^4+8*x^2-5*x+1).
%F 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
%F From _Bob Selcoe_, Jul 06 2014: (Start)
%F a(n) = 2*a(n-1) + sum_{i=1..n-3} a(n-i-2)*[(i*(i+1)/2)+1].
%F 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)
%e From - _Bob Selcoe_, Jul 06 2014 (Start):
%e 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)
%e 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)
%p 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
%t 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 *)
%K nonn,easy
%O 1,2
%A _Lara Pudwell_, Feb 26 2006