OFFSET
0,3
COMMENTS
Also number of permutations in S_n avoiding the patterns 3142 and 2341. Partial sums of A109034.
Hankel transform is 2^floor(n^2/3) (see A134751). - Paul Barry, Dec 15 2008
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..300
Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.
Christian Bean, Émile Nadeau, and Henning Ulfarsson, Enumeration of Permutation Classes and Weighted Labelled Independent Sets, arXiv:1912.07503 [math.CO], 2019.
Darla Kremer and Wai Chee Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.
Ian Le, Wilf classes of pairs of permutations of length 4, Electron. J. Combin., 12(1) (2005), R25, 26 pages.
E. Rowland and R. Yassawi, Automatic congruences for diagonals of rational functions, arXiv preprint arXiv:1310.8635 [math.NT], 2013-2014.
FORMULA
G.f.: (1-sqrt(1-8*x+16*x^2-8*x^3))/(4*x*(1-x)).
From Paul Barry, Dec 15 2008: (Start)
G.f.: (1-x)*c(2*x*(1-x)^2), where c(x) is the g.f. of A000108;
a(n) = sum{k=0..n, (-1)^(n-k)*C(2k+1,n-k)*2^k*A000108(k)}. (End)
G.f.: 1/(1-x/(1-x/(1-2x/(1-x/(1-x/(1-2x/(1-x/(1-x/(1-2x...... (continued fraction). - Paul Barry, Dec 15 2008
a(n) = Sum_{k=0..n} A091866(n,k)*2^(n-k). - Philippe Deléham, Nov 27 2009
Recurrence: (n+1)*a(n) = 3*(3*n-1)*a(n-1) - 12*(2*n-3)*a(n-2) + 12*(2*n-5) * a(n-3) - 4*(2*n-7)*a(n-4). - Vaclav Kotesovec, Oct 24 2012
a(n) ~ sqrt(5-sqrt(5))*(sqrt(5)+3)^n/(2*sqrt(2*Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 24 2012. Equivalently, a(n) ~ 5^(1/4) * 2^(n-1) * phi^(2*n - 1/2) / (sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 10 2021
G.f. A(x) satisfies: A(x) = (1 - x) * (1 + 2*x*A(x)^2). - Ilya Gutkovskiy, Jun 30 2020
EXAMPLE
a(4) = 22 because all permutations of 1234 qualify with the exception of 1342 and 2143.
MAPLE
G:=(1-sqrt(1-8*x+16*x^2-8*x^3))/4/x/(1-x): Gser:=series(G, x=0, 30): 1, seq(coeff(Gser, x^n), n=1..27);
MATHEMATICA
CoefficientList[Series[(1-Sqrt[1-8x+16x^2-8x^3])/(4x(1-x)), {x, 0, 30}], x] (* Harvey P. Dale, Jul 02 2011 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jun 16 2005
STATUS
approved