Repository navigation
Speculative Restriction Counts
enumeratio edited this page Oct 5, 2026
·
1 revision
Speculative design. Open, not settled — thinking and proposals, not shipped behavior. See Roadmap for what's in flight.
Exact completion counts for the permutation classes that still filter (see
Speculative Restrictions §5), kept as plain TypeScript until someone ports them to Epsil.
completions(n, P) is the number of members of size n that start with the prefix P. Each was
checked against brute force over every reachable prefix (a prefix whose parent has a
completion) for n = 0..9. Run a checker with node --experimental-strip-types, the shared
walker saved as verify-lib.ts beside it.
export function verify(name: string, pred: (p: number[]) => boolean, fn: (n: number, P: number[]) => number, known: (n: number) => number, maxN: number) {
let checked = 0, bad = 0;
for (let n = 0; n <= maxN; n++) {
const cnt = new Map<string, number>();
let total = 0;
const rec = (p: number[], used: boolean[]) => {
if (p.length === n) { if (pred(p)) { total++; for (let k = 0; k <= n; k++) { const key = p.slice(0, k).join(","); cnt.set(key, (cnt.get(key) ?? 0) + 1); } } return; }
for (let v = 1; v <= n; v++) if (!used[v]) { used[v] = true; p.push(v); rec(p, used); p.pop(); used[v] = false; }
};
rec([], []);
if (fn(n, []) !== total || known(n) !== total) { bad++; console.log(name, "count mismatch", n, fn(n, []), known(n), total); }
const walk = (prefix: number[]) => {
for (let v = 1; v <= n; v++) if (!prefix.includes(v)) {
const q = [...prefix, v], want = cnt.get(q.join(",")) ?? 0, got = fn(n, q); checked++;
if (want !== got) { bad++; if (bad < 10) console.log(name, n, q.join(""), "want", want, "got", got); }
if (want > 0) walk(q);
}
};
walk([]);
console.log(name, "n", n, "total", total, "checked so far", checked, "bad", bad);
}
console.log(name, { checked, bad });
}baxter-completions.ts:
// Completion count for lex prefixes of Baxter permutations (avoid 2-41-3, 3-14-2).
// Appending entries one at a time is the (h,k) generating tree seen from the right: a new last entry may go
// immediately below an RTL minimum or immediately above an RTL maximum of the current word ("sites").
// Sites form one list in value order with a cut (lower sites | upper sites); choosing a site removes it and
// every site between it and the cut, and puts a new pair (below x, above x) there, cut between them.
// Each site lies in a gap of the prefix values; the gap must receive exactly its free-value count.
// State = (site gaps, cut, remaining counts), with exhausted gaps dropped and gap labels compressed.
export const baxterStats = { states: 0 };
const memo = new Map<string, number>();
function baxterPrefixOk(P: number[]): boolean {
const n = P.length;
for (let pos = 0; pos + 1 < n; pos++) {
const a = P[pos], b = P[pos + 1];
for (let i = 0; i < pos; i++) {
if (a > b ? b < P[i] && P[i] < a : a < P[i] && P[i] < b)
for (let k = pos + 2; k < n; k++) if (a > b ? P[i] < P[k] && P[k] < a : a < P[k] && P[k] < P[i]) return false;
}
}
return true;
}
// sites: gap labels in value order; cut = number of lower sites; r: remaining count per gap label
function solve(sites: number[], cut: number, r: number[]): number {
// drop exhausted gaps, compress labels
const live: number[] = []; const map = new Map<number, number>(); const nr: number[] = [];
r.forEach((x, g) => { if (x > 0) { map.set(g, nr.length); nr.push(x); } });
if (nr.length === 0) return 1;
let ncut = 0; const ns: number[] = [];
sites.forEach((g, i) => { const m = map.get(g); if (m !== undefined) { ns.push(m); if (i < cut) ncut++; } });
const seen = new Set(ns); if (seen.size < nr.length) return 0; // a gap with nothing left to fill it
const key = ns.join(",") + "|" + ncut + "|" + nr.join(",");
const hit = memo.get(key); if (hit !== undefined) return hit;
baxterStats.states++;
let total = 0;
for (let i = 0; i < ns.length; i++) {
const g = ns[i];
const r2 = nr.slice(); r2[g]--;
let next: number[], c2: number;
if (i < ncut) { next = [...ns.slice(0, i), g, g, ...ns.slice(ncut)]; c2 = i + 1; }
else { next = [...ns.slice(0, ncut), g, g, ...ns.slice(i + 1)]; c2 = ncut + 1; }
total += solve(next, c2, r2);
}
memo.set(key, total); return total;
}
const baxterCount = (n: number): number => { // CGHK sum, exact via BigInt-free binomials (n small)
if (n <= 1) return 1;
const C = (a: number, b: number) => { let x = 1; for (let i = 1; i <= b; i++) x = (x * (a - b + i)) / i; return Math.round(x); };
let s = 0; for (let k = 0; k <= n - 1; k++) s += C(n + 1, k) * C(n + 1, k + 1) * C(n + 1, k + 2);
return Math.round(s / (C(n + 1, 1) * C(n + 1, 2)));
};
export function baxterCompletions(n: number, P: number[]): number {
const f = P.length;
if (f === 0) return baxterCount(n);
if (!baxterPrefixOk(P)) return 0;
const sorted = [...P].sort((a, b) => a - b);
const rank = (v: number) => sorted.indexOf(v) + 1;
const r: number[] = [];
for (let g = 0; g <= f; g++) r.push((g === f ? n + 1 : sorted[g]) - (g === 0 ? 0 : sorted[g - 1]) - 1);
const mins: number[] = [], maxs: number[] = []; // RTL minima / maxima, scanned right to left
let lo = Infinity, hi = -Infinity;
for (let i = f - 1; i >= 0; i--) { if (P[i] < lo) { lo = P[i]; mins.unshift(P[i]); } if (P[i] > hi) { hi = P[i]; maxs.push(P[i]); } }
// maxs is now ascending in value (nearest the cut first); mins ascending left to right
const sites = [...mins.map((j) => rank(j) - 1), ...maxs.map((m) => rank(m))];
return solve(sites, mins.length, r);
}Checker:
import { baxterCompletions, baxterStats } from "./baxter-completions.ts";
import { verify } from "./verify-lib.ts";
const pred = (perm: number[]): boolean => { const n = perm.length;
for (let pos = 0; pos + 1 < n; pos++) { const a = perm[pos], b = perm[pos + 1];
for (let i = 0; i < pos; i++) { if (a > b ? b < perm[i] && perm[i] < a : a < perm[i] && perm[i] < b)
for (let k = pos + 2; k < n; k++) if (a > b ? perm[i] < perm[k] && perm[k] < a : a < perm[k] && perm[k] < perm[i]) return false; } }
return true; };
const B = [1, 1, 2, 6, 22, 92, 422, 2074, 10754, 58202, 326988];
verify("baxter", pred, baxterCompletions, (n) => B[n], Number(process.argv[2] ?? 8));
console.log(baxterStats);vexillary-completions.ts:
// Completions of a lex prefix in Av(2143). Exact; memoised over states (m, S, t), S a bitmask of cuts.
// State = constraints on the m free values (ranks 1..m) left by the prefix:
// t: free ranks > t must appear in increasing order (from a prefix inversion; t = m: none)
// S: for each cut s in S (a prefix value sits between free ranks s and s+1), after the first
// free rank <= s every rank > s appears increasing.
// Plus: the suffix itself avoids 2143. Reachable states ~ 2^m (measured), so exponential, not poly.
const has2143 = (w: number[]) => {
const n = w.length;
for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) if (w[i] > w[j])
for (let k = j + 1; k < n; k++) if (w[k] > w[i])
for (let l = k + 1; l < n; l++) if (w[l] < w[k] && w[l] > w[i]) return true;
return false;
};
const memo = new Map<string, number>();
export const stateCountVex = () => memo.size;
function rec(m: number, S: number, t: number): number {
if (m <= 1) return 1;
if (t >= m) t = m;
const key = m + "|" + S + "|" + t;
const hit = memo.get(key);
if (hit !== undefined) return hit;
let total = 0;
const m2 = m - 1;
const top = Math.min(t + 1, m); // x = t+1 is the only allowed top element
for (let x = 1; x <= top; x++) {
if (x === t + 1) { total += rec(m2, S, t); continue; } // smallest top rank: cuts and t unchanged
// x <= t: bottom element. Triggered cuts: s >= x -> threshold s-1.
let t2 = Math.min(t, m) - 1;
let S2 = 0;
for (let s = 1; s <= m - 1; s++) if (S >> s & 1) {
if (s >= x) t2 = Math.min(t2, s - 1);
else S2 |= 1 << s;
}
if (x >= 2 && x <= m - 1) S2 |= 1 << (x - 1);
if (t2 > m2) t2 = m2;
// canonical: cuts must lie in [1, t2-1]
S2 &= t2 >= 1 ? (1 << t2) - 2 : 0;
total += rec(m2, S2, t2);
}
memo.set(key, total);
return total;
}
function derive(n: number, P: number[]) {
const free: number[] = [];
for (let v = 1; v <= n; v++) if (!P.includes(v)) free.push(v);
const m = free.length;
if (has2143(P)) return null;
const cut = (v: number) => { let c = 0; for (const q of free) if (q < v) c++; return c; };
let t = m;
for (let i = 0; i < P.length; i++) for (let j = i + 1; j < P.length; j++) if (P[i] > P[j]) {
t = Math.min(t, cut(P[i]));
for (let k = j + 1; k < P.length; k++) if (P[k] > P[i] && free.some((q) => q > P[i] && q < P[k])) return 0;
}
let S = 0;
for (const v of P) { const c = cut(v); if (c >= 1 && c <= t - 1) S |= 1 << c; }
return { m, S, t };
}
export function completions(n: number, P: number[]): number {
const d = derive(n, P);
if (d === null || d === 0) return 0;
return rec(d.m, d.S, d.t);
}Checker:
import { completions, stateCountVex } from "./vexillary-completions.ts";
const has2143 = (w: number[]) => { const n = w.length; for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) if (w[i] > w[j]) for (let k = j + 1; k < n; k++) if (w[k] > w[i]) for (let l = k + 1; l < n; l++) if (w[l] < w[k] && w[l] > w[i]) return true; return false; };
const brute = (n: number, P: number[]) => { let c = 0; const used = new Set(P); const cur = [...P];
const go = () => { if (cur.length === n) { if (!has2143(cur)) c++; return; } for (let v = 1; v <= n; v++) if (!used.has(v)) { used.add(v); cur.push(v); if (!has2143(cur)) go(); cur.pop(); used.delete(v); } };
go(); return c; };
const N = +(process.argv[2] ?? 8); let checked = 0, bad = 0;
for (let n = 0; n <= N; n++) {
const walk = (P: number[]) => { for (let v = 1; v <= n; v++) if (!P.includes(v)) { const q = [...P, v]; const want = brute(n, q), got = completions(n, q); checked++;
if (want !== got) { bad++; if (bad < 10) console.log("MISMATCH", n, q.join(","), want, got); } if (want > 0) walk(q); } };
if (completions(n, []) !== brute(n, [])) { bad++; console.log("count", n); }
walk([]);
console.log("n", n, "count", completions(n, []), "checked", checked, "bad", bad);
}
console.log({ checked, bad, states: stateCountVex() });smooth-completions.ts:
// Completions of a lex prefix in Av(3412, 4231). Exact. Memoised on a canonical constraint key
// (rank space over the m free values); the key is derived from the prefix in O(f^3 + f^2 m):
// B : cuts s (a prefix value sits between free ranks s and s+1), 2 <= s <= m-1:
// after the first free rank > s, ranks <= s are decreasing (3412, one prefix value)
// T : ranks <= T are decreasing (3412, prefix ascent)
// C : ranks <= C avoid 231 (4231, one prefix value)
// X : pairs (a,b), a<b: every rank <= a precedes every rank in (a,b] (4231, prefix inversion)
// Zero when a prefix ascent x<y then z<x leaves a free value in (z,x), or a prefix 4-2-3 leaves
// a free value below the 2. Key count grows ~2.1^n (exponential, not polynomial).
const has = (w: number[]) => {
const n = w.length;
for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) for (let k = j + 1; k < n; k++) for (let l = k + 1; l < n; l++) {
const a = w[i], b = w[j], c = w[k], d = w[l];
if ((c < d && d < a && a < b) || (d < b && b < c && c < a)) return true;
}
return false;
};
function key(n: number, P: number[]): string | null {
if (has(P)) return null;
const free: number[] = [];
for (let v = 1; v <= n; v++) if (!P.includes(v)) free.push(v);
const m = free.length, f = P.length;
const cut = (v: number) => { let c = 0; for (const q of free) if (q < v) c++; return c; };
let T = 0;
const X = new Set<string>();
for (let i = 0; i < f; i++) for (let j = i + 1; j < f; j++) {
if (P[i] < P[j]) {
T = Math.max(T, cut(P[i]));
for (let k = j + 1; k < f; k++) if (P[k] < P[i] && free.some((q) => q > P[k] && q < P[i])) return null;
} else {
const a = cut(P[j]), b = cut(P[i]);
if (a >= 1 && b > a) X.add(a + ":" + b);
for (let k = j + 1; k < f; k++) if (P[k] > P[j] && P[k] < P[i] && free.some((q) => q < P[j])) return null;
}
}
const B = new Set<number>();
for (const v of P) { const c = cut(v); if (c >= 2 && c <= m - 1) B.add(c); }
let C = f ? cut(Math.max(...P)) : 0;
if (C < 3) C = 0;
if (T < 2) T = 0;
return `${m}|${[...B].sort((a, b) => a - b)}|${T}|${C}|${[...X].sort()}`;
}
const memo = new Map<string, number>();
export const keyCountSmooth = () => memo.size;
export function completions(n: number, P: number[]): number {
const k = key(n, P);
if (k === null) return 0;
if (P.length === n) return 1;
const hit = memo.get(k);
if (hit !== undefined) return hit;
let t = 0;
for (let v = 1; v <= n; v++) if (!P.includes(v)) t += completions(n, [...P, v]);
memo.set(k, t);
return t;
}Checker:
import { completions, keyCountSmooth } from "./smooth-completions.ts";
const hasS = (w: number[]) => { const n = w.length; for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) for (let k = j + 1; k < n; k++) for (let l = k + 1; l < n; l++) { const a = w[i], b = w[j], c = w[k], d = w[l]; if ((c < d && d < a && a < b) || (d < b && b < c && c < a)) return true; } return false; };
const brute = (n: number, P: number[]) => { let c = 0; const used = new Set(P); const cur = [...P];
const go = () => { if (cur.length === n) { if (!hasS(cur)) c++; return; } for (let v = 1; v <= n; v++) if (!used.has(v)) { used.add(v); cur.push(v); if (!hasS(cur)) go(); cur.pop(); used.delete(v); } };
go(); return c; };
const N = +(process.argv[2] ?? 8); let checked = 0, bad = 0;
for (let n = 0; n <= N; n++) {
const walk = (P: number[]) => { for (let v = 1; v <= n; v++) if (!P.includes(v)) { const q = [...P, v]; const want = brute(n, q), got = completions(n, q); checked++;
if (want !== got) { bad++; if (bad < 10) console.log("MISMATCH", n, q.join(","), want, got); } if (want > 0) walk(q); } };
if (completions(n, []) !== brute(n, [])) { bad++; console.log("count", n); }
walk([]);
console.log("n", n, "count", completions(n, []), "checked", checked, "bad", bad);
}
console.log({ checked, bad, states: keyCountSmooth() });