• Xét lưới vuông \((n + 1) x (n + 1)\). Một quy tắc đi thõa mãn:
  • Xuất phát từ ô \((1, 1)\) đến ô \((n + 1, n + 1)\)
  • Mỗi bước đi chỉ được di chuyển đến ô kề cạnh bên phải
    hoặc bên dưới.
  • Không được di chuyển qua ranh giới là đường chéo nối
    đỉnh trái trên và phải dưới của lưới
  • Nếu quy định \(a[1, 1] = 0\) và \(a[i + 1, j] = a[i, j] + 1, a[i, j + 1] = a[i, j] – 1\).
  • Dễ thấy mỗi cách đi từ ô \((1, 1)\) đến ô \((n + 1, n + 1)\) là 1 dãy catalan tương ứng.
• Mảng qhđ:
  • \(F[i, j]\): số cách để đi từ ô \((i, j)\) đến ô \((n + 1, n + 1)\)
  • \(F[i, j] = F[i – 1, j] + F[i, j – 1]\) với \(F[n + 1, n + 1] := 1\);
• Giả sử tại ô \((u,v)\) ta di chuyển xuống ô phía dưới thì cách đi
  này sẽ có số thứ tự lớn hơn cách đi từ ô \((u,v)\) di chuyển sang
  ô bên phải (với \(u > v\)). Do đó ta chỉ quan tâm đến những ô
  (\(u, v\)) mà tại đó thự c hiện di chuyển xuống ô phía dưới, ta
  cộng vào \(s\) thêm \(F[u, v + 1]\).
• Kết quả số thứ tự của dãy catalan tương ứng với cách đi là
  \(s + 1\).

*** Cho số tìm dãy thì làm ngược lại.*