Compute the number of states for an n-block Blocks World planning problem.

blocksstates.py

import math, sys

# Number of blocks to manipulate
nblocks = int(sys.argv[1])

# Number of ways to order a stack of nstack blocks.
def orderings(nstack):
    return math.factorial(nstack)

# Generate all partitions of nblocks. A partition of nblocks
# has the property that the sum of the elements is nblocks.
# https://stackoverflow.com/a/44209393
def partitions(n, I=1):
    yield (n,)
    for i in range(I, n//2 + 1):
        for p in partitions(n-i, i):
            yield (i,) + p

# Number of occurrences of s in p.
def count(p, s):
    return sum(1 for s0 in p if s0 == s)

# Number of states for an n-block system with given partitions.
def nstates(parts):
    nstates = 0
    for p in parts:
        n = sum(p)
        v = 1
        # Overestimate by ignoring duplicates.
        for s in p:
            v *= math.comb(n, s) * orderings(s)
            n -= s
        # Now divide out duplicates.
        for s in set(p):
            v //= math.factorial(count(p, s))
        nstates += v
        print(p, v)
    return nstates

n = nstates(partitions(nblocks))
print(n, math.log10(n))