|
%I #40 Oct 27 2023 21:37:14
%S 1,1,2,6,22,100,540,3388,24248,195048,1742860,17127880,183617280,
%T 2132433940,26669752928,357375269160,5108084756320,77574769941760,
%U 1247401873186560,21172559509803520,378282904982091200,7096584257305845120,139471475802695196160
%N Permutations avoiding the consecutive patterns 4312 and 4213.
%C a(n) gives the number of permutations of [n] which avoid both the pattern 4312 and 4213 consecutively. Also the number avoiding the pairs {2134, 3124}, {1243, 1342}, or {3421, 2431} (by symmetry).
%C This can also be considered avoiding a partially ordered pattern: Suppose p<s, r<s, o<p and o<r. To avoid spor means not to have four consecutive letters such that the first letter is larger than the second and the last one, the third letter is less than the second and the last one.
%C The Baxter-Nakamura-Zeilberger paper has an associated Maple package. See Links.
%H Alois P. Heinz, <a href="/A177478/b177478.txt">Table of n, a(n) for n = 0..120</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>
%H S. Kitaev, <a href="https://doi.org/10.1016/j.dam.2006.09.011">Introduction to partially ordered patterns</a>, Discrete Applied Mathematics 155 (2007), 929-944.
%F a(n) ~ c * d^n * n!, where d = 0.89333294588184091624317413051..., c = 1.4839698712287023868073431417... . - _Vaclav Kotesovec_, Aug 24 2014
%p b:= proc(u, o, s, t) option remember; `if`(u+o=0, 1,
%p add(b(u-j, o+j-1, t, j), j=1..u)+
%p add(b(u+j-1, o-j, 0, 0), j=`if`(s>0, s+t-1, 1)..o))
%p end:
%p a:= n-> b(0, n, 0, 0):
%p seq(a(n), n=0..25); # _Alois P. Heinz_, Oct 25 2013
%t b[u_, o_, s_, t_] := b[u, o, s, t] = If[u+o == 0, 1, Sum[b[u-j, o+j-1, t, j], {j, 1, u}] + Sum[b[u+j-1, o-j, 0, 0], {j, If[s > 0, s+t-1, 1], o}]];
%t a[n_] := b[0, n, 0, 0];
%t a /@ Range[0, 25] (* _Jean-François Alcover_, Nov 03 2020, after _Alois P. Heinz_ *)
%Y Cf. A117226, A117156.
%K nonn
%O 0,3
%A Signy Olafsdottir (signy06(AT)ru.is), May 09 2010
%E More terms, succinct title, additional comments, new references from _Andrew Baxter_, Jan 21 2011
|
