A134751 -id:A134751 - cp's OEIS frontend

A109033 Number of permutations in S_n avoiding the patterns 1342 and 2143.

1, 1, 2, 6, 22, 88, 368, 1584, 6968, 31192, 141656, 651136, 3023840, 14166496, 66876096, 317809216, 1519163456, 7299577216, 35237444736, 170812433536, 831127053696, 4057858988416, 19873611712896, 97609555091456

Offset: 0

Emeric Deutsch, Jun 16 2005

nonn

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

			a(4) = 22 because all permutations of 1234 qualify with the exception of 1342 and 2143.

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.
Wikipedia, Permutation classes avoiding two patterns of length 4.

Cf. A109034.

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);

CoefficientList[Series[(1-Sqrt[1-8x+16x^2-8x^3])/(4x(1-x)), {x,0,30}], x] (* Harvey P. Dale, Jul 02 2011 *)

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

A059279 G.f. is ((1-x)/(1-2x)) G(x(1-x)/(1-2x)) where G(x) is g.f. for Catalan numbers A000108.

Original entry on oeis.org

1, 2, 6, 20, 72, 276, 1112, 4656, 20080, 88608, 398144, 1815248, 8375904, 39037120, 183493440, 868853120, 4140414720, 19841656960, 95559048960, 462268075520, 2245165391360, 10943794652160, 53519094753280, 262510076263680, 1291131867203072

Offset: 0

N. J. A. Sloane, Jan 24 2001

nonn

Hankel transform is A134751. Binomial transform of A105864. [From Paul Barry, Oct 07 2008]

G. C. Greubel, Table of n, a(n) for n = 0..1000
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 18.

CoefficientList[Series[(1 - Sqrt[1 - 4*t*(1 - t)/(1 - 2*t)])/(2*t), {t, 0, 50}], t] (* G. C. Greubel, Jan 04 2017 *)

Vec((1 - sqrt(1 - 4*t*(1 - t)/(1 - 2*t)))/(2*t) + O(t^50)) \\ G. C. Greubel, Jan 04 2017

Conjecture: (n+1)*a(n) +2*(1-4*n)*a(n-1) + 4*(4*n-5)*a(n-2) +4*(5-2*n)*a(n-3)=0. - R. J. Mathar, Nov 15 2011
G.f.: (1 - sqrt(1 - 4*x*(1 - x)/(1 - 2*x)))/(2*x). - G. C. Greubel, Jan 04 2017
G.f. A(x) satisfies: A(x) = 1 + x * (1/(1 - 2*x) + A(x)^2). - Ilya Gutkovskiy, Jun 30 2020
a(n) ~ 5^(1/4) * 2^(n-1) * phi^(2*n + 3/2) / (sqrt(Pi) * n^(3/2)), where phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Jun 30 2020

A105864 Expansion of (1/(1-x^2))*c(x/(1-x^2)), where c(x) is the g.f. of A000108.

Original entry on oeis.org

1, 1, 3, 7, 21, 65, 215, 735, 2585, 9281, 33883, 125383, 469229, 1772801, 6752623, 25902975, 99978865, 388001025, 1513077235, 5926139207, 23301146501, 91942524481, 363957103303, 1444966207967, 5752187960841, 22955311342145

Offset: 0

Paul Barry, Apr 23 2005

Binomial transform is A059279.
Hankel transform is A134751. - Paul Barry, Oct 07 2008
The radius of convergence r of the g.f. A(x) satisfies: r = (1-r^2)/4 = lim_{n->inf} a(n)/a(n+1) = sqrt(5) - 2 = 0.2360679... with A(r) = 1/(2*r) = (sqrt(5) + 2)/2 = 2.1180339... - Paul D. Hanna, Sep 06 2011

Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.

Partial sums of A128750.

a[0] = a[1] = 1; a[2] = 3; a[3] = 7; a[n_] := a[n] = (-((n-3)*a[n-4]) - 2*(2*n-3)*a[n-3] + 2*(n-1)*a[n-2] + 2*(2*n-1)*a[n-1])/(n+1); Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Sep 09 2017, using "FindSequenceFunction" *)

{a(n)=polcoeff((1-sqrt(1-4*x/(1-x^2 +O(x^(n+2)))))/(2*x), n)} /* Paul D. Hanna */

