2
$\begingroup$

The traditional Pascal's triangle grows by a width of 1 (N=1) each row. I have a modified Pascal's triangle that grows by a width of N each row. Where you sum the N+1 numbers symmetrically above a position in a generated row. The starting row contains (N+1) ones.

I am only concerned about when N is odd such that you can sum above easily. I haven't thought much about when N is even.

Example with N=3 and rows=4:

              1 1 1 1
           1 2 3 4 3 2 1
      1 3 6 10 12 12 10 6 3 1
1 4 10 20 31 40 44 40 31 20 10 4 1

Example with N=5 and rows=3:

               1 1 1 1 1 1
          1 2 3 4 5 6 5 4 3 2 1
1 3 6 10 15 21 25 27 27 25 21 15 10 6 3 1

This type of modified pascal's triangle is useful for calculating the probability of the sum of rolling R dice with (N+1) faces.

The only way I can figure out how to generate row R is generate row R-1 which requires me to generate the entire triangle from the top. In the traditional pascal's triangle there is a shortcut to generate a row in linear time. But I cannot seem to figure one out for this modified triangle.

If this is confusing or needs more context or another example just comment. :)

$\endgroup$
2
$\begingroup$

You have better start with the Pascal Triangle in the version having the leftmost elements aligned.
And you have better to consider the full triangle starting with $\binom{n}{m} =\binom {0}{0}$, and consider null all the elements to the left of the column $m=0$.

Then in this version, the triangle is constructed by summing two elements from the line immediately above,
starting from the element immediately above $\binom {n-1}{m}$ and proceeding to the left.
In your case instead you will sum $r$ elements, whether $r$ is odd or even.

You will discover that your elements are the (somebody call them r-nomials) coefficients of $$(1+x+x^2+ \cdots+ x^{r-1})^n=((1-x^r)/(1-x))^n$$.

Then take a look at e.g. this OEIS sequence.

After that take a look at this other related post , and to this one to get a closed sum expression for the numbers you are looking for.

$\endgroup$
0
$\begingroup$

You have each row of your "triangle" being the coefficients of $\,P^n\,$ where $\,P\,$ is the polynomial whose coefficients are the first row. In the usual Pascal's triangle, $\,P := 1 + x.\,$ In your first example with $\,N = 3\,$ the polynomial $\,P = 1 + x + x^2 + x^3.\,$ In this special case, $\, P = (1 - x^4) / (1 - x).\,$ Thus, $\, P^n = (1 - x^4)^n (1 - x)^{-n}.\,$ Using binomial coefficients we have $\, (1 - x^4)^n = \sum_{k=0}^n {n \choose k} x^{4k}.$ Also, $ (1 - x)^{-n} = \sum_{k=0}^\infty x^k {n-k+k \choose k}. \,$ Convolve these two power series to get your $\,P^n.\,$ Of course, there are the Multinomial coefficients but I don't see how they would be better to use in this case.

$\endgroup$

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.