New: 201 pattern programs with tested code in C, C++, Java and Python Explore patterns

Hosoya’s Triangle

Read summary with AI tools

Hosoya’s triangle, sometimes called the Fibonacci triangle in Pascal form, is built from products of Fibonacci numbers. Its outer edges are the Fibonacci series, 1 1 2 3 5, and every row reads the same forwards and backwards.

Quick answer: Fill an array with the Fibonacci numbers, F(1) = F(2) = 1. Number j in row i (both counted from 0) is F(j + 1) × F(i − j + 1). Row 4, for example, is F(1)×F(5), F(2)×F(4), F(3)×F(3), F(4)×F(2) and F(5)×F(1), which gives 5 3 4 3 5.

This program is part of the Series Patterns collection.

Table of contents8 sections
  1. Hosoya’s Triangle output
  2. How the hosoya’s triangle works
  3. Hosoya’s Triangle in C
  4. Hosoya’s Triangle in C++
  5. Hosoya’s Triangle in Java
  6. Hosoya’s Triangle in Python
  7. Time and space complexity
  8. Frequently asked questions

Hosoya’s Triangle output

Output (n = 5):

  1
  1  1
  2  1  2
  3  2  2  3
  5  3  4  3  5
Hosoya's Triangle layout diagram, row by row (n = 5)
The numbers of the hosoya’s triangle laid out row by row (n = 5).

How the hosoya’s triangle works

The triangle was described by the chemist Haruo Hosoya. You can build it with a Pascal-like addition rule, but the product formula is easier to code: the left edge (j = 0) is F(1) × F(i + 1), which is just the Fibonacci series, and the right edge is the same by symmetry. Swapping j and i − j swaps the two factors, so each row is a palindrome.

  1. Fill fib[1] to fib[n + 1] with the Fibonacci numbers, starting 1, 1.
  2. Run the outer loop for i from 0 to n − 1.
  3. For j from 0 to i, print fib[j + 1] × fib[i − j + 1] three characters wide.
  4. Move to the next line.

Key takeaways

  • Every number is a product of two Fibonacci numbers.
  • The left and right edges are the Fibonacci series itself.
  • Each row is a palindrome, because swapping j and i − j swaps the two factors.
  • Computing the Fibonacci numbers once, before the loops, keeps the inner loop to a single multiplication.

Hosoya’s Triangle in C

#include <stdio.h>

int main(void) {
    int n = 5;
    int fib[20];
    fib[1] = fib[2] = 1;
    for (int k = 3; k <= n + 1; k++)
        fib[k] = fib[k - 1] + fib[k - 2];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++)
            printf("%3d", fib[j + 1] * fib[i - j + 1]);
        printf("\n");
    }
    return 0;
}

Hosoya’s Triangle in C++

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

int main() {
    int n = 5;
    vector<int> fib(n + 2, 1);
    for (int k = 3; k <= n + 1; k++)
        fib[k] = fib[k - 1] + fib[k - 2];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++)
            cout << setw(3) << fib[j + 1] * fib[i - j + 1];
        cout << endl;
    }
    return 0;
}

Hosoya’s Triangle in Java

public class HosoyasTriangle {
    public static void main(String[] args) {
        int n = 5;
        int[] fib = new int[n + 2];
        fib[1] = fib[2] = 1;
        for (int k = 3; k <= n + 1; k++)
            fib[k] = fib[k - 1] + fib[k - 2];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++)
                System.out.printf("%3d", fib[j + 1] * fib[i - j + 1]);
            System.out.println();
        }
    }
}

Hosoya’s Triangle in Python

n = 5
fib = [0, 1, 1]
for k in range(3, n + 2):
    fib.append(fib[k - 1] + fib[k - 2])

for i in range(n):
    for j in range(i + 1):
        print(f"{fib[j + 1] * fib[i - j + 1]:3d}", end="")
    print()

Time and space complexity

Building the Fibonacci array takes O(n) time and memory, and printing the triangle takes O(n²) time.

Frequently asked questions

Is there an addition rule like Pascal’s triangle?

Yes. Away from the edges, each number equals the sum of the two numbers above it on the same side, two rows up and one row up: H(i, j) = H(i − 1, j) + H(i − 2, j). The product formula gives the same values and is simpler to write.

Why is it called a Fibonacci triangle?

Because its edges are the Fibonacci series and every entry is made from Fibonacci numbers. Do not mix it up with the Fibonacci triangle on this site, which just prints the series row by row.

How large can n get?

The biggest number in row i is on the edge, F(i + 1), so overflow comes from the Fibonacci numbers themselves. An int is safe up to row 45; use a 64-bit type for more.

Authored by

Ghanendra Yadav runs Pattern Programs from Bangalore, India. The site started in 2020 to help students practise loops and logic through pattern programs in C, C++, Java and Python. Every program published here is compiled and run before it goes live, and the output shown is the real output.

Latest articles

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.