# Pascal's Pyramid and Higher Dimensions

Pascal's Triangle is a familiar mathematical construct with many interesting properties. It is constructed by starting with a 1 on top, and generating the numbers in the next row from the sum of the number to the left and right in the row above (with implied 0's around the boundary):

    1
1 1
1 2 1
1 3 3 1
1 4 6 4 1


The Triangle can be expanded into N dimensions by using the same rules. For example, the 3-D Pascal's Triangle would be a pyramid with each row being a cross-section of the pyramid, i.e., a triangle. Each triangle's entry is generated by adding the three numbers in the "row" above forming a triangle directly above that entry. An example of the first four "rows" is shown below:

1

1
1 1

1
2 2
1 2 1

1
3 3
3 6 3
1 3 3 1


The 4-D Pascal's Triangle would have a 3-D Pascal's Triangle for the cross section, and so forth.

Your task is to write a program that takes as input the dimension of the Pascal's Triange, and a row index to display. The row index starts at 0, so row 0 is 1 for every dimension. Your program should abide by the following specifications:

• Take input N = dimension number, R = row number (0-based). The input can be either command-line arguments or from stdin. N >= 2, R >= 0
• Output the R'th row in the N-dimensional Pascal's Triangle, by displaying each row or triangle on a separate line as in the above example.
• The format can vary as long as it is 'triangle-like' and obvious where each row and entry in the row belongs with respect to other rows.

Here is some sample output (I believe these are correct):

>./pascal 2 5
1 5 10 10 5 1
>./pascal 3 4
1
4   4
6  12   6
4  12  12   4
1   4   6   4   1
>./pascal 4 3
1

3
3 3

3
6 6
3 6 3

1
3 3
3 6 3
1 3 3 1
>./pascal 5 2
1

2

2
2 2

1

2
2 2

1
2 2
1 2 1


Bonus: What is the significance of each "row" in an N-dimensional Pascal's triangle? I can think of at least three interesting facts.

• Attempt to partly answer to the bonus question: 1/ obvious, but each is an (N-1)-dimensional "triangular" slice; 2/ the N extremeties are always all "1". – asoundmove Jun 4 '11 at 4:39
• @asoundmove: All good ideas. Here's something to think about. What is the sum of all the numbers in one "row"? – mellamokb Jun 4 '11 at 4:42
• Further attempt: 3/ all N (N-2)-bases of the (N-1) slice of the N-dimensional pascal triangle are identical. – asoundmove Jun 4 '11 at 4:45
• Yet another one: 4/ all N (2D) vertices of the R-th row of the N-dimensional pascal triangle are the R-th row of the 2D pascal triangle. – asoundmove Jun 4 '11 at 4:47
• @ mellamokb: sum of all numbers: N^R – asoundmove Jun 4 '11 at 4:50

## Ruby, 181

def P(a)a.min<0?0:a.max<1?1:(b=a*1;t=k=0;b.map{b[k]-=1;k+=1;t+=P(b)};t)end
def d(n,a)print n>1?((0..a[-1]).map{|i|d(n-1,a+[i])};"\n"):"#{P(a)} "end
d(ARGV.to_i,[ARGV.to_i])


The first approach using the following recursive formula

P(...,-1,...) = 0
P(0,0,...,0) = 1
P(a,b,c,....) = P(a-1,b,c,...) + P(a-1,b-1,c,...) + P(a-1,b-1,c-1,...) + ...


and then printing row P(R,...).

The output is triangle-like - for pascal 4 2 it looks like

1

3
3 3

3
6 6
3 6 3

1
3 3
3 6 3
1 3 3 1

• @Peter adjusted formula and code to match starting index 0. – Howard Jun 4 '11 at 9:54