OFFSET
0,3
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..450
A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011.
Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for dashed patterns, arXiv preprint arXiv:1108.2642 [math.CO], 2011.
Sergey Kitaev, Partially Ordered Generalized Patterns, preprint.
Sergey Kitaev, Partially Ordered Generalized Patterns, Discrete Math. 298 (2005), no. 1-3, 212-229.
FORMULA
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).
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.] -
MAPLE
b:= proc(u, o, t) option remember; `if`(u+o=0, 1, add(
`if`(t=1 and o>j, 0, b(u+j-1, o-j, t+1)), j=1..o)+
add(b(u-j, o+j-1, 0), j=1..u))
end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..25); # Alois P. Heinz, Nov 14 2015
MATHEMATICA
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Sergey Kitaev, May 26 2002
EXTENSIONS
More terms from Vladeta Jovovic, May 28 2002
Link added by Andrew Baxter, May 17 2011
Typos in formula corrected by Vaclav Kotesovec, Aug 23 2014
STATUS
approved