A122951 -id:A122951 - cp's OEIS frontend

A127617 Number of walks from (0,0) to (n,n) in the region 0 <= x-y <= 3 with the steps (1,0), (0, 1), (2,0) and (0,2).

1, 1, 5, 22, 92, 395, 1684, 7189, 30685, 130973, 559038, 2386160, 10184931, 43472696, 185556025, 792015257, 3380586357, 14429474710, 61589830404, 262886022219, 1122085581740, 4789437042413, 20442921249973, 87257234103245, 372443097062686, 1589711867161816

Offset: 0

Arvind Ayyer, Jan 20 2007

			a(2)=5 because we can reach (2,2) in the following ways:
(0,0),(1,0),(1,1),(2,1),(2,2)
(0,0),(2,0),(2,2)
(0,0),(1,0),(2,0),(2,2)
(0,0),(2,0),(2,1),(2,2)
(0,0),(1,0),(2,0),(2,1),(2,2)

Muniru A Asiru, Table of n, a(n) for n = 0..1550
Arvind Ayyer and Doron Zeilberger, The Number of [Old-Time] Basketball games with Final Score n:n where the Home Team was never losing but also never ahead by more than w Points, arXiv:math/0610734 [math.CO], 2006-2007.
Index entries for linear recurrences with constant coefficients, signature (3,5,2,-1).

Cf. A000108, A046717, A122951, A127618, A127619, A127620.

I:=[1,1,5,22]; [n le 4 select I[n] else 3*Self(n-1)+5*Self(n-2)+2*Self(n-3)-Self(n-4): n in [1..30]]; // Vincenzo Librandi, Dec 13 2018

seq(coeff(series((1-2*x-3*x^2)/(1-3*x-5*x^2-2*x^3+x^4),x,n+1), x, n), n = 0 .. 25); # Muniru A Asiru, Dec 10 2018

LinearRecurrence[{3, 5, 2, -1}, {1, 1, 5, 22}, 23] (* Jean-François Alcover, Dec 10 2018 *)
CoefficientList[Series[(1 - 2 x - 3 x^2) / (1 - 3 x - 5 x^2 - 2 x^3 + x^4), {x, 0, 33}], x] (* Vincenzo Librandi, Dec 13 2018 *)
b[n_, k_] := Boole[n >= 0 && k >= 0 && 0 <= n-k <= 3];
T[0, 0] = T[1, 1] = 1; T[n_, k_] /; b[n, k] == 1 := T[n, k] = b[n-2, k]* T[n-2, k] + b[n-1, k]*T[n-1, k] + b[n, k-2]*T[n, k-2] + b[n, k-1]*T[n, k-1]; T[, ] = 0;
a[n_] := T[n, n];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Apr 03 2019 *)

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

a(n) = 3*a(n-1)+5*a(n-2)+2*a(n-3)-a(n-4). - Vincenzo Librandi, Dec 13 2018

A127618 Number of walks from (0,0) to (n,n) in the region 0 <= x-y <= 4 with the steps (1,0), (0, 1), (2,0) and (0,2).

Original entry on oeis.org

1, 1, 5, 22, 117, 590, 3018, 15378, 78440, 399992, 2039852, 10402480, 53049048, 270531368, 1379614800, 7035549312, 35878823312, 182969359520, 933079279328, 4758375627808, 24266039468160, 123748253080832, 631072497876672

Offset: 0

Arvind Ayyer, Jan 20 2007

			a(2)=5 because we can reach (2,2) in the following ways:
(0,0),(1,0),(1,1),(2,1),(2,2)
(0,0),(2,0),(2,2)
(0,0),(1,0),(2,0),(2,2)
(0,0),(2,0),(2,1),(2,2)
(0,0),(1,0),(2,0),(2,1),(2,2)

Arvind Ayyer and Doron Zeilberger, The Number of [Old-Time] Basketball games with Final Score n:n where the Home Team was never losing but also never ahead by more than w Points, arXiv:math/0610734 [math.CO], 2006-2007.
Index entries for linear recurrences with constant coefficients, signature (4,6,-2).

Cf. A000108, A046717, A122951, A127617, A127619, A127620.

Join[{1, 1}, LinearRecurrence[{4, 6, -2}, {5, 22, 117}, 21]] (* Jean-François Alcover, Dec 10 2018 *)
b[n_, k_] := Boole[n >= 0 && k >= 0 && 0 <= n-k <= 4];
T[0, 0] = T[1, 1] = 1; T[n_, k_] /; b[n, k] == 1 := T[n, k] = b[n-2, k]* T[n-2, k] + b[n-1, k]*T[n-1, k] + b[n, k-2]*T[n, k-2] + b[n, k-1]*T[n, k-1]; T[, ] = 0;
a[n_] := T[n, n];
Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Apr 03 2019 *)

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

A127619 Number of walks from (0,0) to (n,n) in the region 0 <= x-y <= 5 with the steps (1,0), (0, 1), (2,0) and (0,2).

Original entry on oeis.org

1, 1, 5, 22, 117, 654, 3674, 20763, 117349, 663529, 3751874, 21215245, 119963514, 678345474, 3835772387, 21689760681, 122646936325, 693519457822, 3921575652821, 22174944672838, 125390459051898, 709032985366923

Offset: 0

Arvind Ayyer, Jan 20 2007

			a(2)=5 because we can reach (2,2) in the following ways:
(0,0),(1,0),(1,1),(2,1),(2,2)
(0,0),(2,0),(2,2)
(0,0),(1,0),(2,0),(2,2)
(0,0),(2,0),(2,1),(2,2)
(0,0),(1,0),(2,0),(2,1),(2,2)

Arvind Ayyer and Doron Zeilberger, The Number of [Old-Time] Basketball games with Final Score n:n where the Home Team was never losing but also never ahead by more than w Points, arXiv:math/0610734 [math.CO], 2006-2007.
Index entries for linear recurrences with constant coefficients, signature (5, 6, -11, -12, 4).

Cf. A000108, A046717, A122951, A127617, A127618, A127620.

LinearRecurrence[{5, 6, -11, -12, 4}, {1, 1, 5, 22, 117}, 22] (* Jean-François Alcover, Dec 10 2018 *)
b[n_, k_] := Boole[n >= 0 && k >= 0 && 0 <= n - k <= 5];
T[0, 0] = T[1, 1] = 1; T[n_, k_] /; b[n, k] == 1 := T[n, k] = b[n-2, k]* T[n-2, k] + b[n-1, k]*T[n-1, k] + b[n, k-2]*T[n, k-2] + b[n, k-1]*T[n, k-1]; T[, ] = 0;
a[n_] := T[n, n];
Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Apr 03 2019 *)

G.f.: (1-4x-6x^2+2x^3)/(1-5x-6x^2+11x^3+12x^4-4x^5). [Typo corrected by Jean-François Alcover, Dec 10 2018]

A127620 Number of walks from (0,0) to (n,n) in the region 0 <= x-y <= 6 with the steps (1,0), (0, 1), (2,0) and (0,2).

Original entry on oeis.org

1, 1, 5, 22, 117, 654, 3843, 22882, 137443, 827998, 4995443, 30155494, 182083275, 1099560942, 6640309323, 40101959542, 242184540139, 1462610652718, 8833070227499, 53345145429670, 322164911643723, 1945636121710110

Offset: 0

Arvind Ayyer, Jan 20 2007

			a(2)=5 because we can reach (2,2) in the following ways:
(0,0),(1,0),(1,1),(2,1),(2,2)
(0,0),(2,0),(2,2)
(0,0),(1,0),(2,0),(2,2)
(0,0),(2,0),(2,1),(2,2)
(0,0),(1,0),(2,0),(2,1),(2,2)

Arvind Ayyer and Doron Zeilberger, The Number of [Old-Time] Basketball games with Final Score n:n where the Home Team was never losing but also never ahead by more than w Points, arXiv:math/0610734 [math.CO], 2006-2007.
Index entries for linear recurrences with constant coefficients, signature (6, 5, -24, -28, -6, 8).

Cf. A000108, A046717, A122951, A127617, A127618, A127619.

