Theorem: Let F(m,n,k) be the number of lattice paths from (0,0,0) to (m,n,k) in the positive quadrant of the three-dimensional cubic lattice where the Fundamental Steps are {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1]} Let M, N and K be the shift operators in the m, n and k directions, respecti\ vely (M f(m,n,k):=f(m+1,n,k), Nf(m,n,k):=f(m,n+1,k) , Kf(m,n,k):=f(m,n,k+1) .) Then F(m,n,k) satisfies the following pure recurrences (k + 1 - n + m) (k - 1 - n - m) F(m, n, k) 3 2 ------------------------------------------ - (6 - 7 n + n - 7 k + 6 k n - k n (m + 3) (-m - 1 + n + k) 2 3 2 2 2 - n k + k + 13 m - 9 m n - 9 m k + 4 m k n + 9 m - 3 m n - 3 m k 3 + 2 m ) F(m + 1, n, k)/((m + 3) (-m - 1 + n + k) (k - 2 + n - m)) 2 2 (n - n - 2 + 3 k n - k + k - m - m n - m k) F(m + 2, n, k) - ------------------------------------------------------------ (m + 3) (k - 2 + n - m) + F(m + 3, n, k) = 0 (k + 1 + n - m) (k - 1 - n - m) F(m, n, k) 3 ------------------------------------------ - (-7 m + 6 + m - 7 k + 6 m k (n + 3) (-n - 1 + m + k) 2 2 3 2 2 - m k - k m + k + 13 n - 9 m n - 9 k n + 4 m k n + 9 n - 3 n m 2 3 - 3 k n + 2 n ) F(m, n + 1, k)/((n + 3) (-n - 1 + m + k) (k - 2 + m - n)) 2 2 (m - m - 2 + 3 m k - k + k - m n - n - k n) F(m, n + 2, k) - ------------------------------------------------------------ (n + 3) (k - 2 + m - n) + F(m, n + 3, k) = 0 (k + 1 + n - m) (k + 1 - n + m) F(m, n, k) 3 ------------------------------------------ - (-7 n + 6 + n + 6 m n - 7 m (k + 3) (k + 1 - n - m) 2 2 3 2 2 - n m - m n + m - 9 k n + 13 k + 4 m k n - 9 m k + 9 k - 3 n k 2 3 - 3 k m + 2 k ) F(m, n, k + 1)/((k + 3) (k + 2 - m - n) (k + 1 - n - m)) 2 2 (-n + n + 2 - 3 m n + m - m + k n + k + m k) F(m, n, k + 2) - ------------------------------------------------------------- (k + 3) (k + 2 - m - n) + F(m, n, k + 3) = 0 Proof: We will only do the first recurrence We have to prove that F(m,n) is annihilated by the operator, let's call it Q\ := (k + 1 - n + m) (k - 1 - n - m) 3 2 2 ------------------------------- - (6 - 7 n + n - 7 k + 6 k n - k n - n k (m + 3) (-m - 1 + n + k) 3 2 2 2 3 + k + 13 m - 9 m n - 9 m k + 4 m k n + 9 m - 3 m n - 3 m k + 2 m ) M/( (m + 3) (-m - 1 + n + k) (k - 2 + n - m)) 2 2 2 (n - n - 2 + 3 k n - k + k - m - m n - m k) M 3 - ------------------------------------------------ + M (m + 3) (k - 2 + n - m) or equivalenty 2 2 3 3 2 2 2 + 9 M m n - n k - k n + 4 k n - k - 6 M - n + 5 m + m + 6 M - 2 M + 4 m 3 2 2 3 2 + 2 M m k n + 5 M m k n - 4 M m k n + 3 M m n + 2 m k n + M n m 3 3 2 2 2 2 2 2 3 3 - 9 M m n - 2 M m n - M m n + 2 M n m - M m n - 2 m n + m M 2 3 3 2 2 2 3 2 3 2 3 + 6 m M + 11 m M - m M - 3 m M + M k m - 2 M m k - 9 M m k 3 2 2 2 2 2 3 2 2 2 + 6 M k n + 2 M k m - M m k - M m k - 2 m M + 5 M k n - 4 M k n 2 2 2 2 2 2 3 - 4 M n k - 9 m M + 3 M m k + 9 M m k + M n k + M k n - 9 M n 3 2 2 2 2 2 3 3 2 3 + 3 M n + M n + 2 M n - M n - 13 m M - M n - n m + 7 M n + n 2 2 2 2 3 2 3 - 2 n - m n - 2 m k - m k - 2 k + k - 6 M k n - k m + 7 M k - M k 2 2 2 2 3 3 3 2 + M k + 2 M k - M k - 9 M k + 3 M k We know, by the obvious combinatorics, that F(m,n,k) is annihilated by M N K - M N - M K - N K - 1 The sequence of successive commutators is [-2 K (k + 1 - n + m) (k - 1 - n - m) N - 2 K (k - 1 - n - m) (k - 2 + n - m) M 2 + (4 m n - 6 K - 2 n + 6 n + 2 K m k + 2 K m n - 4 - 6 K k n - 11 K m 2 2 2 2 2 + 3 K n + 3 k K - 5 K m + 3 k K + 3 K n - 2 m - 6 m + 2 k - 2 k) M N 2 2 2 2 + K (-2 m n + 2 k n + 6 - 6 m k - n - 3 n + 3 m + 9 m - 9 k + 3 k ) M 2 + (-6 m n + 3 K + 3 n - 9 n - 7 K m k - 7 K m n + 6 + 16 K k n - 5 K m 2 2 2 2 2 + 8 K n + 8 k K + 2 K m + 5 k K + 5 K n + 2 k n + 3 m + 9 m - k - 3 k 2 3 - 2 m k) M N + K (-m - 1 + n + k) (k + 2 n - m - 2) M + (-2 m n + 8 K 2 + n - 3 n + 3 K m k + 3 K m n + 2 - 11 K k n + 15 K m - 11 K n - 11 k K 2 2 2 2 2 3 + 2 K m - 5 k K - 5 K n + 3 k n + m + 3 m + 2 k - 4 k - 3 m k) M N 4 - K (-m - 1 + n + k) (k - 2 + n - m) M 4 + (-m - 1 + n + k) (k K - k + 6 K - n + K n + 2 + m + K m) M N, 2 2 8 K (k - 1 - n - m) M N - 8 K (k + 1 - n + m) M N 2 - 8 K (2 k K + k - m - 2 K m - 2 - K n - 2 K + n) M N 2 2 - 8 K (3 K n - k + 6 K + 3 k K - 2 m - 2 - K m + 2 n) M N 3 - 2 K (6 + 4 m - 3 K m - 4 k - 4 n + 9 K n + 3 K + 3 k K) M N 3 2 + 2 K (20 K n - 3 + 3 m - 8 K m + 20 k K + 34 K - 3 n - 9 k) M N 4 + 2 K (-4 K - 7 K m + 8 K n - k - n + m + 7 k K + 1) M N 4 2 - 2 K (11 k K + 11 K n - 8 k - 7 n - 5 K m + 4 + 7 m + 17 K) M N 2 5 - 4 K (-m - 1 + n + k) M N 5 2 + 2 K (-2 n + 2 m - K m + 2 k K + 2 - 2 k + 3 K + 2 K n) M N , 2 2 2 3 6 K M N (M - 2) (M N K - M N - M K - N K - 1)] As you can see, the last entry, 2 2 2 3 6 K M N (M - 2) (M N K - M N - M K - N K - 1), is a multiple of , M N K - M N - M K - N K - 1 The proof follows by backwards induction, after checking the boundary condit\ ions QED . ------------------------------------------------------ The whole thing took , 144.244, seconds of CPU time