G.f.: (1 - sqrt((1 - 4*x - x^2)/(1 - x^2)))/(2*x).
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k) * A000108(n-2*k).
G.f. satisfies: A(x) = 1/(1-x^2) + x*A(x)^2. - Paul D. Hanna, Sep 06 2011
Conjecture: (n+1)*a(n) + 2*(1-2*n)*a(n-1) + 2*(1-n)*a(n-2) + 2*(2*n-3)*a(n-3) + (n-3)*a(n-4) = 0. - R. J. Mathar, Nov 15 2011
G.f.: (1-1/G(0))/(2*x), where G(k) = 1 + 4*x*(4*k+1)/( (1-x^2)*(4*k+2) - x*(1-x^2)*(4*k+2)*(4*k+3)/(x*(4*k+3) + (1-x^2)*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 26 2013
a(n) ~ 5^(1/4)*(2+sqrt(5))^(n+1)/(4*sqrt(2*Pi)*n^(3/2)). - Vaclav Kotesovec, Sep 16 2013
G.f.: 1/G(x), where G(x) = 1 - x^2 - (x - x^3)/ G(x) (continued fraction). - Nikolaos Pantelidis, Jan 08 2023

A174016 Row sums of number triangle A174014.

Original entry on oeis.org

1, 2, 6, 16, 40, 92, 192, 352, 528, 512, -192, -2128, -3840, 5888, 69056, 299264, 917760, 2125184, 3258368, -117760, -23297536, -103321600, -295843840, -577744128, -416948224, 2490589184, 14821469184, 50063536128

Offset: 0

Paul Barry, Mar 05 2010

Hankel transform is 1, 2, -8, -32, -256, 4096, ... (signed version of A134751).

G.f.: (sqrt(1-4x+4x^2+8x^3)+4x-1)/(2x(1-2x));
g.f.: 1/(1-2x/(1-x/(1+x/(1-2x/(1-x/(1+x/(1-2x/(1-... (continued fraction).
a(n) = Sum_{k=0..n} A198379(n,k)*2^k. - Philippe Deléham, Oct 29 2011
Conjecture: (n+1)*a(n) - 6*n*a(n-1) + 12*(n-1)*a(n-2) - 12*a(n-3) + 8*(7-2*n)*a(n-4) = 0. - R. J. Mathar, Nov 13 2012

First formula corrected by Philippe Deléham, Feb 16 2012

A186341 a(n)=sum{k=0..floor(n/2), binomial(n-k,k)*A186338(k)}.

Original entry on oeis.org

1, 1, 3, 5, 15, 33, 95, 237, 667, 1765, 4943, 13505, 37967, 105837, 299675, 847253, 2417903, 6909409, 19866303, 57253165, 165728475, 480938693, 1400391247, 4087481409, 11963060527, 35089773869, 103157489499, 303856951925, 896755068783, 2651120922081, 7850714948511

Offset: 0

Paul Barry, Feb 18 2011

Hankel transform is A134751.

CoefficientList[Series[(1-x-3x^2-Sqrt[(1-3x-7x^2+19x^3+15x^4-25x^5-16x^6)/(1-x)])/(2x^2(1-x-2x^2)),{x,0,40}],x]  (* Harvey P. Dale, Mar 04 2011 *)

G.f.: 1/(1-x-2x^2/(1-2x^2/(1-x-x^2/(1-2x^2/(1-x-2x^2/(1-x^2/(1-x-2x^2/(1-... (continued fraction).
G.f.: (1-x-3x^2-sqrt((1-3x-7x^2+19x^3+15x^4-25x^5-16x^6)/(1-x)))/(2x^2(1-x-2x^2)).
Conjecture: (n+2)*a(n) +5*(-n-1)*a(n-1) +2*(-n+3)*a(n-2) +(38*n-59)*a(n-3) +(-22*n+41)*a(n-4) +4*(-22*n+81)*a(n-5) +3*(19*n-79)*a(n-6) +3*(29*n-164)*a(n-7) +2*(-17*n+98)*a(n-8) +16*(-2*n+15)*a(n-9)=0. - R. J. Mathar, Oct 08 2016

cp's OEIS Frontend

A109033 Number of permutations in S_n avoiding the patterns 1342 and 2143.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A059279 G.f. is ((1-x)/(1-2*x)) * G(x*(1-x)/(1-2*x)) where G(x) is g.f. for Catalan numbers A000108.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

PARI

Formula

A105864 Expansion of (1/(1-x^2))*c(x/(1-x^2)), where c(x) is the g.f. of A000108.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A174016 Row sums of number triangle A174014.

Views

Author

Keywords

Comments

Formula

Extensions

A186341 a(n)=sum{k=0..floor(n/2), binomial(n-k,k)*A186338(k)}.

Views

Author

Keywords

Comments

Programs

Mathematica

Formula

A059279 G.f. is ((1-x)/(1-2x)) G(x(1-x)/(1-2x)) where G(x) is g.f. for Catalan numbers A000108.