A284414 -id:A284414 - cp's OEIS frontend

A284778 Number of self-avoiding planar walks of length n+1 starting at (0,0), ending at (n,0), remaining in the first quadrant and using steps (0,1), (1,0), (1,1), (-1,1), and (1,-1) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal.

0, 1, 1, 4, 8, 22, 54, 142, 370, 983, 2627, 7086, 19238, 52561, 144377, 398518, 1104794, 3074809, 8588093, 24064642, 67630898, 190584766, 538412426, 1524554956, 4326119748, 12300296227, 35037658099, 99977847308, 285741659312, 817901027070, 2344475178110

Offset: 0

Alois P. Heinz, Apr 02 2017

From Gus Wiseman, Nov 15 2022: (Start)
Conjecture: Also the number of topologically series-reduced ordered rooted trees with n + 3 vertices and more than one branch of the root. This would imply a(n) = A187306(n+1) - A005043(n+1). For example, the a(1) = 1 through a(5) = 22 trees are:
  (ooo)  (oooo)  (ooooo)   (oooooo)   (ooooooo)
                 ((oo)oo)  ((oo)ooo)  ((oo)oooo)
                 (o(oo)o)  ((ooo)oo)  ((ooo)ooo)
                 (oo(oo))  (o(oo)oo)  ((oooo)oo)
                           (o(ooo)o)  (o(oo)ooo)
                           (oo(oo)o)  (o(ooo)oo)
                           (oo(ooo))  (o(oooo)o)
                           (ooo(oo))  (oo(oo)oo)
                                      (oo(ooo)o)
                                      (oo(oooo))
                                      (ooo(oo)o)
                                      (ooo(ooo))
                                      (oooo(oo))
                                      (((oo)o)oo)
                                      ((o(oo))oo)
                                      ((oo)(oo)o)
                                      ((oo)o(oo))
                                      (o((oo)o)o)
                                      (o(o(oo))o)
                                      (o(oo)(oo))
                                      (oo((oo)o))
                                      (oo(o(oo)))
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..2105
Alois P. Heinz, Animation of a(6)=54 walks

First upper diagonal of A284414, A284652.

CF. A005043, A187306.

a:= proc(n) option remember; `if`(n<3, (3-n)*n/2,
      ((n^2-n+3)*a(n-1)+(5*n-2)*n*a(n-2)+
       3*(n-1)*n*a(n-3))/((n+3)*(n-1)))
    end:
seq(a(n), n=0..35);

CoefficientList[Series[(1 - 2*x - x^2 - Sqrt[1 - 4*x + 2*x^2 + 4*x^3 - 3*x^4])/(2*(x + 1)*x^3), {x, 0, 50}], x] (* Indranil Ghosh, Apr 02 2017 *)

a(n):=if n=0 then 0 else sum(((k+1)^2*sum(binomial(i,n-1-2*k-i)*binomial(n-k,i),i,0,n-1-2*k))/(n-k),k,0,floor((n)/2)); /* Vladimir Kruchinin, Mar 20 2023 */

