Fixed-excess simple paths in multidimensional king graphs

Let Kd,n = P_n⊠d be the d-fold strong product of a path, with opposite corners s and t. For k ≥ 0, let Cd,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 Cd,k(n) = Σ_{S ⊆ In+k−1,k} (−1)|S| Mn,k(S)^d. Consequently, as a function of d, Cd,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 Qd,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 Cn,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.