# Rook walk and RecurrenceTable in Mathematica

This appears in a combinatorics book:

$a(m,n)=2 a(m,n-1)+2 a(m-1,n)-3 a(m-1,n-1)$

It is a recurrence equation for the number of rook walks from $(0,0)$ to $(m,n)$.

The initial conditions are:

$a(0,0)=1,\;a(0,1)=1,\;a(1,0)=1,\;a(1,1)=2$

The following is my implementation in Mathematica:

RecurrenceTable[{ a[m,n] == -3a[m-1,n-1] + 2a[m1,n] + 2a[m,n1],
a[0,0] == 1, a[0,1] == 1, a[1,0] == 1, a[1,1] == 2},
a, {m, 1, 10},{n, 1, 10}]


That will not work and just returns the function. I tried entering more initial conditions and changing the iterators to 0,10 and 2,10 etc.

I know I can do this with loops or recursive functions and memoization, but I am wondering what I am doing wrong with RecurrenceTable

• You may not have enough initial conditions. For example, how would a[1,2] be calculated? – bill s Oct 31 '13 at 18:12
• Plus, note that there aren't any m1 or n1 rather than m-1 and n-1. – Sektor Oct 31 '13 at 18:46
• Hi Nikola; That is an error the minus signs are gone it is supposed to be m-1 and n-1. Hi Bill; Why is it sufficient for Kenny's way and not RecurrenceTable? What conditions would you add? – bobbym Nov 1 '13 at 13:30

I cannot comment regarding RecurrenceTable. I presemt another way to generate the table. In this case for board of size, (m,n) run f[m+1,n+1] as you are countig from (0,0).

fun[m_, n_] := Module[{s, pos, ws},
s = SparseArray[{{1, 1} -> 1, {2, 1} -> 1, {1, 2} -> 1, {2, 2} ->
2, {j_, 1} /; j > 1 -> 2^(j - 2), {1, j_} /; j > 1 ->
2^(j - 2)}, {m, n}, "x"] // Normal;
pos = Position[s, "x"];
ws = {#, {# - {1, 0}, # - {0, 1}, # - {1, 1}}} & /@ pos;
(s = ReplacePart[s, #[] -> Extract[s, #[]].{2, 2, -3}]) & /@
ws;
s
]


This just uses your initial conditions and the boundary conditions of grid. Displaying result for (9,9) or 10 x 10 grid:

TableForm[fun[10, 10], TableHeadings -> {Range[0, 9], Range[0, 9]},
TableAlignments -> Right] I used

Clear[r]
r[0, 0] := 1
r[1, 0] := 1
r[0, 1] := 1
r[1, 1] := 2
r[m_?Negative, n_] := 0
r[m_, n_?Negative] := 0
r[m_?Negative, n_?Negative] := 0
r[m_, n_] := r[m, n] = 2 r[m - 1, n] + 2 r[m, n - 1] - 3 r[m - 1, n - 1]


and, for example,

With[{m = 7, n = 7},
Table[r[i, j], {i, 0, m - 1}, {j, 0, n - 1}] // TableForm]

• Hi Kenny; I know about that, I was wondering why using the same 4 initial conditions is not sufficient for RecurrenceTable? – bobbym Nov 1 '13 at 13:36
• But your recurrence table does not have the same initial conditions! KennyCoinago has three extra lines that explicitly assign the value 0 when the indices are negative. – bill s Nov 1 '13 at 14:00