I was playing a bit with Pascal's triangle and more or less by accident, I found the trinomial triangle. Knowing that marking the odd numbers in Pascal's triangle creates an approximation of Sierpinski's triangle fractal, I tried doing the same for the trinomial triangle and was surprised by a similar pattern. Does this pattern have a name? I can't imagine it has never been seen before.
I tried generating a large fractal using Python.
The pattern somewhat resembles Sierpinski's triangle, but it's visibly different. I browsed the internet and barely found anything about the pattern. I did find some paper with a vague description of how the pattern is created from the trinomial triangle (see this page), but not what it is called or what relations it has to the Sierpinski triangle.
I drew an inaccurate, but smoother image of the triangle in inkscape.
Obviously, it has triangular holes, yet the black surfaces are not always triangles and are sometimes constructed from two overlapping triangles instead. I'm very curious now and would love to learn more about this. Where could I find more information about this pattern?
Edit: the pattern goes on
I confirmed the triangular pattern appears according to cellular automaton Rule 150. But once I start extending this into adding up more than 3 cells above each lower cell I get back similar triangular patterns once I mark all odd numbers in the triangles constructed by that.
To explain it more formally I'm assuming all rows of each numeric triangle to be left-justified. In the case of Pascal's triangle that looks like this (the definition of Pascal's triangle implies that any empty cell outside of the triangle should be 0):
k 1 2 3 4 5
n
1 1 0 0 0 0
2 1 1 0 0 0
3 1 2 1 0 0
4 1 3 3 1 0
5 1 4 6 4 1
This creates a grid where where each cell is labeled with a pair of two numbers $(k, n)$ (given that $k \in \mathbb{N}$ and $n \in \mathbb{N}$), and we compute the number in each cell as $n \choose k$ (binomial coefficient). One definition we know is ${n \choose k} = {{n-1} \choose {k-1}} + {{n-1} \choose k}$, and we obviously see that definition coming back in the number grid.
For the trinomial triangle we replace the binomial coefficent with the trinomial coefficient: ${n \choose k}_2 = {{n-1} \choose k-2}_2 + {{n-1} \choose k-1}_2 + {{n-1} \choose k}_2$. We now get
k 1 2 3 4 5 6 7 8
n
1 1 0 0 0 0 0 0 0
2 1 1 1 0 0 0 0 0
3 1 2 3 2 1 0 0 0
4 1 3 6 7 6 3 1 0
We can generalize the definition of Pascal's triangle and the trinomial triangle into one general definition:
$$ D_l(n, k)= \begin{cases} 0, & \text{if } k>(n-1)(l-1)+1 \text{ or } k<0 \\ 1, & \text{if } n = 1 \\ \sum \limits_{i=0}^{l-1} D_l(n - 1, k - i), & \text{otherwise} \end{cases} $$
This function $D_l$, given $l \geq 2$, takes the pair $(n, k)$, and gives back one number for the cell $(n, k)$. The parameter $l$ is important here: for $l=2$ we get the function for Pascal's triangle: $$ D_2(n, k)= \begin{cases} 0, & \text{if } k > n \text{ or } k < 0 \\ 1, & \text{if } n = 1 \\ D_2(n - 1, k) + D_2(n - 1, k - 1), & \text{otherwise} \end{cases} \\ = {{n - 1} \choose {k - 1}} + {{n - 1} \choose {k}} = {{n} \choose {k}} $$ For the trinomial triangle, we take $l = 3$: $$ D_3(n, k)= \begin{cases} 0, & \text{if } k > 2n-1 \text{ or } k < 0 \\ 1, & \text{if } n = 1 \\ D_3(n-1, k) + D_3(n-1, k-1) + D_3(n-1, k-2), & \text{otherwise} \end{cases} \\ = {{n - 1} \choose {k - 2}}_2 + {{n - 1} \choose {k - 1}}_2 + {{n - 1} \choose {k}} = {{n} \choose {k}}_2 $$
The general function $D_l$ basically defines a numeric triangle in 3 simple rules:
- the first row is one single 1;
- any number outside the 'boundaries' of the row is a 0;
- and any number within a row is the sum of the cell above, and all $l-1$ cells left to that (above) cell.
(You could say that $D_l(n, k) = {n \choose k}_{l-1}$.)
Back to the fractal: instead of filling the grid with numbers, we now color the cells with an odd number, and we'll get a triangle of colored and not-colored cells. Aligning the rows centered gives the sierpinski triangle for $l=2$ and the cellular automaton rule 150 for $l=3$.
From here on, I extended to $l=4$, and found that the same procedure gives the sierpinski triangle again. However, $l=5$ again yields a unique repetitive pattern of triangles:
For $l=6$ and $l=7$ similar, but new pattern comes back, while for $l=8$ I find the sierpinski triangle again:
(to un-stretch the image a bit I printed every row twice).
I see a certain pattern here. With $l=2^x$, somehow the sierpinski triangle comes back, while with $l≠2^x$ the patterns of odd numbers form unique fractals shaped in similar ways as the sierpinski triangle. For every triangle I see that the upper half is a copy of itself (which is not entirely surprising knowing how the triangles are constructed).
I certainly want to know more: Why does this happen? What could it be used for? Why do we see the Sierpinski triangle for $l=2^x$? And why do the triangles arrange in specifically these ways?