develooper Front page | perl.golf | Postings from July 2002

Re: pascal's hyper-pyramid... a wee bit OT (Was: more minigolf)

From:
matthew wickline
Date:
July 11, 2002 16:45
Subject:
Re: pascal's hyper-pyramid... a wee bit OT (Was: more minigolf)
Message ID:
3D2E187B.F2517540@wickline.org
Phil Carmody <thefatphil@yahoo.co.uk> wrote:
> (1+1)^0 =     1
> (1+1)^1 =    1+1
> (1+1)^2 =   1+2+1
> (1+1)^3 =  1+3+3+1
> (1+1)^4 = 1+4+6+4+1


As an interesting aside, pascal's (bottomless) triangle is actually a
triangular (bottomless) face of an infinitely-dimensioned hyper-pyramid.
To see how this works, you can back up to a lower dimension and work
forward from there.

In the case above, we're looking at a two-term polynomial raised to
various powers. Let's consider what happens when you raise a single-term
polynomial to various powers:

    monomial expansion => just the coeficients
    x^0 = 1x^0         =>  1
    x^1 = 1x^1         =>  1
    x^2 = 1x^2         =>  1
    x^3 = 1x^3         =>  1
    x^4 = 1x^4         =>  1

We could expand that series of ones forever. It's a "bottomless line" (a
ray) of ones. Now imagine that the bottomless line of ones is the edge
of pascal's bottomless triangle from up above. It is. Pascal's triangle
is hiding behind that edge, burried inside your monitor. Just mentally
rotate it out from behind the edge, and you'll have pascal's triangle as
shown above.

Pascal's triangle shows the coeficients which result from the expansion
of polynomials of two terms. The resulting structure is two-dimensional.
Looking back at monomials, we got a one-dimensional structure from our
coeficients, and that one-dimensional structure was a subset of the
two-dimensional structure.

If we look at three-term polynomials, will we see a three-dimensional
structure (a bottomless pyramid), of which pascal's triangle is merely
an outer face? Yes. The coeficients you get from expanding a trinomial
can be very handily represented in a triangle. If stack up that infinite
series of triangles to obtain a bottomless pyramid, then each of the
three outer faces of that pyramid will show pascal's triangle. Below are
the first half-dozen layers of that pryamid. Note that the sequence of
rows from pascal's triangle form the three outer edges of the sequence
of triangular layers:

1    (x+y+z)^0    edge => 1
~
  1
 1 1    (x+y+z)^1    edge => 1 1
 ~~~
    1   
   2 2    (x+y+z)^2    edge => 1 2 1
  1 2 1 
  ~~~~~
        1    
       3 3   
      3 6 3    (x+y+z)^3    edge => 1 3 3 1
     1 3 3 1 
     ~~~~~~~
             1         
            4  4       
           6 12  6    (x+y+z)^4    edge => 1  4  6  4  1 
          4 12 12  4 
         1  4  6  4  1 
         ~~~~~~~~~~~~~
                       1           
                      5  5         
                    10 20 10       
                   10 30 30 10    (x+y+z)^5    edge => 1  5 10 10  5  1
                   5 20 30 20  5   
                  1  5 10 10  5  1 
                  ~~~~~~~~~~~~~~~~

If you inspect each layer of the triangle, you'll note some interesting
symetries (for example, each three-element row is a multiple of the
1-2-1 three-element row in the original pascal's triangle) and that the
formation rule of addition works in this case too, except that instead
of filling a grid on graph paper, you're filling space tesselated with
cubes (rotated to be point-up). You add the values across the three
upper faces instead of the values across the two upper edges.

Enough of that.

The same interesting patterns apply in more mind-bending dimensions.

If you expand a quad-nomial (polynomial with four terms), the resulting
coeficients fit quite tidily into a pyramid. This infinite series of
pyramids forms a bottomless hyper-pyramid, of which the above bottomless
3-d pyramid is a mere "outer volume".

(w+x+y+z)^0 =>
1
~

(w+x+y+z)^1 =>
     1  
1 ; 1 1 
~~~~~~~

(w+x+y+z)^2 =>
            1   
     2     2 2  
1 ; 2 2 ; 1 2 1 
~~~~~~~~~~~~~~~

(w+x+y+z)^3 =>
                     1    
            3       3 3   
     3     6 6     3 6 3  
1 ; 3 3 ; 3 6 3 ; 1 3 3 1 
~~~~~~~~~~~~~~~~~~~~~~~~~

(w+x+y+z)^4 =>
                                       1         
                         4            4  4       
              6        12 12         6 12  6     
      4     12 12     12 24 12      4 12 12  4   
 1 ; 4  4 ; 6 12  6 ; 4 12 12  4 ; 1  4  6  4  1 
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(w+x+y+z)^5 =>
                                                             1           
                                           5               5  5         
                            10           20 20           10 20 10       
               10         30 30        30 60 30        10 30 30 10     
      5      20 20      30 60 30     20 60 60 20      5 20 30 20  5   
 1 ; 5  5 ; 10 20 10; 10 30 30 10 ; 5 20 30 20  5 ; 1  5 10 10  5  1 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Want more?

Here's the coeficients you get from raising a five-term polynomial to
the sixth power. The coeficients fit very handily into a 4D
hyperpyramid, and this 4D layer is just one slice of the botomless 5D
structure which contains all coeficients for expanding five-term polynomials.

coeficients from (a+b+c+d+e)^6
    http://wickline.org/polynomial_expansion/?6,5


You can continue this for polynomials of N terms expanding with
coeficients well-represented in an N-1 dimensional hyperpyramid, an
infinite series of which stack up to form an N-dimensional hyperpyramid
of which pascal's triangle is merely the outer edge. Pascal's triangle
is really just a superficial view of an infinitely dimensioned botomless hyperpyramid.


Yes, that's all off-topic. In a (vain?) attempt to get back on topic,
that CGI generates the set of exponents for a specified exponent and
polynomial term count. It's in perl. Since algorithms are a significant
portion of the battle, I won't tell you how it generates the numbers or
lays them out.

As a golf challenge, can you get something that will create roughly
equivilant output? Triangles should have roughly the same shape. Note
how in the 6,5 example above, the numbers are all padded to accomodate
the widest number so that the pyramidal shape is maintained. ...but
minor whitespace issues are no big deal (how you justify the number
within the space provided, whether you make a little bit "wider"
structure by adding an additional space between horizontally adjacent
triangles, etc)

The idea is to get the numbers right, and the overall visual effect
which emphasizes the hyper-pyramidal structure and symetries.

How many characters does it take? Less than 500?

-matt



nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About