login
Number of permutations of [n] avoiding the consecutive pattern 45321.
27

%I #58 Oct 27 2023 21:38:29

%S 1,1,2,6,24,119,708,4914,38976,347765,3447712,37598286,447294144,

%T 5764747515,80011430240,1189835682714,18873422539776,318085061976105,

%U 5676223254661760,106919460527212950,2119973556022047744,44136046410218669055,962630898723772565760

%N Number of permutations of [n] avoiding the consecutive pattern 45321.

%C a(n) is the number of permutations on [n] that avoid the consecutive pattern 45321. It is the same as the number of permutations which avoid 12354, 21345 or 54312.

%H Alois P. Heinz, <a href="/A202213/b202213.txt">Table of n, a(n) for n = 0..200</a> (terms n = 1..40 from Ray Chandler)

%H A. Baxter, B. Nakamura, and D. Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/auto.html">Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes</a>, 2011.

%H Sergi Elizalde and Marc Noy, <a href="https://doi.org/10.1016/S0196-8858(02)00527-4 ">Consecutive patterns in permutations</a>, Adv. Appl. Math. 30 (2003), 110-125; see Theorem 3.2 (p. 116) with m = a = 3 and u = 0.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PochhammerSymbol.html">Pochhammer Symbol</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Falling_and_rising_factorials">Falling and rising factorials</a>.

%F From _Petros Hadjicostas_, Nov 02 2019: (Start)

%F E.g.f.: 1/W(z), where W(z) = 1 + Sum_{n >= 0} (-1)^(n+1)* z^(4*n+1)/(b(n)*(4*n+1)) with b(n) = A329070(n,4) = (4*n)!/(4^n*(1/4)_n). (Here (x)_n = x*(x + 1)*...*(x + n - 1) is the Pochhammer symbol, or rising factorial, which is denoted by (x)^n in some papers and books.) The function W(z) satisfies the o.d.e. W^(4)(z) + z*W'(z) = 0 with W(0) = 1, W'(0) = -1, and W^(k)(0) = 0 for k = 2..3. [See Theorem 3.2 (with m = a = 3 and u = 0) in Elizalde and Noy (2003).]

%F a(n) = Sum_{m = 0..floor((n-1)/4)} (-4)^m * (1/4)_m * binomial(n, 4*m+1) * a(n-4*m-1) for n >= 1 with a(0) = 1. (End)

%p b:= proc(u, o, t) option remember; `if`(u+o=0, 1,

%p add(b(u+j-1, o-j, `if`(u+j-1<j, 0, j)), j=1..o)+

%p `if`(t=-2, 0, add(b(u-j, o+j-1, `if`(j<t, 0,

%p `if`(t>0, -1, `if`(t=-1, -2, 0)))), j=1..u)))

%p end:

%p a:= n-> b(n, 0$2):

%p seq(a(n), n=0..40); # _Alois P. Heinz_, Nov 19 2013

%t b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Sum[b[u+j-1, o-j, If[u+j-1 < j, 0, j]], {j, 1, o}] + If[t == -2, 0, Sum[b[u-j, o+j-1, If[j<t, 0, If[t>0, -1, If[t == -1, -2, 0]]]], {j, 1, u}]]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Mar 12 2015, after _Alois P. Heinz_ *)

%Y Cf. A177523, A202214-A202236, A329070.

%Y Column k = 0 of A264781 and row m = 2 of A327722.

%K nonn

%O 0,3

%A _Ray Chandler_, Dec 14 2011