Fixed-excess simple paths in multidimensional king graphs

Abstract

Let K_{d,n} = P_n^{⊠d} be the d-fold strong product of a path, with opposite corners s and t. For k ≥ 0, let C_{d,k}(n) count simple s–t paths with n − 1 + k edges. Coordinate deficits show that every such path has at most dk moves other than the positive main diagonal. We prove that C_{d,k}(n) = Σ_{S ⊆ I_{n+k−1,k}} (−1)^{|S|} M_{n,k}(S)^d. Consequently, as a function of d, C_{d,k}(n) is a finite linear combination of integer exponentials and therefore satisfies a constant-coefficient recurrence. For every d ≥ 2, we obtain closed forms for k = 0, 1, 2, 3; the k = 3 formula is accompanied by an independently executable Möbius certificate. A constructive skeleton-gap argument proves polynomiality for fixed d and k throughout the sufficient range n ≥ d²k² + (2d − 1)k + 2, with Q_{d,k}(n) = 1/(k!)^d [n^(dk) + α_d(k)n^(dk−1) + O(n^(dk−2))], where α_d(k) = k(2k − 3) for d = 2, and α_d(k) = (3d/2)k(k − 1) for d ≥ 3. An independent nineteen-skeleton classification verifies the two-dimensional excess-two formula. Reflection gives the exact admissible one-coordinate word count, and in the growing-dimension regime C_{n,k}(n) ~ e^[3k(k−1)/2] (n^k/k!)^n for fixed k. The novelty claim is restricted to this fixed-excess structure; the graph family and the elementary partition by path length are not new.