13
$\begingroup$

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$.

$\endgroup$
13
$\begingroup$

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 x^i \right)^n$$

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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Marc van Leeuwen Sep 19 '14 at 11:45
6
$\begingroup$

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 -> ""]

enter image description here

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 *)
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – David Richerby Sep 19 '14 at 10:36
  • 2
    $\begingroup$ @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. $\endgroup$ – Mark McClure Sep 19 '14 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.