r"""Is the path the tree that minimises Z_F(a) = sum_{X subset V(F)} a^|X| 2^{e(F[X])}?

For the Graph Motif cost g(X) = (k - |X|) + comp(F[X]) on a spanning tree F of
the solution, the exponential moments are 2^{-k} Z_F(y) with a = y (because
comp = |X| - e(F[X]) and y^|X| 2^{|X|} 2^{-|X|} = y^|X|).  If the path
minimises Z_F for every a > 0, the Theorem 3.5 rate over all connected
solutions equals the path rate computed in motif_rates.py.  Here we test all
labelled trees on k <= 8 vertices (via Pruefer codes, deduplicated by Z value)
for a in a grid.  Exact rationals; standard library only.
"""
import itertools
from fractions import Fraction as Fr


def pruefer_to_edges(seq, k):
    degree = [1] * k
    for x in seq:
        degree[x] += 1
    edges = []
    for x in seq:
        for leaf in range(k):
            if degree[leaf] == 1:
                edges.append((leaf, x))
                degree[leaf] -= 1
                degree[x] -= 1
                break
    u, v = [i for i in range(k) if degree[i] == 1]
    edges.append((u, v))
    return edges


def Z(edges, k, a):
    # polynomial in a: coefficients by |X|, weight 2^{e(X)}
    total = Fr(0)
    for mask in range(1 << k):
        e = sum(1 for (u, v) in edges if (mask >> u) & 1 and (mask >> v) & 1)
        total += a ** bin(mask).count("1") * 2 ** e
    return total


grid = [Fr(1, 8), Fr(1, 4), Fr(1, 2), Fr(1), Fr(2), Fr(4)]
violations = 0
for k in range(3, 9):
    path = [(i, i + 1) for i in range(k - 1)]
    zp = [Z(path, k, a) for a in grid]
    seen = set()
    for seq in itertools.product(range(k), repeat=k - 2):
        edges = pruefer_to_edges(list(seq), k)
        z = tuple(Z(edges, k, a) for a in grid)
        if z in seen:
            continue
        seen.add(z)
        for zi, zpi in zip(z, zp):
            if zi < zpi:
                violations += 1
    print(f"k={k}: {len(seen)} distinct Z-profiles; path minimal so far: {violations == 0}")
print("violations:", violations)