A387912 Triangle read by rows: T(n,k) is the number of 3-dimensional balanced ballot paths of 3n steps such that the height is exactly k, 2 <= k <= 2*n.

1, 1, 2, 2, 1, 8, 18, 10, 5, 1, 26, 120, 142, 117, 42, 14, 1, 80, 720, 1480, 1789, 1130, 596, 168, 42, 1, 242, 4122, 13680, 23205, 20940, 14817, 6936, 2781, 660, 132, 1, 728, 23058, 119042, 276749, 332830, 296805, 185306, 97922, 37796, 12430, 2574, 429, 1, 2186, 127440, 1001022, 3142289, 4873500, 5315887, 4102472, 2642389, 1329328, 577005, 192478, 54197, 10010, 1430

Offset

1,3

Comments

For point x (x_1,x_2,x_3) in the 3-dimensional lattice, we define the height of x as h_3(x) := 2x_1 - x_2 - x_3. The 3-dimensional balanced ballot path (multidimensional Dyck path), is a sequence of 3*n steps with initial point (0,0,0) and ending at (n,n,n) satisfying that each step is a standard unit vector and each point of the path satisfies x_1 >= x_2 >= x_3. T(n,k) is the number of 3-dimensional balanced ballot paths of 3*n steps such that the largest height reached by any point in the path is equal to k; i.e. for at least one intermediate point h(x) = k, but for no points h(x) > k.

Links

Sean A. Irvine, Table of n, a(n) for n = 1..10000 (rows 1..100 flattened)

Ryota Inagaki and Dimana Pramatarova, On Semisymmetric Height and a Multidimensional Generalization of Weighted Catalan Numbers, arXiv:2604.04900 [math.CO], 2026. See p. 26.

Example

Triangle begins:
  1;
  1,   2,     2;
  1,   8,    18,     10,      5;
  1,  26,   120,    142,    117,     42,     14;
  1,  80,   720,   1480,   1789,   1130,    596,    168,    42;
  1, 242,  4122,  13680,  23205,  20940,   6936,   2781,   660,   132;
  1, 728, 23058, 119042, 276749, 332830, 296805, 185306, 97922, 37796, 12430, 2574, 429;
  ...

Prog

(Python)
from functools import lru_cache
# change values for the endpoint t=(n, n, n) and the height bound bd=k
t = (5, 5, 5)
bd = 5
def ht(t):
    """Height function h(x0, x1, x2) = 2*x0 - x1 - x2."""
    return 2 * t[0] - t[1] - t[2]
@lru_cache(maxsize=None)
def altern(x0, x1, x2, bd):
    """
    Number of 3D ballot paths from (0, 0, 0) to (x0, x1, x2)
    with the constraints:
      - x0 >= x1 >= x2 at all times (ballot condition)
      - height <= bd when stepping in x1 or x2
    """
    if (x0, x1, x2) == (0, 0, 0):
        return 1
    count = 0
    if x0 > 0 and x0 - 1 >= x1:
        count += altern(x0 - 1, x1, x2, bd)
    if x1 > 0 and x1 - 1 >= x2 and ht((x0, x1 - 1, x2)) <= bd:
        count += altern(x0, x1 - 1, x2, bd)
    # step along x2 (height cap)
    if x2 > 0 and ht((x0, x1, x2 - 1)) <= bd:
        count += altern(x0, x1, x2 - 1, bd)
    return count
@lru_cache(maxsize=None)
def exact_height(x0, x1, x2, bd):
    if bd < 0:
        return 0
    return altern(x0, x1, x2, bd) - altern(x0, x1, x2, bd - 1)
print(exact_height(*t, bd))

Crossrefs

Row sums are A005789.

Rightmost terms are A000108 (final term), A024483 (penultimate term).

Columns k=2..3 are A000012, A024023.

Sequence in context: A117260 A077944 A077992 * A126586 A128463 A136730

Adjacent sequences: A387909 A387910 A387911 * A387913 A387914 A387915

Keyword

nonn,tabf

Author

Dimana Pramatarova and Ryota Inagaki, Oct 11 2025

Status

approved