A106228 -id:A106228 - cp's OEIS frontend

A107708 Number of paths from (0,0) to (3n,0) that stay in the first quadrant (x,y >= 0) and where each step is (3,0), (2,1), (1,2), or (1,-1).

1, 3, 18, 144, 1323, 13176, 138348, 1507977, 16900650, 193536864, 2254630788, 26635735440, 318350663748, 3842488208997, 46770206742342, 573435609537600, 7075551692662875, 87794803094586336, 1094807464312435344

Offset: 0

Emeric Deutsch, Jun 10 2005

nonn

			a(1)=3 because we have H, uD and Udd, where H=(3,0), u=(2,1), U=(1,2) and D=(1,-1).

G. C. Greubel, Table of n, a(n) for n = 0..880
Emeric Deutsch, Problem 10658, American Math. Monthly, 107, 2000, 368-370.
M. Dziemianczuk, Counting Lattice Paths With Four Types of Steps, Graphs and Combinatorics, September 2013, DOI 10.1007/s00373-013-1357-1.

Cf. A027307, A106228, A346626.

a:=n->(1/n)*sum(3^j*binomial(n,j)*binomial(n+j,2*n+1-j),j=ceil((n+1)/2)..n): 1,seq(a(n),n=1..22);

Flatten[{1,Table[1/n*Sum[3^j*Binomial[n, j]*Binomial[n+j, 2n+1-j], {j,Floor[(n+1)/2],n}],{n,1,20}]}] (* Vaclav Kotesovec, Mar 17 2014 *)

concat([1], for(n=1,50, print1((1/n)*sum(j=floor((n+1)/2),n, 3^j*binomial(n,j)*binomial(n+j,2*n+1-j)), ", "))) \\ G. C. Greubel, Mar 16 2017

a(n) = (1/n)*Sum(3^j*binomial(n, j)*binomial(n+j, 2n+1-j), j=ceiling((n+1)/2)..n) for n >= 1; a(0)=1.
G.f. = (2/3)w*sin((1/3)*arcsin((36-7z)/2/(3-2z)/w))-1/3, where w=sqrt((3-2z)/z).
Recurrence: 2*n*(2*n+1)*(17*n-25)*a(n) = 4*(238*n^3 - 588*n^2 + 395*n - 72)*a(n-1) - 12*(n-2)*(34*n^2 - 67*n + 21)*a(n-2) + 3*(n-3)*(n-2)*(17*n - 8)*a(n-3). - Vaclav Kotesovec, Mar 17 2014
a(n) ~ (1/204)*sqrt(102)*sqrt((134963 + 21573*sqrt(17))^(1/3) * ((134963 + 21573*sqrt(17))^(2/3) + 2176 + 68*(134963 + 21573*sqrt(17))^(1/3))) / ((134963 + 21573*sqrt(17))^(1/3)*sqrt(Pi)) * 6^(-n) * ((19009 + 153*sqrt(17))^(2/3) + 712 + 28*(19009 + 153*sqrt(17))^(1/3))^n * (19009 + 153*sqrt(17))^(-n/3)*(1/n)^(3/2). - Vaclav Kotesovec, Mar 17 2014
D-finite with recurrence 8*n*(2*n+1)*a(n) +2*(-106*n^2+97*n-18)*a(n-1) +36*(-2*n^2+12*n-15)*a(n-2) +12*(5*n-14)*(n-3)*a(n-3) -9*(n-3)*(n-4)*a(n-4)=0. - R. J. Mathar, Jul 26 2022
G.f. satisfies A(x) = 1 + x * A(x) * (1 + A(x) + A(x)^2). - Seiichi Manyama, Apr 01 2024

A165542 Number of permutations of length n which avoid the patterns 4231 and 4123.

Original entry on oeis.org

1, 1, 2, 6, 22, 89, 380, 1677, 7566, 34676, 160808, 752608, 3548325, 16830544, 80234659, 384132724, 1845829988, 8897740300, 43010084460, 208409687323, 1012046126532, 4923952560917, 23997719075657, 117136530812812, 572552052378494, 2802078324448067

Offset: 0

Vincent Vatter, Sep 21 2009

nonn

G.f. conjectured to be non-D-finite (see Albert et al link). - Jay Pantone, Oct 01 2015

			There are 22 permutations of length 4 which avoid these two patterns, so a(4)=22.

David Bevan, Jay Pantone, and Nathaniel Shar, Table of n, a(n) for n = 0..1000 (terms 1 through 40 by David Bevan, terms 41 through 70 by Nathaniel Shar)
Michael H. Albert, Cheyne Homberger, Jay Pantone, Nathaniel Shar, Vincent Vatter, Generating Permutations with Restricted Containers, arXiv:1510.00269 [math.CO], 2015.
C. Bean, M. Tannock and H. Ulfarsson, Pattern avoiding permutations and independent sets in graphs, arXiv:1512.08155 [math.CO], 2015.
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.
Wikipedia, Permutation classes avoiding two patterns of length 4.

Cf. A053614, A106228, A165542, A165545, A257561, A257562.

More terms from David Bevan, Feb 04 2014

a(0)=1 prepended by Jay Pantone, Oct 01 2015

A165545 Number of permutations of length n which avoid the patterns 2341 and 3421.

Original entry on oeis.org

1, 1, 2, 6, 22, 89, 382, 1711, 7922, 37663, 182936, 904302, 4535994, 23034564, 118209806, 612165222, 3195359360, 16795435994, 88825567814, 472356139660, 2524292893556, 13549955878141, 73026827854516, 395017112175542, 2143881709415478, 11671226062503926

Offset: 0

Vincent Vatter, Sep 21 2009

nonn

These permutations have an enumeration scheme of depth 4.

G.f. is conjectured to be non-D-finite (see Albert et al link). - Jay Pantone, Oct 01 2015

			There are 22 permutations of length 4 which avoid these two patterns, so a(4)=22.

Jay Pantone, Table of n, a(n) for n = 0..1000
Michael H. Albert, Cheyne Homberger, Jay Pantone, Nathaniel Shar, Vincent Vatter, Generating Permutations with Restricted Containers, arXiv:1510.00269 [math.CO], 2015.
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.
V. Vatter, Enumeration schemes for restricted permutations, Combin., Prob. and Comput. 17 (2008), 137-159.
Wikipedia, Permutation classes avoiding two patterns of length 4.

Cf. A053614, A106228, A165542, A165545, A257561, A257562.

a(0)=1 prepended by Jay Pantone, Oct 01 2015

A257562 Number of permutations of length n that avoid the patterns 4123, 4231, and 4312.

Original entry on oeis.org

1, 1, 2, 6, 21, 79, 310, 1251, 5150, 21517, 90921, 387595, 1663936, 7183750, 31158310, 135661904, 592558096, 2595232344, 11392504426, 50109205789, 220777103354, 974162444028, 4303957562319, 19036842605855, 84285643628790, 373502845338552, 1656428550764640, 7351106011540209, 32643855249507805, 145040974005303590, 644756480385363800

Offset: 0

Jay Pantone, Apr 30 2015

nonn

G.f. conjectured to be non-D-finite (see Albert et al. link). Jay Pantone, Oct 01 2015

Unlike A061552, whose g.f. is also conjectured to be non-D-finite, thousands of terms of the counting sequence are known. - David Callan, Aug 29 2017

			a(4) = 21 because there are 24 permutations of length 4 and 3 of them do not avoid 4123, 4231, and 4312.

Jay Pantone, Table of n, a(n) for n = 0..5000
D. Callan, T. Mansour, Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns, arXiv:1705.00933 [math.CO] (2017).
David Callan, Toufik Mansour, Mark Shattuck, Enumeration of permutations avoiding a triple of 4-letter patterns is almost all done, Pure Mathematics and Applications (2019) Vol. 28, Issue 1, 14-69.
Michael H. Albert, Cheyne Homberger, Jay Pantone, Nathaniel Shar, Vincent Vatter, Generating Permutations with Restricted Containers, arXiv:1510.00269 [math.CO], (2015).