G.f.: (1-2*x-x^2-sqrt(1-4*x+2*x^2+4*x^3-3*x^4))/(2*(x+1)*x^3).
Recursion: see Maple program.
a(n) = A284414(n,n+1) = A284652(n,n+1).
a(n) ~ 3^(n+5/2) / (4*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Apr 02 2017
a(n) = Sum_{k=0..floor(n/2)} (k+1)^2/(n-k)*Sum_{i=0..n-1-2*k} C(i,n-1-2*k-i)*C(n-k,i), n>0, a(0)=0. - Vladimir Kruchinin, Mar 20 2023

A284230 Number of self-avoiding planar walks starting at (0,0), ending at (n,0), remaining in the first quadrant and using steps (0,1), (1,0), (1,1), (-1,1), and (1,-1) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal.

Original entry on oeis.org

1, 2, 5, 24, 111, 762, 5127, 45588, 400593, 4370634, 47311677, 611446464, 7857786015, 117346361778, 1745000283087, 29562853594284, 499180661754849, 9458257569095826, 178734707493557301, 3744942786114870888, 78294815164675006479, 1797384789345147560298

Offset: 0

Alois P. Heinz, Mar 23 2017

			a(0) = 1: [(0,0)].
a(1) = 2: [(0,0),(1,0)], [(0,0),(0,1),(1,0)].
a(2) = 5: [(0,0),(1,0),(2,0)], [(0,0),(0,1),(1,0),(2,0)], [(0,0),(1,1),(2,0)], [(0,0),(0,1),(0,2),(1,1),(2,0)], [(0,0),(1,0),(0,1),(0,2),(1,1),(2,0)].

Alois P. Heinz, Table of n, a(n) for n = 0..448
Alois P. Heinz, Animation of a(4)=111 walks
Wikipedia, Lattice path
Wikipedia, Self-avoiding walk

Row sums of A284414.
Bisection (even part) gives A284461.
Cf. A001900, A277358, A284231, A285673.

a:= proc(n) option remember; `if`(n<2, n+1,
      (n+irem(n, 2))*a(n-1)+(n-1)*a(n-2))
    end:
seq(a(n), n=0..25);

a[n_]:=If[n<2, n + 1, (n + Mod[n,2]) * a[n - 1] + (n - 1) a[n - 2]]; Table[a[n], {n, 0, 25}] (* Indranil Ghosh, Mar 27 2017 *)

a(n) ~ c * n^(n+2) / exp(n), where c = 0.7741273379869056907732932906458364317717498069987762339667734187318... - Vaclav Kotesovec, Mar 27 2017

Conjecture: a(n) -a(n-1) +(-n^2-n+3)*a(n-2) +(-n+2)*a(n-3) +(n-2)*(n-3)*a(n-4)=0. - R. J. Mathar, Apr 09 2017

A284231 Total number of nodes summed over all self-avoiding planar walks starting at (0,0), ending at (n,0), remaining in the first quadrant and using steps (0,1), (1,0), (1,1), (-1,1), and (1,-1) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal.

Original entry on oeis.org

1, 5, 21, 152, 975, 8835, 75499, 830180, 8819417, 114384573, 1450018173, 21689509992, 319180726887, 5411092531323, 90615453774771, 1717272516535812, 32234085990345105, 675335923050095253, 14040521125141683717, 322252846702242056280, 7349647183279936080543

Offset: 0

Alois P. Heinz, Mar 23 2017

			a(0) = 1: [(0,0)].
a(1) = 5: [(0,0),(1,0)], [(0,0),(0,1),(1,0)].
a(2) = 21: [(0,0),(1,0),(2,0)], [(0,0),(0,1),(1,0),(2,0)], [(0,0),(1,1),(2,0)], [(0,0),(0,1),(0,2),(1,1),(2,0)], [(0,0),(1,0),(0,1),(0,2),(1,1),(2,0)].

Alois P. Heinz, Table of n, a(n) for n = 0..446
Wikipedia, Lattice path
Wikipedia, Self-avoiding walk

Cf. A277424, A284230, A284414, A285673.

a(n) = Sum_{k=n..n*(n+3)/2} (k+1) * A284414(n,k).

A284461 Number of self-avoiding planar walks starting at (0,0), ending at (n,n), remaining in the first quadrant and using steps (0,1), (1,0), (1,1), (-1,1), and (1,-1) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal.

Original entry on oeis.org

1, 5, 111, 5127, 400593, 47311677, 7857786015, 1745000283087, 499180661754849, 178734707493557301, 78294815164675006479, 41186656484051421462615, 25619826402721039367943729, 18600984174200732870460447213, 15588291843672510150758754601407

Offset: 0

Alois P. Heinz, Mar 27 2017

Alois P. Heinz, Table of n, a(n) for n = 0..224
Alois P. Heinz, Animation of a(2)=111 walks
Wikipedia, Lattice path
Wikipedia, Self-avoiding walk

Bisection of A284230 (even part).

Cf. A284414, A285673.

b:= proc(n) option remember; `if`(n<2, n+1,
      (n+irem(n, 2))*b(n-1)+(n-1)*b(n-2))
    end:
a:= n-> b(2*n):
seq(a(n), n=0..15);
# second Maple program:
a:= proc(n) option remember; `if`(n<2, 4*n+1,
      ((2*n+1)^2-2)*a(n-1)-(4*n-6)*n*a(n-2))
    end:
seq(a(n), n=0..15);

a[n_] := a[n] = If[n<2, 4n+1, ((2n+1)^2-2) a[n-1] - (4n-6) n a[n-2]];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Jun 19 2017, after 2nd Maple program *)