b[n_, k_] := Boole[n >= 0 && k >= 0 && 0 <= n-k <= 6];
T[0, 0] = T[1, 1] = 1; T[n_, k_] /; b[n, k] == 1 := T[n, k] = b[n-1, k]* T[n-1, k] + b[n-2, k]*T[n-2, k] + b[n, k-1]*T[n, k-1] + b[n, k-2]*T[n, k-2]; T[, ] = 0;
a[n_] := T[n, n];
Table[a[n], {n, 0, 21}]
(* or: *)
LinearRecurrence[{6, 5, -24, -28, -6, 8}, {1, 1, 5, 22, 117, 654}, 22] (* Jean-François Alcover, Apr 02 2019 *)

G.f.: (1 - 5x - 6x^2 + 11x^3 + 12x^4 - 4x^5)/(1 - 6x - 5x^2 + 24x^3 + 28x^4 + 6x^5 - 8x^6). [corrected by Jean-François Alcover, Apr 02 2019]

A122941 Rectangular table, read by antidiagonals, where the g.f. of row n is Sum_{i>=0} F_i(x)^n / 2^(i+1), where F_0(x)=x, F_{n+1}(x) = F_n(x+x^2), for n>=1.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 7, 7, 1, 4, 15, 34, 34, 1, 5, 26, 94, 214, 214, 1, 6, 40, 200, 726, 1652, 1652, 1, 7, 57, 365, 1831, 6645, 15121, 15121, 1, 8, 77, 602, 3865, 19388, 70361, 160110, 160110, 1, 9, 100, 924, 7239, 46481, 233154, 846144, 1925442, 1925442, 1

Offset: 1

Paul D. Hanna, Sep 25 2006

A122940(n)/n = Sum_{m=1..n} (-1)^(m-1)*T(m,n-m+1)/m ; where l.g.f. of A122940, L(x), satisfies: L(x+x^2) = 2*L(x) - log(1+x).

			Table begins:
1, 1, 2, 7, 34, 214, 1652, 15121, 160110, 1925442, 25924260, ...;
1, 2, 7, 34, 214, 1652, 15121, 160110, 1925442, 25924260, ...;
1, 3, 15, 94, 726, 6645, 70361, 846144, 11392530, 169785124, ...;
1, 4, 26, 200, 1831, 19388, 233154, 3139200, 46784118, ...;
1, 5, 40, 365, 3865, 46481, 625820, 9326720, 152426170, ...;
1, 6, 57, 602, 7239, 97470, 1452610, 23739936, 422171622, ...;
1, 7, 77, 924, 12439, 185388, 3029782, 53879148, 1035760670, ...;
1, 8, 100, 1344, 20026, 327296, 5820360, 111889248, 2312153223, ...;
1, 9, 126, 1875, 30636, 544824, 10473576, 216432783, 4784414985, ...;
1, 10, 155, 2530, 44980, 864712, 17868995, 395007850, 9301284465, ...;
Given that A122940 begins:
[1, 1, 4, 17, 106, 796, 7176, 75057, 894100, 11946906, ...],
demonstrate A122940(n)/n = Sum_{m=1..n} (-1)^(m-1)*T(m,n-m+1)/m
at n=4: A122940(4)/4 = 17/4 = 7/1 - 7/2 + 3/3 - 1/4;
at n=5: A122940(5)/5 = 106/5 = 34/1 - 34/2 + 15/3 - 4/4 + 1/5;
at n=6: A122940(6)/6 = 796/6 = 214/1 - 214/2 + 94/3 - 26/4 + 5/5 - 1/6.

Cf. A122940; rows: A122942, A122943, A122944, A122945; related tables: A122888, A122946, A122948, A122951.

/* Get T(n,k) from H(n,), the n-th self-composition of x+x^2: */
{H(n,p)=local(F=x+x^2, G=x+x*O(x^p));if(n==0,G=x,for(i=1,n,G=subst(F,x,G));G)}
{T(n,k)=round(polcoeff( sum(i=0,6*n+100,H(i,k+n-1)^n/2^(i+1)),k+n-1))}