Cf. A053614, A106228, A165542, A165545, A257561, A257562.

A363809 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, and 2-1-3-5-4.

Original entry on oeis.org

1, 1, 2, 6, 22, 89, 378, 1647, 7286, 32574, 146866, 667088, 3050619, 14039075, 64992280, 302546718, 1415691181, 6656285609, 31436228056, 149079962872, 709680131574, 3390269807364, 16248661836019, 78109838535141, 376531187219762, 1819760165454501

Offset: 0

Andrei Asinowski, Jun 23 2023

nonn

Equivalently, for n>0, the number of separable permutations of [n] that avoid 2-1-3-5-4.

The number of guillotine rectangulations (with respect to the weak equivalence) that avoid the geometric pattern "7". See the Merino and Mütze reference, Table 3, entry "12347".

Andrei Asinowski and Cyril Banderier. Geometry meets generating functions: Rectangulations and permutations (2023).

Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
Arturo Merino and Torsten Mütze. Combinatorial generation via permutation languages. III. Rectangulations. Discrete & Computational Geometry, 70 (2023), 51-122. Preprint: arXiv:2103.09333 [math.CO], 2021.

Other entries including the patterns 1, 2, 3, 4 in the Merino and Mütze reference: A006318, A106228, A078482, A033321, A363810, A363811, A363812, A363813, A006012.

The generating function F=F(x) satisfies the equation x^4*(x - 2)^2*F^4 + x*(x - 2)*(4*x^3 - 7*x^2 + 6*x - 1)*F^3 + (2*x^4 - x^3 - 2*x^2 + 5*x - 1)*F^2 - (4*x^3 - 7*x^2 + 6*x - 1)*F + x^2 = 0.

A363810 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-14-3, and 4-5-3-1-2.

Original entry on oeis.org

1, 1, 2, 6, 21, 79, 306, 1196, 4681, 18308, 71564, 279820, 1095533, 4298463, 16913428, 66769536, 264526329, 1051845461, 4197832133, 16813161765, 67571221016, 272448598737, 1101876945673, 4469106749281, 18174503562880, 74093063050412, 302753929958872

Offset: 0

Andrei Asinowski, Jun 23 2023

nonn

Equivalently, for n>0, the number of separable permutations of [n] that avoid 2-14-3 and 2-1-3-5-4.

The number of guillotine rectangulations (with respect to the weak equivalence) that avoid the geometric patterns "5" and "8". See the Merino and Mütze reference, Table 3, entry "123458".

Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
Arturo Merino and Torsten Mütze. Combinatorial generation via permutation languages. III. Rectangulations. Discrete & Computational Geometry, 70 (2023), 51-122. Preprint: arXiv:2103.09333 [math.CO], 2021.

Other entries including the patterns 1, 2, 3, 4 in the Merino and Mütze reference: A006318, A106228, A363809, A078482, A033321, A363811, A363812, A363813, A006012.

with(gfun): seq(coeff(algeqtoseries(x^8*(-2+x)^2*F^4 - x^3*(x-1)*(-2+x)*(x^5-7*x^4+4*x^3-6*x^2+5*x-1)*F^3 - x*(x-1)*(4*x^7-22*x^6+37*x^5-42*x^4+53*x^3-35*x^2+10*x-1)*F^2 - (5*x^6-16*x^5+15*x^4-28*x^3+23*x^2-8*x+1)*(x-1)^2*F - (2*x^5-5*x^4+4*x^3-10*x^2+6*x-1)*(x-1)^2, x, F, 32, true)[1], x, n+1), n = 0..30); # Vaclav Kotesovec, Jun 24 2023

