Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer

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]
share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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