# Is there a name for this kind of "Pascal's Triangle"?

I've been working on a problem and came across an interesting triangle that functions almost exactly like a Pascal Triangle. I'd like to see if I am able to find more about the properties of these triangles. I've found information on Pascal's simplexes, but that is not what this is.

Pascal's Triangle can be constructed by the fact that each cell is the sum of the $2$ above it. But I'm interested in the resulting triangles when you sum the above $3$ cells, $4$ cells, or more.

$n=3$:

$$1\\ 1\ \ 1\ \ 1\\ 1\ \ 2\ \ 3\ \ 2\ \ 1\\ 1\ \ 3\ \ 6\ \ 7\ \ 6\ \ 3\ \ 1\\$$

$n=5$:

$$1\\ 1\ \ \ 1\ \ \ 1\ \ \ 1\ \ \ 1\\ 1\ \ \ 2\ \ \ 3\ \ \ 4\ \ \ 5\ \ \ 4\ \ \ 3\ \ \ 2\ \ \ 1\\ 1\ \ \ 3\ \ \ 6\ \ 10\ 15\ 18\ 19\ 18\ 15\ 10\ \ 6\ \ \ 3\ \ \ 1$$

In particular what I'd like to know is how to generate an arbitrary row, like the $20$th row when $n=11$.

They don't have names to my knowledge, but they're easy to calculate. For example, you can find the third row of the order-3 triangle by expanding:

$$(1 + x + x^2)^3 = 1 + 3x + 6x^2 + 7x^3 + 6x^4 + 3x^5 + x^6$$

In general, the $$n$$th row of the order-$$k$$ triangle is given by expanding

$$\left( \sum_{i=0}^{k-1} x^i \right)^n$$

and reading off the coefficients. The proof (it's not hard) is left as an exercise.

• I think it should be $$\left( \sum_{i=0}^{k-1} x^i \right)^n$$, if the order is $k$, then the polynomial is of order $k-1$. Nov 25, 2020 at 11:24
• You are correct! Updated, thanks. Nov 25, 2020 at 22:59

The version with $n=3$ is called the "trinomial triangle"; here is its Wikipedia page. Here is a previous math.SE question about it.

In general, these triangles are calculable via multinomial coefficients. The expression $$\binom{n}{k_1,\;k_2,\;\ldots,\;k_m}=\frac{n!}{k_1!k_2!\cdots k_m!}$$ is the coefficient of $a_1^{k_1}a_2^{k_2}\cdots a_m^{k_m}$ in the expansion of $$(a_1+a_2+\cdots+a_m)^n$$ where $k_1+k_2+\cdots+k_m=n$. Then substitute $a_i=x^{i-1}$, and collect the appropriate terms.

• Having to collect appropriate terms is kind of opposite to the purpose of having (formulas for) binomial/multinomial coefficients. After all $\binom nk$ can be found by setting $a=1+x$ in $a^n$ and collecting terms contributing to $x^k$. Sep 19, 2014 at 11:45

Though I rather like the previous two answers, this configuration can also be thought of as a cellular automaton. Thus, your $n=3$ version can be computed in Mathematica like so:

radius = 1;
duration = 9;
ca = CellularAutomaton[{Total[##] &, {}, radius}, {{1}, 0}, duration];
Grid[ca /. 0 -> ""]


Simply increase radius and/or duration as desired. We can generate your 20th row for $n=11$ and check it against the first, accepted answer as follows:

ca = First[CellularAutomaton[{Total[##] &, {}, 5}, {{1}, 0}, {{20}}]];
nom = CoefficientList[Expand[Sum[x^i, {i, 0, 10}]^20], x];
ca == nom
(* Out: True *)

• Sure, the sequence is computable so it's obviously expressible in one of the Turing-complete cellular automaton models and possibly also in some CA models that aren't Turing-complete. But what does that buy you? The CA is much harder to analyze than the original sequence. What advantages do you expect to come from building this sledgehammer factory? Sep 19, 2014 at 10:36
• @DavidRicherby Well, the question asks us to place the triangle in some broader context, which the answer certainly does. Sounds like your problem is not at all with this answer but with the "sledgehammer" of cellular automata or, possibly, Mathematica - I don't know which. Sep 19, 2014 at 10:56