The generating function F=F(x) satisfies the equation x^8*(x - 2)^2*F^4 - x^3*(x - 1)*(x - 2)*(x^5 - 7*x^4 + 4*x^3 - 6*x^2 + 5*x - 1)*F^3 - x*(x - 1)*(4*x^7 - 22*x^6 + 37*x^5 - 42*x^4 + 53*x^3 - 35*x^2 + 10*x - 1)*F^2 - (5*x^6 - 16*x^5 + 15*x^4 - 28*x^3 + 23*x^2 - 8*x + 1)*(x - 1)^2*F - (2*x^5 - 5*x^4 + 4*x^3 - 10*x^2 + 6*x - 1)*(x - 1)^2 = 0.

A363811 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-1-3-5-4, and 4-5-3-1-2.

Original entry on oeis.org

1, 1, 2, 6, 22, 88, 362, 1488, 6034, 24024, 93830, 359824, 1357088, 5043260, 18501562, 67120024, 241169322, 859450004, 3041415520, 10699090888, 37448249502, 130518538696, 453276141238, 1569476495000, 5420784841936, 18683861676756, 64286814548706

Offset: 0

Andrei Asinowski, Jun 23 2023

Equivalently, for n>0, the number of separable permutations of [n] that avoid 2-1-3-5-4 and 4-5-3-1-2.

The number of guillotine rectangulations (with respect to the weak equivalence) that avoid the geometric patterns "7" and "8". See the Merino and Mütze reference, Table 3, entry "123478".

Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
Arturo Merino and Torsten Mütze. Combinatorial generation via permutation languages. III. Rectangulations. Discrete & Computational Geometry, 70 (2023), 51-122. Preprint: arXiv:2103.09333 [math.CO], 2021.
Index entries for linear recurrences with constant coefficients, signature (18,-141,630,-1767,3224,-3834,2896,-1312,320,-32).

Other entries including the patterns 1, 2, 3, 4 in the Merino and Mütze reference: A006318, A106228, A363809, A078482, A033321, A363810, A363812, A363813, A006012.

CoefficientList[Series[(1 - x)*(1 - 16*x + 109*x^2 - 410*x^3 + 923*x^4 - 1256*x^5 + 988*x^6 - 400*x^7 + 66*x^8 - 2*x^9)/((1 - 4*x + 2*x^2)*(1 - 3*x + x^2)^2*(1 - 2*x)^4),{x,0,26}],x] (* Stefano Spezia, Jun 24 2023 *)

G.f.: (1 - x)*(1 - 16*x + 109*x^2 - 410*x^3 + 923*x^4 - 1256*x^5 + 988*x^6 - 400*x^7 + 66*x^8 - 2*x^9)/((1 - 4*x + 2*x^2)*(1 - 3*x + x^2)^2*(1 - 2*x)^4).

A363812 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-1-4-3, and 3-41-2.

Original entry on oeis.org

1, 1, 2, 6, 20, 69, 243, 870, 3159, 11611, 43130, 161691, 611065, 2325739, 8907360, 34304298, 132770564, 516164832, 2014739748, 7892775473, 31022627947, 122304167437, 483513636064, 1916394053725, 7613498804405, 30313164090695

Offset: 0

Andrei Asinowski, Jun 23 2023

Equivalently, for n>0, the number of separable permutations of [n] that avoid 2-1-4-3 and 3-41-2.

The number of guillotine rectangulations (with respect to the weak equivalence) that avoid the geometric patterns "5", "6", "7". See the Merino and Mütze reference, Table 3, entry "1234567".

Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
Arturo Merino and Torsten Mütze. Combinatorial generation via permutation languages. III. Rectangulations. Discrete & Computational Geometry, 70 (2023), 51-122. Preprint: arXiv:2103.09333 [math.CO], 2021.

Other entries including the patterns 1, 2, 3, 4 in the Merino and Mütze reference: A006318, A106228, A363809, A078482, A033321, A363810, A363811, A363813, A006012.

