I came across an interesting paper by Christian Krattenthaler, called Advanced Determinant Calculus: A Complement, at http://arxiv.org/abs/math.CO/0503507 He evaluates a bunch of determinants, but in passing he generalizes one of Gosper's pi formulas, and gets into planar partitions and cutting up hexagons. He mentions en passant that there's an algorithm for computing the Nth *decimal* digit of pi without computing the first N-1 digits, by Fabrice Bellard, using Gosper's formula. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com on behalf of Richard Schroeppel Sent: Wed 5/18/2005 1:04 AM To: math-fun@mailman.xmission.com Subject: Re: [math-fun] hexagons, sequences, omino This is from Dylan Thurston. --Rich ----- Date: Wed, 18 May 2005 01:18:25 -0400 Reply-To: dpt@math.harvard.edu From: dpt@lotus.bostoncoop.net (Dylan Thurston) Subject: Re: [math-fun] hexagons, sequences, omino On Tue, May 17, 2005 at 08:50:52AM -0600, Schroeppel, Richard wrote:
Scott asks ...
Is there a nice general formula or a good approximation for the number of nondecreasing sequences in N^k, for integers N and k ?
For an exact formula: The 1D case is already answered, a quotient of factorials. Based on experiments done long long ago, at an Institute far far away, the 2D case seems to be a product of something like the 1D answers. Strict vs. non-strict vs. semi-strict perturbs the formulas slightly.
The 2D case is actually a well-known problem, called "plane partitions"; it's equivalent to counting lozenge tilings of a hexagon. (A 'lozenge' is a 60-120-60-120 rhombus obtained by gluing two triangles.) You have an rectangular array of numbers, non-decreasing in the rows and columns. Above each square, make a stack of cubes with height given by the number in that square. Add in two walls and the floor of the room. Tilt the whole construction and balance it on one corner; looking at it from the corner, you get a lozenge tiling of a hexagon. (Recall that if you look at a cube from a corner you see a hexagon.) There are many different symmetry classes of such tilings. Many have nice counts.
This also worked for rectangles, MxN. But I couldn't find a similar answer for the 3D case. I always figured there was a tie-in with linear and planar partitions having a nice generating function, while cubic partitions don't seem to have one.
Other people have noticed this too; I haven't heard a convincing explanation why this should be true. Peace, Dylan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun