A284652 -id:A284652 - cp's OEIS frontend

A284414 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), n>=0, n<=k<=n*(n+3)/2, read by rows.

1, 1, 1, 2, 1, 1, 1, 4, 4, 4, 7, 3, 1, 1, 9, 8, 16, 21, 17, 15, 10, 9, 4, 1, 1, 21, 22, 54, 87, 87, 116, 99, 91, 78, 42, 31, 17, 10, 5, 1, 1, 51, 54, 178, 269, 370, 499, 536, 590, 560, 510, 420, 350, 268, 185, 132, 69, 44, 23, 11, 6, 1, 1

Offset: 0

Alois P. Heinz, Mar 26 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,  4,  1,  1;
.  .  .  .  .  21, 22, 54, 87, 87, 116, 99, 91, 78, 42, 31, 17, 10, 5, 1, 1;

Alois P. Heinz, Rows n = 0..50, flattened
Alois P. Heinz, Animation of T(5,12)=91 walks
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.
Cf. A000096, A284231, A284461, A284652 (this triangle read by columns).

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

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.

Original entry on oeis.org

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

cp's OEIS Frontend

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

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