a(n) = A284230(2n).

a(n) = Sum_{k=2n..n*(2n+3)} A284414(2n,k).

A284415 Number of self-avoiding planar walks of length n starting at (0,0), ending on the x-axis, remaining in the first quadrant and using steps (0,1), (1,0), (1,1), (-1,1), and (1,-1) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal.

Original entry on oeis.org

1, 1, 3, 5, 14, 34, 96, 259, 748, 2142, 6329, 18727, 56358, 170370, 520354, 1596980, 4935307, 15319460, 47794472, 149681904, 470620062, 1484513696, 4697619876, 14906459690, 47426014833, 151247657528, 483426998881, 1548323383749, 4968516324954, 15972198595374

Offset: 0

Alois P. Heinz, Mar 26 2017

Alois P. Heinz, Table of n, a(n) for n = 0..516
Alois P. Heinz, Animation of a(6)=96 walks
Wikipedia, Lattice path
Wikipedia, Self-avoiding walk

Column sums of A284414.

Cf. A001006, A003056.

a(n) = Sum_{j=floor((sqrt(1+8*n)-1)/2)..n} A284414(j,n).

A284416 Number of self-avoiding planar walks of length 2n starting at (0,0), ending at (n,0), remaining in the first quadrant and using steps (0,1), (1,0), (1,1), (-1,1), and (1,-1) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal.

Original entry on oeis.org

1, 1, 1, 7, 17, 116, 536, 3732, 21609, 152225, 991680, 7142207, 49671146, 364955208, 2644449147, 19764753353, 147264417970, 1116423286310, 8488332597668, 65109780090520, 502742629038600, 3893865922507871, 30436537169536769, 237651376621912220

Offset: 0

Alois P. Heinz, Mar 26 2017

Alois P. Heinz, Table of n, a(n) for n = 0..360
Alois P. Heinz, Animation of a(5)=116 walks
Wikipedia, Lattice path
Wikipedia, Self-avoiding walk

Cf. A284414.

a(n) = A284414(n,2n).

A284418 Number of self-avoiding planar walks of length n*(n+1)/2 starting at (0,0), ending at (n,0), remaining in the first quadrant and using steps (0,1), (1,0), (1,1), (-1,1), and (1,-1) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal.

Original entry on oeis.org

1, 1, 1, 7, 10, 31, 69, 196, 451, 1168, 2813, 7119, 17618, 44206, 111399, 277972, 709411, 1763795, 4543873, 11269489, 29244239, 72402587, 188977618, 467258134, 1225383748, 3026799348, 7969173506, 19669004793, 51959167749, 128161003199, 339530403506

Offset: 0

Alois P. Heinz, Mar 26 2017

Alois P. Heinz, Animation of a(6)=69 walks
Wikipedia, Lattice path
Wikipedia, Self-avoiding walk

Cf. A000217, A284414.

a(n) = A284414(n,n*(n+1)/2).

A284428 Number of all self-avoiding planar walks of length j (0<=j<=n) starting at (0,0), ending at (n-j,0), remaining in the first quadrant and using steps (0,1), (1,0), (1,1), (-1,1), and (1,-1) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 5, 5, 13, 15, 40, 44, 123, 156, 402, 536, 1361, 1857, 4689, 6681, 16536, 24286, 59400, 89131, 216114, 331324, 796029, 1243168, 2963859, 4700410, 11133792, 17901901, 42155014, 68618679, 160736012, 264497624, 616693942, 1024713750, 2379184108

Offset: 0

Alois P. Heinz, Mar 26 2017

Alois P. Heinz, Table of n, a(n) for n = 0..675
Alois P. Heinz, Animation of a(12)=123 walks
Wikipedia, Lattice path
Wikipedia, Self-avoiding walk

Antidiagonal sums of A284414.

A284652 Number T(n,k) of self-avoiding planar walks of length k starting at (0,0), ending at (n,0), remaining in the first quadrant and using steps (0,1), (1,0), (1,1), (-1,1), and (1,-1) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal; triangle T(n,k), k>=0, floor((sqrt(1+8*k)-1)/2)<=n<=k, read by columns.

Original entry on oeis.org

1, 1, 1, 2, 1, 4, 1, 4, 9, 1, 4, 8, 21, 7, 16, 22, 51, 3, 21, 54, 54, 127, 1, 17, 87, 178, 142, 323, 1, 15, 87, 269, 565, 370, 835, 10, 116, 370, 896, 1766, 983, 2188, 9, 99, 499, 1473, 2776, 5446, 2627, 5798, 4, 91, 536, 2290, 5528, 8657, 16655, 7086, 15511

Offset: 0

Alois P. Heinz, Mar 31 2017

			Triangle T(n,k) begins:
1;
.  1, 1;
.  .  2, 1, 1,  1;
.  .  .  4, 4,  4,  7,   3,   1,   1;
.  .  .  .  9,  8, 16,  21,  17,  15,   10,    9, ... ;
.  .  .  .  .  21, 22,  54,  87,  87,  116,   99, ... ;
.  .  .  .  .   .  51,  54, 178, 269,  370,  499, ... ;
.  .  .  .  .   .   .  127, 142, 565,  896, 1473, ... ;
.  .  .  .  .   .   .    .  323, 370, 1766, 2776, ... ;
.  .  .  .  .   .   .    .    .  835,  983, 5446, ... ;
.  .  .  .  .   .   .    .    .     . 2188, 2627, ... ;

Alois P. Heinz, Columns k = 0..160, flattened
Wikipedia, Lattice path
Wikipedia, Self-avoiding walk

Row sums give A284230.
Column sums give A284415.
Antidiagonal sums give A284428.
T(n,n) gives A001006.
T(n,n+1) gives A284778.
T(n,2n) gives A284416.
T(n,n*(n+1)/2) gives A284418.
Column heights give A122797(k+1).
Cf. A000096, A284231, A284461, A284414 (this triangle read by rows).

Sum_{k=n..n*(n+3)/2} (k+1) * T(n,k) = A284231(n).

cp's OEIS Frontend

A284778 Number of self-avoiding planar walks of length n+1 starting at (0,0), ending at (n,0), remaining in the first quadrant and using steps (0,1), (1,0), (1,1), (-1,1), and (1,-1) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

A284230 Number of self-avoiding planar walks starting at (0,0), ending at (n,0), remaining in the first quadrant and using steps (0,1), (1,0), (1,1), (-1,1), and (1,-1) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A284461 Number of self-avoiding planar walks starting at (0,0), ending at (n,n), remaining in the first quadrant and using steps (0,1), (1,0), (1,1), (-1,1), and (1,-1) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A284415 Number of self-avoiding planar walks of length n starting at (0,0), ending on the x-axis, remaining in the first quadrant and using steps (0,1), (1,0), (1,1), (-1,1), and (1,-1) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal.

Views

Author

Keywords

Links

Crossrefs

Formula

A284416 Number of self-avoiding planar walks of length 2n starting at (0,0), ending at (n,0), remaining in the first quadrant and using steps (0,1), (1,0), (1,1), (-1,1), and (1,-1) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal.

Views

Author

Keywords

Links

Crossrefs

Formula

A284418 Number of self-avoiding planar walks of length n*(n+1)/2 starting at (0,0), ending at (n,0), remaining in the first quadrant and using steps (0,1), (1,0), (1,1), (-1,1), and (1,-1) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal.

Views

Author

Keywords

Links

Crossrefs

Formula

Views

Author

Keywords

Links

Crossrefs

Views

Author

Keywords

Examples

Links

Crossrefs

Formula