3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ You may not have enough initial conditions. For example, how would a[1,2] be calculated? $\endgroup$ – bill s Oct 31 '13 at 18:12
  • $\begingroup$ Plus, note that there aren't any m1 or n1 rather than m-1 and n-1. $\endgroup$ – Sektor Oct 31 '13 at 18:46
  • $\begingroup$ 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? $\endgroup$ – bobbym Nov 1 '13 at 13:30
2
$\begingroup$

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, #[[1]] -> Extract[s, #[[2]]].{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]

enter image description here

$\endgroup$
3
$\begingroup$

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]
$\endgroup$
  • $\begingroup$ Hi Kenny; I know about that, I was wondering why using the same 4 initial conditions is not sufficient for RecurrenceTable? $\endgroup$ – bobbym Nov 1 '13 at 13:36
  • 1
    $\begingroup$ 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. $\endgroup$ – bill s Nov 1 '13 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.