A071076 - OEIS

%I #43 Mar 24 2024 03:17:16

%S 1,1,2,6,23,108,598,3815,27532,221708,1970251,19150132,202064380,

%T 2300071071,28092017668,366425723926,5083645400819,74745472084176,

%U 1160974832572274,18995175706664735,326531476287842760,5883736110875887560,110893188848753125475

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

%H Alois P. Heinz, <a href="/A071076/b071076.txt">Table of n, a(n) for n = 0..450</a>

%H 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 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 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 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 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 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 b:= proc(u, o, t) option remember; `if`(u+o=0, 1, add(

%p       `if`(t=1 and o>j, 0, b(u+j-1, o-j, t+1)), j=1..o)+

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

%p     end:

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

%p seq(a(n), n=0..25);  # _Alois P. Heinz_, Nov 14 2015

%t 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 Cf. A049774, A071088, A071075, A071077.

%K nonn

%O 0,3

%A _Sergey Kitaev_, May 26 2002

%E More terms from _Vladeta Jovovic_, May 28 2002

%E Link added by _Andrew Baxter_, May 17 2011

%E Typos in formula corrected by _Vaclav Kotesovec_, Aug 23 2014