Can You Permeate the Pyramid?

Sixteen points form a diamond (rows of $1,2,3,4,3,2,1$), joined by the edges of a triangular grid. How many distinct paths run from the top point to the bottom point if you may only move downward or sideways, never upward, and never revisit a point?

The Fiddler, Zach Wissner-Gross, May 16, 2025(original post)

Solution

Sideways moves are what make this interesting: within a row you may walk left or right before dropping down, as long as you never repeat a point. A depth-first count over the diamond’s edges, forbidding any move to a higher row, gives $$\boxed{2304}\ \text{paths}.$$

The computation

Place the sixteen points, wire up the triangular-grid edges (same-row neighbours and the two down-diagonals), then depth-first count every self-avoiding route from top to bottom that never steps to a higher row.

import itertools as it
rows = [1, 2, 3, 4, 3, 2, 1]; P = []; row = {}
for r, n in enumerate(rows):
    for k in range(n): P.append((k - (n - 1)/2, -r)); row[len(P) - 1] = r
E = {i: [] for i in range(len(P))}
for a, b in it.combinations(range(len(P)), 2):
    dx, dy = abs(P[a][0] - P[b][0]), abs(P[a][1] - P[b][1])
    if (dy < 1e-9 and abs(dx - 1) < 1e-9) or (abs(dy - 1) < 1e-9 and abs(dx - 0.5) < 1e-9):
        E[a].append(b); E[b].append(a)
top, bot = 0, len(P) - 1; cnt = 0
def dfs(u, vis):
    global cnt
    if u == bot: cnt += 1; return
    for v in E[u]:
        if v not in vis and row[v] >= row[u]: dfs(v, vis | {v})
dfs(top, {top}); print(cnt)            # 2304

Extra Credit

Replace the flat diamond with a three-dimensional triangular bipyramid of $30$ points (triangular layers $1,3,6,10,6,3,1$) and ask the same question. How many paths from top to bottom?

The same rule (down or sideways, no repeats) applies, but the count now hinges on the exact $3$-dimensional adjacency of the bipyramid, which the source specifies by figure. That figure sits behind the paywall and the wiring is not pinned down by the text alone, so I do not assert a value here: the answer is the count of self-avoiding non-ascending top-to-bottom walks on whatever adjacency the figure fixes, and the sideways freedom makes it very large.