cp's OEIS Frontend

A071077 Number of permutations that avoid the generalized pattern 1234-5.

%I A071077 #24 Mar 24 2024 03:17:11
%S A071077 1,1,2,6,24,119,705,4857,38142,336291,3289057,35337067,413698248,
%T A071077 5241768017,71465060725,1043175024243,16231998346794,268207096127991,
%U A071077 4690005160446721,86528908665043683,1679764981327051508,34226671269330933413,730361830628447403029
%N A071077 Number of permutations that avoid the generalized pattern 1234-5.
%H A071077 Alois P. Heinz, <a href="/A071077/b071077.txt">Table of n, a(n) for n = 0..450</a>
%H A071077 Sergey Kitaev, <a href="https://web.archive.org/web/20040902121307/http://www.ms.uky.edu/~kitaev/index_files/Papers/partial_order_patterns_perm.pdf">Partially Ordered Generalized Patterns</a>, preprint.
%H A071077 Sergey Kitaev, <a href="http://dx.doi.org/10.1016/j.disc.2004.03.017">Partially Ordered Generalized Patterns</a>, Discrete Math. 298 (2005), no. 1-3, 212-229.
%F A071077 E.g.f.: exp(int(A(y), y=0..x)), where A(y) = 1/(Sum_{i>=0} y^{4*i}/(4*i)! - Sum_{i>=0} y^{4*i+1}/(4*i+1)!).
%F A071077 Let b(n) = A117158(n) = number of permutations of [n] that avoid the consecutive pattern 1234. Then a(n) = Sum_{i = 0..n-1} binomial(n-1,i)*b(i)*a(n-1-i) with a(0) = b(0) = 1. [See the recurrence for A_n and B_n in the proof of Theorem 13 in Kitaev's papers.] - _Petros Hadjicostas_, Oct 31 2019
%p A071077 b:= proc(u, o, t) option remember; `if`(u+o=0, 1, add(
%p A071077       `if`(t=2 and o>j, 0, b(u+j-1, o-j, t+1)), j=1..o)+
%p A071077        add(b(u-j, o+j-1, 0), j=1..u))
%p A071077     end:
%p A071077 a:= n-> b(n, 0$2):
%p A071077 seq(a(n), n=0..25);  # _Alois P. Heinz_, Nov 14 2015
%t A071077 b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Sum[If[t == 2 && o>j, 0, b[u+j-1, o-j, t+1]], {j, 1, o}] + Sum[b[u-j, o+j-1, 0], {j, 1, u}]];
%t A071077 a[n_] := b[n, 0, 0];
%t A071077 a /@ Range[0, 25] (* _Jean-François Alcover_, Apr 23 2020, after _Alois P. Heinz_ *)
%Y A071077 Cf. A071088, A071075, A071076, A117158.
%K A071077 nonn
%O A071077 0,3
%A A071077 _Sergey Kitaev_, May 26 2002
%E A071077 Corrected and extended by _Vladeta Jovovic_, May 28 2002