CoefficientList[Series[(1 - 3*x + 3*x^2 - Sqrt[1 - 6*x + 7*x^2 + 2*x^3 + x^4])/(2*x^2*(2 - x)),{x,0,25}],x] (* Stefano Spezia, Jun 24 2023 *)

G.f.: (1 - 3*x + 3*x^2 - sqrt(1 - 6*x + 7*x^2 + 2*x^3 + x^4))/(2*x^2*(2 - x)).

A363813 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-1-4-3, and 4-5-3-1-2.

Original entry on oeis.org

1, 1, 2, 6, 21, 78, 295, 1114, 4166, 15390, 56167, 202738, 724813, 2570276, 9052494, 31702340, 110503497, 383691578, 1328039043, 4584708230, 15793983638, 54315199642, 186526735307, 639831906594, 2192754259993, 7509139583560, 25699765092254, 87913948206096

Offset: 0

Andrei Asinowski, Jun 23 2023

Equivalently, for n>0, the number of separable permutations of [n] that avoid 2-1-4-3 and 4-5-3-1-2.

The number of guillotine rectangulations (with respect to the weak equivalence) that avoid the geometric patterns "5", "7", "8". See the Merino and Mütze reference, Table 3, entry "1234578".

Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
Arturo Merino and Torsten Mütze. Combinatorial generation via permutation languages. III. Rectangulations. Discrete & Computational Geometry, 70 (2023), 51-122. Preprint: arXiv:2103.09333 [math.CO], 2021.
Index entries for linear recurrences with constant coefficients, signature (10,-37,62,-47,16,-2).

Other entries including the patterns 1, 2, 3, 4 in the Merino and Mütze reference: A006318, A106228, A363809, A078482, A033321, A363810, A363811, A363812, A006012.

CoefficientList[Series[(1 - 9*x + 29*x^2 - 39*x^3 + 20*x^4 - 3*x^5)/((1 - 4*x + 2*x^2)*(1 - 3*x + x^2)^2),{x,0,27}],x] (* Stefano Spezia, Jun 24 2023 *)

G.f.: (1 - 9*x + 29*x^2 - 39*x^3 + 20*x^4 - 3*x^5)/((1 - 4*x + 2*x^2)*(1 - 3*x + x^2)^2).

A364735 G.f. satisfies A(x) = 1 + xA(x) / (1 + xA(x)^2).

Original entry on oeis.org

1, 1, 0, -2, -1, 8, 10, -37, -84, 168, 660, -624, -4950, 583, 35464, 23166, -240513, -359008, 1511640, 3898100, -8387664, -36522256, 35444728, 311764768, -25659766, -2466384737, -1793133360, 18077558170, 28951038285, -120750295320, -330486900870

Offset: 0

Seiichi Manyama, Aug 05 2023

sign

Cf. A364736, A364737, A364738.

Cf. A106228.

a(n) = if(n==0, 1, sum(k=0, n-1, (-1)^k*binomial(n, k)*binomial(n+k, n-1-k))/n);

a(n) = (1/n) * Sum_{k=0..n-1} (-1)^k * binomial(n,k) * binomial(n+k,n-1-k) for n > 0.

cp's OEIS Frontend

A107708 Number of paths from (0,0) to (3n,0) that stay in the first quadrant (x,y >= 0) and where each step is (3,0), (2,1), (1,2), or (1,-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A165542 Number of permutations of length n which avoid the patterns 4231 and 4123.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A165545 Number of permutations of length n which avoid the patterns 2341 and 3421.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A257562 Number of permutations of length n that avoid the patterns 4123, 4231, and 4312.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A363809 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, and 2-1-3-5-4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A363810 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-14-3, and 4-5-3-1-2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A363811 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-1-3-5-4, and 4-5-3-1-2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A363812 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-1-4-3, and 3-41-2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A363813 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-1-4-3, and 4-5-3-1-2.

Views

A364735 G.f. satisfies A(x) = 1 + xA(x) / (1 + xA(x)^2).