Skip to main content

Hosoya’s Triangle

By

The Fibonnaci triangle or Hosoya’s triangle is a triangular arrangement of numbers based on Fibonacci numbers. Each number is the sum of two numbers above in either the left diagonal or the right diagonal.


function Hosoya(n, m)
{
    if ((n == 0 && m == 0) ||
        (n == 1 && m == 0) ||
        (n == 1 && m == 1) ||
        (n == 2 && m == 1))
        return 1;

    if (n > m)
        return Hosoya(n - 1, m)
               + Hosoya(n - 2, m);

    else if (m == n)
        return Hosoya(n - 1, m - 1)
               + Hosoya(n - 2, m - 2);

    else
        return 0;
}