"""Exact, independent checks for Kimberling's interlacing-triangle count. Usage: python verify_interlacing.py (Python 3 with NumPy). The worked checks use ranks 1 through 6. The proof covers arbitrary rank. """ from functools import cache from itertools import combinations, permutations, product from math import comb import numpy as np def triangle_constraints(n): """Triples (parent, left child, right child), cells numbered in row order.""" return [ (r * (r - 1) // 2 + j, r * (r + 1) // 2 + j, r * (r + 1) // 2 + j + 1) for r in range(1, n) for j in range(r) ] def direct(n): triples = triangle_constraints(n) return sum( all(min(a[i], a[k]) < a[j] < max(a[i], a[k]) for j, i, k in triples) for a in permutations(range(n * (n + 1) // 2)) ) def threshold_count(n): """Add the labels, smallest first. Only the triples at a changed cell matter.""" cells = n * (n + 1) // 2 full = (1 << cells) - 1 incident = [[] for _ in range(cells)] for parent, left, right in triangle_constraints(n): masks = 1 << parent, 1 << left, 1 << right for i in (parent, left, right): incident[i].append(masks) @cache def count(mask): if mask == full: return 1 remaining = full ^ mask ways = 0 while remaining: bit = remaining & -remaining remaining ^= bit enlarged = mask | bit for parent, left, right in incident[bit.bit_length() - 1]: p = bool(enlarged & parent) l = bool(enlarged & left) r = bool(enlarged & right) if l == r and p != l: break else: ways += count(enlarged) return ways answer = count(0) count.cache_clear() return answer class RectangleSums: def __init__(self, values): rank = values.ndim self.alphabet = values.shape[0] self.width = rank # All counts are nonnegative. These Python-integer checks certify the # signed int64 operations, including intermediate corner sums. self.total = sum(map(int, values.flat)) if (1 << rank) * self.total > np.iinfo(np.int64).max: raise OverflowError("use smaller batches or arbitrary-precision tables") for axis in range(rank): values = values.cumsum(axis=axis) self.prefix = values.reshape(-1) self.strides = [self.alphabet ** i for i in reversed(range(rank))] self.corners = list(product((0, 1), repeat=rank)) def rows(self, bottom): """Count upper fillings for each column of 'bottom', in zero-based labels.""" low = np.minimum(bottom[:-1], bottom[1:]) high = np.maximum(bottom[:-1], bottom[1:]) valid = ((high - low) >= 2).all(axis=0) result = np.zeros(bottom.shape[1], dtype=np.int64) if not valid.any(): return result lower = low[:, valid] upper = high[:, valid] - 1 # For the open integer interval (a,b), sum = prefix[b-1] - prefix[a]. indices = [np.zeros(upper.shape[1], dtype=np.int64)] for axis, stride in enumerate(self.strides): offset_low = lower[axis] * stride offset_high = upper[axis] * stride indices = [item + offset for item in indices for offset in (offset_high, offset_low)] sums = np.zeros(upper.shape[1], dtype=np.int64) for index, corner in zip(indices, self.corners): if sum(corner) % 2: sums -= self.prefix[index] else: sums += self.prefix[index] result[valid] = sums return result def row_blocks(width, alphabet, block=32768): if width == 0: yield np.empty((0, 1), dtype=np.int64) return size = alphabet**width shape = (alphabet,) * width for start in range(0, size, block): yield np.array(np.unravel_index(np.arange(start, min(start + block, size)), shape)) def exact_sum(values): limit = np.iinfo(np.int64).max if values.size and int(values.max()) * values.size > limit: return sum(map(int, values)) return int(values.sum()) def transfer_by_extrema(n): """Return exact counts indexed by the bottom positions of 1 and M.""" if n == 1: return [[1]] m = n * (n + 1) // 2 counts = np.ones(m, dtype=np.int64) for width in range(1, n - 1): box = RectangleSums(counts) next_table = np.empty(m**(width + 1), dtype=np.int64) first = 0 for rows in row_blocks(width + 1, m): size = rows.shape[1] next_table[first:first + size] = box.rows(rows) first += size counts = next_table.reshape((m,) * (width + 1)) box = RectangleSums(counts) answer = [[0] * n for _ in range(n)] for k in range(2, m + 1): weight = (-1)**(m-k) * comb(m-2, k-2) for inner in row_blocks(n - 2, k - 2): for i, j in combinations(range(n), 2): reflected = (n-1-j, n-1-i) if (i, j) > reflected: continue # Reversing a row interchanges reflected pairs of positions. # Complementing the colors interchanges minimum and maximum. rows = np.empty((n, inner.shape[1]), dtype=np.int64) rows[i], rows[j] = 0, k-1 rest = [h for h in range(n) if h not in (i, j)] rows[rest] = inner + 1 ways = weight * exact_sum(box.rows(rows)) positions = {(i, j), (j, i), reflected, reflected[::-1]} for minimum, maximum in positions: answer[minimum][maximum] += ways return answer if __name__ == "__main__": published = (1, 2, 20, 1744, 2002568, 42263042752) for n, expected in enumerate(published, 1): positions = transfer_by_extrema(n) value = sum(map(sum, positions)) assert value == threshold_count(n) == expected if n <= 4: assert value == direct(n) if n == 4: assert positions == [ [0, 160, 110, 68], [160, 0, 264, 110], [110, 264, 0, 160], [68, 110, 160, 0], ] print(f"n={n} count={value:,} checked", flush=True)