Треугольник Паскаля

Конструкция треугольника Паскаля широко известна. В виде треугольной таблицы записываются биномиальные коэффициенты. Для удобства будем делать это следующим образом:

package ru.xaoc.fractalworld.pascaltriangle;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Image;
import java.awt.geom.Rectangle2D;
import java.awt.image.BufferedImage;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class Main {
    public static Image draw(int[][] A) {
        int r = A.length;
        int s = A[0].length;
        BufferedImage image = 
		new BufferedImage(s, r, BufferedImage.TYPE_INT_RGB);
        Graphics2D graphics = image.createGraphics();
        graphics.setColor(Color.WHITE);
        graphics.fill(new Rectangle2D.Double(0, 0, s, r));
        graphics.setColor(Color.BLACK);
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < s; ++j) {
                if (A[i][j] != 0) {
                    graphics.fillRect(j, i, 1, 1);
                }
            }
        }
        return image;
    }

    public static int[][] generatePascalTriangle(int n, int m) {
        int[][] T = new int[n][n];
        for (int i = 0; i < n; ++i) {
            T[i][0] = 1;
            for (int j = 1; j <= i; ++j) {
                T[i][j] = (T[i - 1][j - 1] + T[i - 1][j]) % m;
            }
            for (int j = i + 1; j < n; ++j) {
                T[i][j] = 0;
            }
        }
        return T;
    }

    public static Image drawSierpinskiTriangle(int n, int m) {
        return draw(generatePascalTriangle(n, m));
    }

    public static Image image;

    public static void main(String[] args) {
        image = drawSierpinskiTriangle(512, 2);

        int width = image.getWidth(null);
        int height = image.getHeight(null);
        JFrame frame = new JFrame();
        frame.addNotify();
        frame.setSize(frame.getInsets().left +
                frame.getInsets().right + width,
                frame.getInsets().top +
                frame.getInsets().bottom + height);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        frame.add(new JPanel() {
            @Override
            public void paintComponent(Graphics g) {
                Graphics2D G = (Graphics2D) g;
                if (image != null) {
                    G.drawImage(image, 0, 0, null);
                }
            }
        });
        frame.setVisible(true);
    }
}

Можно также вместо 2, рассматривать треугольник Паскаля по модулю других чисел, ниже приведены случаи для 3, 4, 5 и 8.

Теперь построим с помощью подобной процедуры ковёр Серпинского. Для этого будем вычислять по формуле , положив . Все вычисления производятся по модулю 3.

public static int[][] generateSierpinskiCarpet(int n) {
    int[][] T = new int[n + 1][n + 1];
    for (int j = 0; j < n + 1; ++j) {
        T[0][j] = T[j][0] = 0;
    }
    T[1][1] = 1;

    for (int i = 1; i < n + 1; ++i) {
        for (int j = 1; j < n + 1; ++j) {
            if (i == 1 && j == 1) {
                continue;
            }
            T[i][j] = (T[i - 1][j]  + T[i - 1][j - 1] + T[i][j - 1]) % 3;
        }
    }
    return T;
}

Обобщим. Пусть задана квадратная матрица размера . Будем в таком же порядке вычислять по формуле

public static int[][] generateField(int[][] a, int n, int m) {
    int w = a.length;
    int[][] T = new int[n + w - 1][n + w - 1];
    for (int i = 0; i < n + w - 1; ++i) {
        for (int j = 0; j < n + w - 1; ++j) {
            T[i][j] = 0;
        }
    }

    T[w - 1][w - 1] = 1;

    for (int i = w - 1; i < n + w - 1; ++i) {
        for (int j = w - 1; j < n + w - 1; ++j) {
            for (int r = 0; r < w; ++r) {
                for (int s = 0; s < w; ++s) {
                    T[i][j] += a[r][s] * T[i - w + 1 + r][j - w + 1 + s];
                }
            }
            T[i][j] %= m;
        }
    }
    return T;
}

При очевидно, получится ковёр Серпинского, а при получится треугольник Серпинского.

Смотрите также:

• Треугольник Серпинского,
• ковёр Серпинского,
• построение треугольника Серпинского с помощью матриц Адамара,
• построение фракталов с помощью произведения Кронекера,
• губка Менгера и пирамида Серпинского.

Ссылки:

• Sierpiński Sieve from Wolfram Mathworld.
• 3 ways of Creating the Sierpinski Carpet .
• A Second Level Sierpinski from A Pascal's Triangle Sum Modulo Program .
• Pascal's Triangle from Wolfram Mathworld.
• Elementary Cellular Automaton from Wolfram Mathworld.
• М. Шредер, Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая. Из-во РХД, Ижевск, 2001. 486--488.