A230556 -id:A230556 - cp's OEIS frontend

A333105 Number of nonnegative lattice paths from (0,0) to (n,0) where the allowed steps at (x,y) are (1,v) with v in {-1,0,...,max(y,1)}.

1, 1, 2, 4, 9, 21, 51, 128, 331, 880, 2402, 6724, 19285, 56612, 169908, 520723, 1627477, 5180064, 16766824, 55112302, 183710312, 620213500, 2118094664, 7309077920, 25459737905, 89438446602, 316606738516, 1128566016617, 4048230694964, 14604517154115

Offset: 0

Alois P. Heinz, Mar 07 2020

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1673
Wikipedia, Counting lattice paths
Wikipedia, Motzkin number

Cf. A001006, A230556, A333069, A333106, A333107, A333608.

b:= proc(x, y) option remember; `if`(x=0, 1, add(
      b(x-1, y+j), j=-min(1, y)..min(max(1, y), x-y-1)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..29);

b[x_, y_] := b[x, y] = If[x == 0, 1, Sum[b[x - 1, y + j],
     {j, -Min[1, y], Min[Max[1, y], x - y - 1]}]];
a[n_] := b[n, 0];
a /@ Range[0, 29] (* Jean-François Alcover, Mar 30 2021, after Alois P. Heinz *)

a(n) >= A001006(n) with equality only for n <= 6.

a(n) ~ c * 4^n / n^(3/2), where c = 0.0019335749177095597674777855613451543338378695415042866523284... - Vaclav Kotesovec, Oct 24 2021

A230551 Number of involutions avoiding the pattern 2431.

Original entry on oeis.org

1, 2, 4, 10, 24, 62, 154, 396, 992, 2536, 6376, 16238, 40914, 103954, 262298, 665478, 1680726, 4260262, 10766470, 27274444

Offset: 1

Cheyne Homberger, Oct 23 2013

nonn

			Of the 26 involutions of length 26, only 35142 and 52431 contain the pattern 2431, so a(5) = 24.

Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, Pattern-avoiding involutions: exact and asymptotic enumeration, arxiv:1310.7003, 2013.

Cf. A001006, A121704, A230552-A230556.

A230552 Number of involutions avoiding the pattern 2341.

Original entry on oeis.org

1, 2, 4, 10, 25, 66, 170, 441, 1124, 2870, 7273, 18477, 46825, 118917, 301734, 766525, 1946293, 4944614, 12557685

Offset: 1

Cheyne Homberger, Oct 23 2013

nonn

			Of the 26 involutions of length 5, only 52341 contains the pattern 2341, so a(5) = 25.

Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, Pattern-avoiding involutions: exact and asymptotic enumeration, arxiv:1310.7003, 2013.

Cf. A001006, A121704, A230551-A230556.

A230555 Number of involutions avoiding 3421.

Original entry on oeis.org

1, 1, 2, 4, 10, 25, 66, 173, 460, 1218, 3240, 8602, 22878, 60794, 161668, 429752, 1142758, 3038173, 8078606, 21479469, 57113888

Offset: 0

Cheyne Homberger, Oct 23 2013

nonn

			Of the 26 involutions of length 5, only 45312 contains the pattern 3421, so a(5) = 25.

Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, Pattern-avoiding involutions: exact and asymptotic enumeration, arxiv:1310.7003, 2013.

Cf. A000085, A001006, A121704, A230551-A230556.

A230553 Number of involutions avoiding the pattern 1342.

Original entry on oeis.org

1, 1, 2, 4, 10, 24, 62, 156, 406, 1040, 2714, 7012, 18322, 47560, 124358, 323708, 846766, 2208032, 5777330, 15082372, 39469786

Offset: 0

Cheyne Homberger, Oct 23 2013

nonn

			Of the 26 involutions of length 5, only 14523 and 15342 contain the pattern 1342, so a(5) = 24.

Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, Pattern-avoiding involutions: exact and asymptotic enumeration, arxiv:1310.7003, 2013.

Cf. A000085, A001006, A121704, A230551-A230556.

A230554 Number of involutions avoiding the pattern 1324.

Original entry on oeis.org

1, 1, 2, 4, 9, 21, 51, 126, 321, 820, 2160, 5654, 15272, 40758, 112280, 304471, 852164, 2341980, 6640755, 18460066, 52915999

Offset: 0

Cheyne Homberger, Oct 23 2013

nonn

			Of the 26 involutions of length 5, only 21435, 13254, 13245, 14325, and 12435 contain the pattern 1324, so a(5) = 21.

Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, Pattern-avoiding involutions: exact and asymptotic enumeration, arxiv:1310.7003, 2013.

Cf. A000085, A001006, A121704, A230551-A230556.

A230557 The number of 123-avoiding simple involutions of length n.

Original entry on oeis.org

1, 2, 0, 0, 2, 3, 2, 5, 10, 17, 22, 44, 68, 127, 184, 356, 530, 1017, 1502, 2906, 4312, 8351, 12388, 24067, 35748, 69577, 103404, 201642, 299882, 585691, 871498, 1704509, 2537522, 4969153, 7400782, 14508938, 21617096, 42422023, 63226948, 124191257, 185155568, 363985681, 542815792, 1067892398, 1592969006

Offset: 1

Jay Pantone, Nov 05 2013

nonn

An interval in a permutation is a set of contiguous indices such that the set of values of these indices under the permutation is also contiguous. A permutation is simple if it has no proper intervals (those of length more than 1 and less than the whole permutation). - Charles R Greathouse IV, Nov 06 2013

			a(8) = 5 because there are 5 simple involutions of length 8 which avoid the pattern 123: 58371642, 64827153, 68375142, 75382614, and 75842613.

Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vincent Vatter, Pattern-avoiding involutions: exact and asymptotic enumeration, arxiv:1310.7003, 2013.

Cf. A111111, A230551-A230556.

x='x+O('x^66); Vec((-1-2*x+x^6+2*x^3+6*x^5+2*x^7+4*x^5*(-3*x^4-2*x^2+1)^(1/2)+2*x^7*(-3*x^4-2*x^2+1)^(1/2)+x^4*(-3*x^4-2*x^2+1)^(1/2)+2*x^6*(-3*x^4-2*x^2+1)^(1/2)-2*x*(-3*x^4-2*x^2+1)^(1/2)-(-3*x^4-2*x^2+1)^(1/2)+x^2+3*x^4)/(3*x^6+2*x^6*(-3*x^4-2*x^2+1)^(1/2)+5*x^4+3*x^4*(-3*x^4-2*x^2+1)^(1/2)+x^2-1-(-3*x^4-2*x^2+1)^(1/2))) \\ Joerg Arndt, Nov 05 2013

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

a(n) ~ (2*sqrt(3)+3 + (-1)^n*(2*sqrt(3)-3)) * 3^(n/2) / (12 * sqrt(2*Pi*n)). - Vaclav Kotesovec, Jan 27 2015

cp's OEIS Frontend

A333105 Number of nonnegative lattice paths from (0,0) to (n,0) where the allowed steps at (x,y) are (1,v) with v in {-1,0,...,max(y,1)}.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A230551 Number of involutions avoiding the pattern 2431.

Views

Author

Keywords

Examples

Links

Crossrefs

A230552 Number of involutions avoiding the pattern 2341.

Views

Author

Keywords

Examples

Links

Crossrefs

A230555 Number of involutions avoiding 3421.

Views

Author

Keywords

Examples

Links

Crossrefs

A230553 Number of involutions avoiding the pattern 1342.

Views

Author

Keywords

Examples

Links

Crossrefs

A230554 Number of involutions avoiding the pattern 1324.

Views

Author

Keywords

Examples

Links

Crossrefs

A230557 The number of 123-avoiding simple involutions of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula