cp's OEIS Frontend

A380120 Triangle read by rows: T(n, k) is the number of walks of length n on the Z X Z grid with unit steps in all four directions (NSWE) starting at (0, 0). k is the absolute value of the x-coordinate of the endpoint of the walk.

%I A380120 #21 May 27 2025 07:28:38
%S A380120 1,2,2,6,8,2,20,30,12,2,70,112,56,16,2,252,420,240,90,20,2,924,1584,
%T A380120 990,440,132,24,2,3432,6006,4004,2002,728,182,28,2,12870,22880,16016,
%U A380120 8736,3640,1120,240,32,2,48620,87516,63648,37128,17136,6120,1632,306,36,2
%N A380120 Triangle read by rows: T(n, k) is the number of walks of length n on the Z X Z grid with unit steps in all four directions (NSWE) starting at (0, 0). k is the absolute value of the x-coordinate of the endpoint of the walk.
%H A380120 Alin Bostan, <a href="https://www-apr.lip6.fr/sem-comb-slides/IHP-bostan.pdf">Computer Algebra for Lattice Path Combinatorics</a>, Séminaire de Combinatoire Philippe Flajolet, Institut Henri Poincaré, March 28, 2013.
%H A380120 Alin Bostan and Manuel Kauers, <a href="https://arxiv.org/abs/0811.2899">Automatic Classification of Restricted Lattice Walks</a>, arXiv:0811.2899 [math.CO], 2008-2009; Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AK, (FPSAC 2009).
%H A380120 R. K. Guy, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">Catwalks, sandsteps and Pascal pyramids</a>, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
%F A380120 T(n, k) = binomial(2*n, n - k) if k = 0, otherwise 2*binomial(2*n, n - k).
%F A380120 Assuming the columns starting at n = 0, i.e. prepended by k zeros:
%F A380120 T(n, k) = [x^n] (2^(2*k+1)*x^k / (sqrt(1-4*x)*(1+sqrt(1-4*x))^(2*k))) for k >= 1.
%F A380120 T(n, k) = n! * [x^n] (2*BesselI(k, 2*x)*exp(2*x)) for k >= 1.
%e A380120 Triangle starts:
%e A380120   [0] [    1]
%e A380120   [1] [    2,     2]
%e A380120   [2] [    6,     8,     2]
%e A380120   [3] [   20,    30,    12,     2]
%e A380120   [4] [   70,   112,    56,    16,     2]
%e A380120   [5] [  252,   420,   240,    90,    20,    2]
%e A380120   [6] [  924,  1584,   990,   440,   132,   24,    2]
%e A380120   [7] [ 3432,  6006,  4004,  2002,   728,  182,   28,   2]
%e A380120   [8] [12870, 22880, 16016,  8736,  3640, 1120,  240,  32,  2]
%e A380120   [9] [48620, 87516, 63648, 37128, 17136, 6120, 1632, 306, 36, 2]
%e A380120 .
%e A380120 For n = 0 there is only the empty walk w = '' with start and end point (x=0, y=0).
%e A380120 For n = 3 the walks depending on the x-coordinate of the endpoint are:
%e A380120 W(x= 3) = {WWW},
%e A380120 W(x= 2) = {NWW,SWW,WNW,WSW,WWN,WWS},
%e A380120 W(x= 1) = {NNW,NSW,NWN,NWS,SNW,SSW,SWN,SWS,WNN,WNS,WSN,WSS,WWE,WEW,EWW},
%e A380120 W(x= 0) = {NNN,NNS,NSN,NSS,NWE,NEW,SNN,SNS,SSN,SSS,SWE,SEW,WNE,WSE,WEN,WES,ENW,ESW,EWN,EWS},
%e A380120 W(x=-1) = {NNE,NSE,NEN,NES,SNE,SSE,SEN,SES,WEE,ENN,ENS,ESN,ESS,EWE,EEW},
%e A380120 W(x=-2) = {NEE,SEE,ENE,ESE,EEN,EES},
%e A380120 W(x=-3) = {EEE}.
%e A380120 T(3, 0) = card(W(x=0)) = 20, T(3, 1) = card(W(x=1)) + card(W(x=-1)) = 30,
%e A380120 T(3, 2) = card(W(x=2)) + card(W(x=-2)) = 12, T(3, 3) = card(W(x=3)) + card(W(x=-3)) = 2.
%p A380120 T := (n, k) -> ifelse(k = 0, binomial(2*n, n - k), 2*binomial(2*n, n - k)):
%p A380120 seq(print(seq(T(n, k), k = 0..n)), n = 0..9);
%o A380120 (Python)
%o A380120 from dataclasses import dataclass
%o A380120 @dataclass
%o A380120 class Walk:
%o A380120     s: str = ""
%o A380120     x: int = 0
%o A380120     y: int = 0
%o A380120 def Trow(n: int) -> list[int]:
%o A380120     W = [Walk()]
%o A380120     row = [0] * (n + 1)
%o A380120     for w in W:
%o A380120         if len(w.s) == n:
%o A380120             row[abs(w.x)] += 1
%o A380120         else:
%o A380120             for s in "NSWE":
%o A380120                 x = y = 0
%o A380120                 match s:
%o A380120                     case "W": x =  1
%o A380120                     case "E": x = -1
%o A380120                     case "N": y =  1
%o A380120                     case "S": y = -1
%o A380120                     case _  : pass
%o A380120                 W.append(Walk(w.s + s, w.x + x, w.y + y))
%o A380120     return row
%o A380120 for n in range(10): print(Trow(n))
%Y A380120 Related triangles: A052174 (N X N), A378067 (Z X N), A379822 (Z X Z, variant), A380119.
%Y A380120 Cf. A000984 (column 0), A162551 (column 1), A006659 (column 2), A000302 (row sums), A068551 (row sum without column 0), A040000 (row minimum).
%K A380120 nonn,tabl,walk
%O A380120 0,2
%A A380120 _Peter Luschny_, Jan 17 2025