cp's OEIS Frontend

A071076 Number of permutations that avoid the generalized pattern 123-4.

%I A071076 #46 Feb 21 2025 12:15:20
%S A071076 1,1,2,6,23,108,598,3815,27532,221708,1970251,19150132,202064380,
%T A071076 2300071071,28092017668,366425723926,5083645400819,74745472084176,
%U A071076 1160974832572274,18995175706664735,326531476287842760,5883736110875887560,110893188848753125475
%N A071076 Number of permutations that avoid the generalized pattern 123-4.
%H A071076 Alois P. Heinz, <a href="/A071076/b071076.txt">Table of n, a(n) for n = 0..450</a>
%H A071076 A. M. Baxter, <a href="https://www.semanticscholar.org/paper/Algorithms-for-permutation-statistics-Zeilberger-Baxter/2c5d79e361d3aecb25c380402144177ad7cd9dc8">Algorithms for Permutation Statistics</a>, Ph. D. Dissertation, Rutgers University, May 2011.
%H A071076 Andrew M. Baxter and Lara K. Pudwell, <a href="http://arxiv.org/abs/1108.2642">Enumeration schemes for dashed patterns</a>, arXiv preprint arXiv:1108.2642 [math.CO], 2011.
%H A071076 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 A071076 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.
%H A071076 Yan Wang, Qi Fang, Shishuo Fu, Sergey Kitaev, and Haijun Li, <a href="https://arxiv.org/abs/2502.10128">Consecutive and quasi-consecutive patterns: des-Wilf classifications and generating functions</a>, arXiv:2502.10128 [math.CO], 2025. See p. 9.
%F A071076 E.g.f.: exp(int(A(y), y=0..x)), where A(y) = (sqrt(3)/2)*exp(y/2)/cos((sqrt(3)/2)*y + Pi/6).
%F A071076 Let b(n) = A049774(n) = number of permutations of [n] that avoid the consecutive pattern 123. 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.] -
%p A071076 b:= proc(u, o, t) option remember; `if`(u+o=0, 1, add(
%p A071076       `if`(t=1 and o>j, 0, b(u+j-1, o-j, t+1)), j=1..o)+
%p A071076        add(b(u-j, o+j-1, 0), j=1..u))
%p A071076     end:
%p A071076 a:= n-> b(n, 0$2):
%p A071076 seq(a(n), n=0..25);  # _Alois P. Heinz_, Nov 14 2015
%t A071076 b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, Sum[If[t == 1 && 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}]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Feb 01 2016, after _Alois P. Heinz_ *)
%Y A071076 Cf. A049774, A071088, A071075, A071077.
%K A071076 nonn
%O A071076 0,3
%A A071076 _Sergey Kitaev_, May 26 2002
%E A071076 More terms from _Vladeta Jovovic_, May 28 2002
%E A071076 Link added by _Andrew Baxter_, May 17 2011
%E A071076 Typos in formula corrected by _Vaclav Kotesovec_, Aug 23 2014