Message Boards Message Boards

0
|
1987 Views
|
4 Replies
|
4 Total Likes
View groups...
Share
Share this post:

Binomial question

Posted 10 years ago
Hi.
I hope someone can help with this construction problem.

The arithmetic tetrahedron is defined to be a regular tetrahedron composed of layers of unit diameter spheres.The base triangle on which the unit spheres are stacked is the arithmetic, or Pascal triangle.The value of an element (sphere) in the second layer and higher, is the sum of the values of the 3 contacting elements in the layer below. Each element can be designated by 3 coordinates (Layer, Row, Column) (l,r,c).
An nth order arithmetic tetrahedron has n layers.    
ATn = L1 + L2 + L3 + ... + Ln.     Where L1 is the arithmetic triangle.
I have been able to generate the 1st and 2nd layers. 
The 1st layer 
Sum[Column[Table[Binomial[n,k],{n,0,6},{k,0,n}],Center],{n,6}]

The 2nd layer
Column[Table[Binomial[r,c]+Binomial[r+1,c]+Binomial[r+1,c+1],{r,0,9},{c,0,r}],Center]

Can anyone show how to write the code for the 3rd and subsequent layers?

Thanks

Den
POSTED BY: Den Roussel
4 Replies
Posted 10 years ago
Someone would have to make a much more convincing argument before I would believe there can be no single line simple closed form expression that gives the number at any particular position.

There is a whole field called 'generating functions' which can sometimes come up with the most surprising solutions to problems like this. Mathematica implements this using RSolve. If you could express the value at any position as the sum of the three values at the next lower positions along with the values of the base cases for the bottom layer then RSolve might find such an expression.

There is even a free online course underway right now on the topic of generating functions called Analytic Combinatorics over at coursera.org. The class has been going for a couple of weeks and is only six weeks long, so it might be a challenge, but if it isn't beyond you then it might be an interesting new way of looking at problems like this.

There is also a text called Concrete Mathematics written by Knuth and a couple of other authors that tries to introduce the subject. I had a difficult time trying to adapt to the style of that book, but you might do better. Surprisingly, there were a number of errors in earlier printings of that so if you consider buying an inexpensive used copy then you might try to get the latest printing you can find.

There is a text called Proofs that Really Count which tries to show that many times hard problems in combinatorics are perhaps only hard because we are trying to count up the numbers in an inconvenient way. He tries to show how you look for a different way of counting exactly the same number of items and which makes the problem much easier to do. I'd have to think a while before deciding whether that could help with this particular problem, but I would expect that it would apply.

I tried to give Simplify some assumptions about the domain of r and c and hoped that it might surprise me with a greatly simpler expression, but I was unsuccessful. Perhaps someone else would have more luck.

I did not find this as an example or exercise in Concrete Mathematics, but if you could swim in that text I suppose you could easily solve this problem.

I did not find this as a sequence in the OEIS, but finding multidimensional sequences in that is usually difficult for me.

Using FunctionExpand on things like Binomial[ r+2,c+1 ] / Binomial[ r,c ] I tried expressing coefficients in one layer as a rational times the Binomial of the previous layer. But I just can't see a nice simple factorial or binomial that relates a layer to the previous layer. Fumbling with RSolve didn't seem to help either. Perhaps someone else can do better.
POSTED BY: Bill Simpson
Posted 10 years ago
Thanks Bill.
Your code works very nicely. 
I have been scratching my head on this problem for many moons. I see now that it was wishful thinking to expect that any layer could be produced by a single line with appropriate modifications of the row and column indices. With your pattern, I can now push on with the tedious task of producing additional layers. Thanks again.
Den
POSTED BY: Den Roussel
Posted 10 years ago
 Column[Table[
   Binomial[n, k],
   {n, 0, 6}, {k, 0, n}], Center]
 
 Column[Table[
   Binomial[r, c] +
    Binomial[r + 1, c] +
    Binomial[r + 1, c + 1],
   {r, 0, 5}, {c, 0, r}], Center]

Column[Table[
  Binomial[r, c] + Binomial[r + 1, c] + Binomial[r + 1, c + 1] +
   Binomial[r + 1, c] + Binomial[r + 2, c] + Binomial[r + 2, c + 1] +
   Binomial[r + 1, c + 1] + Binomial[r + 2, c + 1] + Binomial[r + 2, c + 2],
  {r, 0, 4}, {c, 0, r}], Center]

Column[Table[
  (Binomial[r, c] + Binomial[r + 1, c] + Binomial[r + 1, c + 1] +
     Binomial[r + 1, c] + Binomial[r + 2, c] + Binomial[r + 2, c + 1] +
     Binomial[r + 1, c + 1] + Binomial[r + 2, c + 1] + Binomial[r + 2, c + 2]) +
   (Binomial[r + 1, c] + Binomial[r + 2, c] + Binomial[r + 2, c + 1] +
     Binomial[r + 2, c] + Binomial[r + 3, c] + Binomial[r + 3, c + 1] +
     Binomial[r + 2, c + 1] + Binomial[r + 3, c + 1] + Binomial[r + 3, c + 2]) +
   (Binomial[r + 1, c + 1] + Binomial[r + 2, c + 1] + Binomial[r + 2, c + 2] +
     Binomial[r + 2, c + 1] + Binomial[r + 3, c + 1] + Binomial[r + 3, c + 2] +
     Binomial[r + 2, c + 2] + Binomial[r + 3, c + 2] + Binomial[r + 3, c + 3]),
  {r, 0, 3}, {c, 0, r}], Center]

From that you may be able to see the pattern for how to generate all subsequent  layers.
POSTED BY: Bill Simpson
You are actually dealing with tetrahedral numbers. See the Wikipedia article http://en.wikipedia.org/wiki/Tetrahedral_number
POSTED BY: S M Blinder
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract