6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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". \$\endgroup\$ – asoundmove Jun 4 '11 at 4:39
  • \$\begingroup\$ @asoundmove: All good ideas. Here's something to think about. What is the sum of all the numbers in one "row"? \$\endgroup\$ – mellamokb Jun 4 '11 at 4:42
  • \$\begingroup\$ Further attempt: 3/ all N (N-2)-bases of the (N-1) slice of the N-dimensional pascal triangle are identical. \$\endgroup\$ – asoundmove Jun 4 '11 at 4:45
  • \$\begingroup\$ 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. \$\endgroup\$ – asoundmove Jun 4 '11 at 4:47
  • 1
    \$\begingroup\$ @ mellamokb: sum of all numbers: N^R \$\endgroup\$ – asoundmove Jun 4 '11 at 4:50
5
\$\begingroup\$

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[0].to_i,[ARGV[1].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 
\$\endgroup\$
  • \$\begingroup\$ @Peter adjusted formula and code to match starting index 0. \$\endgroup\$ – Howard Jun 4 '11 at 9:54

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.