Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was quite impressed by a beautiful proof1 of the formula for n'th triangular number — it's kind of a bijective proof built on the top of geometric summation idea.

Question: does this argument generalize to higher dimensions? i.e. can someone prove the formula for n-th «k-dimensional simplex number» this way?

the proof

For example, the statement for k=3 is that n-th pyramidal number is $\binom{n+2}{3}$.

(One obvious fallback would be observing that any ball in the pyramid is characterized by its coordinates2, i.e. balls are counted by a negative binomial coefficient — which is exactly the desired result. That's a good proof, but needless to say, that's not the proof I'm looking for.)

1 original post by Mariano Suárez-Alvarez, cited by Vaughn Climenhaga

2 k-simplex is the subset $x_0+\dots+x_k=1$, $x_i\ge0$ in $\mathbb{R}^{k+1}$, and n-th k-simplex number is the number of non-negative integer solutions of $x_0+\dots+x_k=n$

share|improve this question
    
What is wrong with that proof? –  Casebash Aug 14 '10 at 11:34
    
@Casebash it doesn't generalize the proof I want to generalize (i.e. for k=2 it gives different proof for the formula for n-th triangular number) — so it doesn't answer the question –  Grigory M Aug 14 '10 at 11:45
    
BTW, how do you define coordinates on the pyramid? I know how it works for a triangle –  Casebash Aug 15 '10 at 0:30
    
It is fine now –  Casebash Aug 15 '10 at 12:20
add comment

1 Answer 1

up vote 4 down vote accepted

Place the balls so that the corners of the pyramid have coordinates (1,1,1), (n,1,1), (1,n,1), (1,1,n). Then for the ball at (x,y,z) we see that (x,x+y,x+y+z) is an ordered triple of distinct numbers between 1 and n+2 inclusive. There are $\binom{n+2}{3}$ such triples, and they are clearly in one-to-one correspondence with the balls. Geometrically, this corresponds to drawing planes x=constant, x+y=constant, and x+y+z=constant through a given ball, and seeing where these planes intersect the x axis.

(To compare with the case $k=2$, "straighten" the picture above into a right triangle. Then the diagonal lines become lines x=constant and x+y=constant, and the bottom row of balls (the blue ones) can be identified with the points where these lines intersect the x axis.)

This also works in higher dimensions, giving $\binom{n+k-1}{k}$.

Whether this proof really is any different from the one you suggested in the question can of course be debated...

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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