201227

Python

Dyck path とSelf-avoiding walk の融合(8)

151123(6) 分より多く求めることができた。

from graphillion import GraphSet

def make_stairs(m, n):
    s = 1
    grids = []
    for i in range(m * n + 1, 1, -m):
        for j in range(i - 1):
            a, b, c = s + j, s + j + 1, s + i + j
            grids.append((a, b))
            if j < i - m:
                grids.append((a, c))
        s += i
    return grids

def A(m, n):
    if m== 0 or n == 0: return 1
    universe = make_stairs(m, n)
    GraphSet.set_universe(universe)
    start, goal = m * n + 1, (n + 1) * (m * n + 2) // 2
    paths = GraphSet.paths(start, goal)
    return paths.len()

a = [0, 18, 12, 9, 7, 6]
for m in range(1, 6):
    print([m, [A(m, n) for n in range(a[m])]])

出力結果

[1, [1, 1, 2, 7, 40, 369, 5680, 150707, 6993712, 567670347, 80294818098, 19750798800833, 8447500756620198, 6286515496550185699, 8145835634791919637646, 18387066260739625200447575, 72319765957232441125506763756, 495718308213370458738098777141317]]

[2, [1, 1, 4, 44, 1282, 105022, 25769912, 19275194154, 43766618972372, 300611108229024928, 6247844562000612352002, 393544904039878168133931630]]

[3, [1, 1, 8, 284, 44360, 33970104, 136342264948, 2895975018297704, 323953287601729898128]]

[4, [1, 1, 16, 1872, 1592536, 11455899880, 752600965180800]]

[5, [1, 1, 32, 12384, 57870848, 3912442265360]]