A306814
Number T(n,k) of n-step paths from (0,0) to (0,k) that stay in the first quadrant (but may touch the axes) consisting of steps (-1,0), (0,1), (0,-1) and (1,-1); triangle T(n,k), n>=0, 0<=k<=n, read by rows.
Original entry on oeis.org
1, 0, 1, 1, 0, 1, 1, 2, 0, 1, 2, 3, 3, 0, 1, 7, 5, 6, 4, 0, 1, 10, 23, 9, 10, 5, 0, 1, 38, 35, 51, 14, 15, 6, 0, 1, 89, 131, 84, 94, 20, 21, 7, 0, 1, 229, 355, 309, 168, 155, 27, 28, 8, 0, 1, 752, 874, 947, 608, 300, 237, 35, 36, 9, 0, 1, 1873, 3081, 2292, 2075, 1070, 495, 343, 44, 45, 10, 0, 1
Offset: 0
T(4,2) = 3:
[(0,0), (0,1), (0,0), (0,1), (0,2)],
[(0,0), (0,1), (0,2), (0,1), (0,2)],
[(0,0), (0,1), (0,2), (0,3), (0,2)].
Triangle T(n,k) begins:
1;
0, 1;
1, 0, 1;
1, 2, 0, 1;
2, 3, 3, 0, 1;
7, 5, 6, 4, 0, 1;
10, 23, 9, 10, 5, 0, 1;
38, 35, 51, 14, 15, 6, 0, 1;
89, 131, 84, 94, 20, 21, 7, 0, 1;
229, 355, 309, 168, 155, 27, 28, 8, 0, 1;
752, 874, 947, 608, 300, 237, 35, 36, 9, 0, 1;
...
-
b:= proc(n, x, y) option remember; `if`(min(n, x, y, n-x-y)<0, 0,
`if`(n=0, 1, add(b(n-1, x-d[1], y-d[2]),
d=[[-1, 0], [0, 1], [0, -1], [1, -1]])))
end:
T:= (n, k)-> b(n, 0, k):
seq(seq(T(n, k), k=0..n), n=0..12);
-
b[n_, x_, y_] := b[n, x, y] = If[Min[n, x, y, n - x - y] < 0, 0, If[n == 0, 1, Sum[b[n - 1, x - d[[1]], y - d[[2]]], {d, {{-1, 0}, {0, 1}, {0, -1}, {1, -1}}}]]];
T[n_, k_] := b[n, 0, k];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 14 2020, after Maple *)
A151346
Number of walks within N^2 (the first quadrant of Z^2) starting and ending at (0,0) and consisting of n steps taken from {(-1, 0), (-1, 1), (0, -1), (1, 0)}.
Original entry on oeis.org
1, 0, 1, 1, 2, 7, 10, 38, 89, 229, 752, 1873, 6009, 17746, 51970, 168199, 503489, 1609327, 5131184, 16183314, 53017947, 170708648, 559207257, 1846295302, 6075728984, 20284263554, 67649481468, 226890912838, 765669449228, 2585600921015, 8785174853897, 29918390234278, 102190450691351, 350429638975797
Offset: 0
- Alois P. Heinz, Table of n, a(n) for n = 0..1000
- A. Bostan, K. Raschel, B. Salvy, Non-D-finite excursions in the quarter plane, J. Comb. Theory A 121 (2014) 45-63, Table 1 Tag 8, Tag 9.
- M. Bousquet-Mélou and M. Mishna, 2008. Walks with small steps in the quarter plane, ArXiv 0810.4387.
-
aux[i_Integer, j_Integer, n_Integer] := Which[Min[i, j, n] < 0 || Max[i, j] > n, 0, n == 0, KroneckerDelta[i, j, n], True, aux[i, j, n] = aux[-1 + i, j, -1 + n] + aux[i, 1 + j, -1 + n] + aux[1 + i, -1 + j, -1 + n] + aux[1 + i, j, -1 + n]]; Table[aux[0, 0, n], {n, 0, 25}]
A317782
Number of 2n-step paths from (0,0) to (0,n) that stay in the first quadrant (but may touch the axes) consisting of steps (1,0), (0,1), (0,-1) and (-1,1).
Original entry on oeis.org
1, 1, 5, 51, 474, 4329, 43406, 469565, 5228459, 59259957, 686003702, 8097484169, 97005128492, 1175916181703, 14404685872773, 178105648065109, 2220134252592683, 27872257776993240, 352143374331177766, 4474477933645201621, 57147423819800882972
Offset: 0
a(2) = 5: [(0,1),(0,-1),(0,1),(0,1)], [(0,1),(0,1),(0,-1),(0,1)], [(0,1),(0,1),(0,1),(0,-1)], [(1,0),(-1,1),(1,0),(-1,1)], [(1,0),(1,0),(-1,1),(-1,1)].
-
b:= proc(n, x, y) option remember; `if`(min(args, n-x-y)<0, 0, `if`(n=0, 1,
add(b(n-1, x-d[1], y-d[2]), d=[[1, 0], [0, 1], [0, -1], [-1, 1]])))
end:
a:= n-> b(2*n, 0, n):
seq(a(n), n=0..25);
-
b[n_, x_, y_] := b[n, x, y] = If[Min[n, x, y, n - x - y] < 0, 0, If[n == 0, 1, Sum[b[n - 1, x - d[[1]], y - d[[2]]], {d, {{1, 0}, {0, 1}, {0, -1}, {-1, 1}}}]]];
a[n_] := b[2n, 0, n];
a /@ Range[0, 25] (* Jean-François Alcover, May 13 2020, after Maple *)
A151412
Number of walks within N^2 (the first quadrant of Z^2) starting at (0,0), ending on the vertical axis and consisting of n steps taken from {(-1, 1), (0, -1), (0, 1), (1, 0)}.
Original entry on oeis.org
1, 1, 3, 7, 21, 63, 198, 648, 2148, 7303, 25159, 87771, 309885, 1103217, 3961285, 14322270, 52098790, 190586734, 700547511, 2586505466, 9587737311, 35667671240, 133128177959, 498385063314, 1870940572326, 7041423384111, 26563151794983, 100425970551436, 380444157541490, 1443958508666422
Offset: 0
- M. Bousquet-Mélou and M. Mishna, 2008. Walks with small steps in the quarter plane, ArXiv 0810.4387.
-
aux[i_Integer, j_Integer, n_Integer] := Which[Min[i, j, n] < 0 || Max[i, j] > n, 0, n == 0, KroneckerDelta[i, j, n], True, aux[i, j, n] = aux[-1 + i, j, -1 + n] + aux[i, -1 + j, -1 + n] + aux[i, 1 + j, -1 + n] + aux[1 + i, -1 + j, -1 + n]]; Table[Sum[aux[0, k, n], {k, 0, n}], {n, 0, 25}]
Showing 1-4 of 4 results.