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

%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