T(n,k) = [x^k] Sum_{i>=0} F_i(x)^n / 2^(i+1) where F_0(x)=x, F_{n+1}(x) = F_n(x+x^2); a sum involving n-th powers of self-compositions of x+x^2 (cf. A122888).

A175883 Number of lattice paths from (0,0) to (n,n) using steps S={(k,0),(0,k)|0

Original entry on oeis.org

1, 1, 5, 29, 170, 1093, 7346, 50957, 362476, 2629150, 19371533, 144585146, 1090886362, 8306621114, 63752890716, 492671044866, 3830272606911, 29937476853483, 235104315621495, 1854181694878573, 14679397763545597, 116619744085592959, 929412502842262520

Offset: 0

Eric Werley, Dec 05 2010

nonn

			a(3)=29 because we can reach (3,3) in the following ways:
by getting to (3,2) in 17 ways and then taking step (0,1), or
by getting to (3,1) in 8 ways and then taking step (0,2), or
by getting to (3,0) in 4 ways and then taking step (0,3).

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A000108, A122951.

b:= proc(x, y) option remember; `if`(y>x or y<0, 0,
      `if`(x=0, 1, add(b(x-j, y)+b(x, y-j), j=1..3)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..35);  # Alois P. Heinz, May 16 2017

b[x_, y_] := b[x, y] = If[y > x || y < 0, 0, If[x == 0, 1, Sum[b[x - j, y] + b[x, y - j], {j, 1, 3}]]];
a[n_] := b[n, n];
a /@ Range[0, 35] (* Jean-François Alcover, Nov 11 2020, after Alois P. Heinz *)

A175891 Number of lattice paths from (0,0) to (n,n) using steps S={(k,0),(0,k)|0

Original entry on oeis.org

1, 1, 5, 29, 185, 1226, 8553, 61642, 455337, 3429002, 26229691, 203237747, 1591820564, 12582288455, 100241042348, 804090987555, 6488942266564, 52644171729304, 429123506792664, 3512829202462126, 28866426741057006, 238031465396515626, 1969001793889730276

Offset: 0

Eric Werley, Dec 05 2010

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A000103, A122951, A175883, A286918.

b:= proc(x, y) option remember; `if`(y>x or y<0, 0,
      `if`(x=0, 1, add(b(x-j, y)+b(x, y-j), j=1..4)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..35);  # Alois P. Heinz, May 16 2017

b[x_, y_] := b[x, y] = If[y > x || y < 0, 0, If[x == 0, 1, Sum[b[x - j, y] + b[x, y - j], {j, 1, 4}]]];
a[n_] := b[n, n];
a /@ Range[0, 35] (* Jean-François Alcover, Nov 11 2020, after Alois P. Heinz *)

a(n) ~ c * d^n / n^(3/2), where d = 8.84734830841870961487278801886633962039798... is the real root of the equation 4 + 4*d - 8*d^2 - 8*d^3 + d^4 = 0 and c = 0.31736815701423989167651891084531024477617724724822148387263881713... - Vaclav Kotesovec, May 30 2017

cp's OEIS Frontend

A127617 Number of walks from (0,0) to (n,n) in the region 0 <= x-y <= 3 with the steps (1,0), (0, 1), (2,0) and (0,2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A127618 Number of walks from (0,0) to (n,n) in the region 0 <= x-y <= 4 with the steps (1,0), (0, 1), (2,0) and (0,2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A127619 Number of walks from (0,0) to (n,n) in the region 0 <= x-y <= 5 with the steps (1,0), (0, 1), (2,0) and (0,2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A127620 Number of walks from (0,0) to (n,n) in the region 0 <= x-y <= 6 with the steps (1,0), (0, 1), (2,0) and (0,2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A122941 Rectangular table, read by antidiagonals, where the g.f. of row n is Sum_{i>=0} F_i(x)^n / 2^(i+1), where F_0(x)=x, F_{n+1}(x) = F_n(x+x^2), for n>=1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A175883 Number of lattice paths from (0,0) to (n,n) using steps S={(k,0),(0,k)|0

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A175891 Number of lattice paths from (0,0) to (n,n) using steps S={(k,0),(0,k)|0

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula