Solve g(n) = sum(j=0 to n-2) { sum(k=1 to n-j-2) { g(n-j-k-1) } }

g(n) = sum(j=0 to n-2) { g(n-j-2) + g(n-j-3) + g(n-j-4) + ... }

g(n) = g(n-2) + 2*g(n-3) + 3*g(n-4) + ...

So g(n-1) = g(n-3) + 2*g(n-4) + 3*g(n-5) + ...

Subtracting yields:

g(n) - g(n-1) = g(n-2) + g(n-3) + g(n-4) + ...
g(n) = g(n-1) + g(n-2) + g(n-3) + g(n-4) + ...

With g(1) = g(2) = 1, this reduces to

g(n) = f(3,n) = 2^(n-2) for n >= 2.

Thus f(3,1)=1, f(3,2)=1, f(3,3)=2, f(3,4)=4, f(3,5)=8, etc.

What about f(m,n)?

Note: the outer summand range in the previous two posts should read:
sum(j=0 to n-1).

I assume that there is no simple solution for the n>4 and m>4. The equation gets so difficult and large that brute force or even monte carlo (for an esimate) is faster.

I know a similar problem where all paths from 1,1 to n,n in a n*n Square need to be counted (not necessary to visit all squares; but every square can be visited at most once.
Here already the case n=10 has so many solutions that they could not be counted in reasonable time (Maybe the database of interger Sequences has a solution for small n).

Thanks. I did some research:

(1) Wrote a back-tracking counting program to find and count
all snail-paths from (1,1) to (m,n).

Some numbers:
3x1-> 1
3x2-> 1
3x3-> 2 /// 5x3-> 8
3x4-> 4 /// 5x4-> 20 /// 7x4->111 /// 9x4->624?
3x5-> 8 /// 5x5-> 104 /// 7x5->1670 /// 9x5->>28417
3x6-> 16 /// 5x6-> 378 /// 7x6->10204 /// 9x6->286395
3x7-> 32 /// 5x7->1670 /// 7x7->111712 /// 9x7->8261289
3x8-> 64 /// 5x8->6706 /// 7x8->851073 /// 9x8->114243216
3x9->128 /// 5x9->28417 /// 7x9->8261289

(2) Found second column in "integer sequences" site list,
but NOT the higher columns.
They're "Hamiltonian simple rook paths in rectangular 5xn grid".

(3) The m x n problem is NOT completely solved. There is an interesting
refererence to a paper by "Collins and Klompart" (Google it).