Plane (but not plain) Partitions
Wouter Meeussen
eu000949 at pophost.eunet.be
Wed May 26 01:47:29 CEST 1999
Plane Partitions:
(see my earlier mails on "safe pilings")
I send this to seqfan in the hope of being corrected, checked, admonished or
extended. I know it's a long mail. Sorry.
Maybe R.P. Stanley should be invited to give his blessing.
(* intro *)
if we look at the plane partitions as cubes piled in a corner (x,y,z
coordinates,
first octant), with the proviso that the stack height should either remain
constant or
decrease away from the corner, than they can be classified as regular 3D
objects.
The following symmetries can occur:
C1 = no symmetry
Cs = one symmetry plane (mirror plane)
C3 = a threefold axis only
C3v= a threefold axis is the intersection of three mirror planes.
(* sequences *)
the number of plane partitions of n elements for each of the 4 cases is:
a=={0,0,0,1,2,5,11,21,39,73,129,226,388,659,1100,1821,2976,4828,7754,12370,
19574,30789,48097,74725,115410,177366,271159,412665,625098,942932,1416362,
2119282,3158840,4691431}
== symmetry C1 ( only the Identity operation)
s=={0,1,2,2,4,6,6,11,16,20,28,41,51,70,93,122,158,211,266,350,450,577,730,948,
1186,1510,1901,2408,2999,3790,4703,5898,7310,9111}
== symmetry Cs ( 1 symmetry plane)
r={0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,2,2,0,3,3,0,5,6,0,7,9,0,11,16,1,14}
== symmetry C3 ( a three-fold axis but no mirror plane)
b={1,0,0,1,0,0,2,1,0,2,1,0,2,1,0,3,2,0,4,4,0,4,5,0,5,7,1,6,9,1,6,11,1,8}
== symmetry C3v ( a three-fold axis plus 3 mirror planes)
============================================================================
=====
combining these, we can reconstruct the number of plane partitions under
different sets
of restrictions:
nosym == no symmetry restrictions : every plane partition counted once
rotasym == the pilings are "lifted out of the corner", and "rotamers" are
counted only once.
this looks only at the piling itself, not discriminating the
different rotated forms.
mirrsym == this considers mirror images to be equivalent, and counts them as
one.
bothsym == this considers both rotation and mirroring of a piling to be
equivalent states,
and counts them all as appearances of one essentially different form.
the link between both counting strategies is given by :
nosym == 3s+6a+2r +b ,
rotasym == s+2a+2r +b ,
mirrsym == 2s+3a+ r +b ,
bothsym == s+ a+ r +b
as can easily be obtained from the definitions above.
The second way of counting gives:
nosym=
{1,3,6,13,24,48,86,160,282,500,859,1479,2485,4167,6879,11297,18334,
29601,47330,75278,118794,186475,290783,451194,696033,1068745,1632658,
2483234,3759612,5668963,8512309,12733429,18974973,28175955};
rotasym=
{1,1,2,5,8,16,30,54,94,168,287,493,831,1391,2293,3769,6114,9867,15782,
25098,39598,62165,96935,150398,232021,356261,544220,827758,1253222,
1889655,2837455,4244505,6324993,9392009}
mirrsym=
{1,2,4,8,14,27,47,86,149,261,444,760,1269,2119,3486,5711,9247,14906,23800,
37816,59622,93528,145759,226071,348612,535131,817280,1242824,1881310,
2836377,4258509,6369669,9491142,14092537}
bothsym=
{1,1,2,4,6,11,19,33,55,95,158,267,442,731,1193,1947,3137,5039,8026,12726,
20024,31373,48835,75673,116606,178889,273061,415086,628115,946723,1421082,
2125207,3166152,4700564}
(* comparisons to stuff in EIS *)
P. A. MacMahon in A000784 counts the Cs pilings (my "s" );
and in A000785 he counts the asymmetric pilings (my "a") :
ID Number: A000784 (Formerly M0322 and N0119)
Sequence: 0,1,2,2,4,6,6,11,16,20,28,41,51,70,93,122
Name: Symmetrical planar partitions of n.
References P. A. MacMahon, Combinatory Analysis. Cambridge Univ. Press,
London and New York, Vol.
1, 1915 and Vol. 2, 1916; see vol. 2, p 332.Keywords: nonn
Offset: 1Author(s): njas
ID Number: A000785 (Formerly M1392 and N0542)
Sequence: 0,0,0,1,2,5,11,21,39,73,129,226,388,659,1100,1821
Name: Asymmetrical planar partitions of n.
References P. A. MacMahon, Combinatory Analysis. Cambridge Univ. Press,
London and New York, Vol.
1, 1915 and Vol. 2, 1916; see vol. 2, p 332.Keywords: nonn
Offset: 1Author(s): njas
while in A000786, he counts my "a+s+b+r" .In other words, my "bothsym"
ID Number: A000786 (Formerly M1020 and N0383)
Sequence: 1,1,2,4,6,11,19,33,55,95,158,267,442,731,1193,1947
Name: Planar partitions of n.
References P. A. MacMahon, Combinatory Analysis. Cambridge Univ. Press,
London and New York, Vol.
1, 1915 and Vol. 2, 1916; see vol. 2, p 332.
Keywords: nonn
Offset: 1
Author(s): njas
==========================================================================
here, Atkin et al. count all the pilings : my "nosym" (but with offset =0)
ID Number: A000219 (Formerly M2566 and N1016)
Sequence: 1,1,3,6,13,24,48,86,160,282,500,859,1479,2485,4167,6879,11297,18334,
29601,47330,75278,118794,186475,290783,451194,696033,1068745,1632658,
2483234,3759612,5668963,8512309,12733429,18974973,28175955
Name: Planar partitions of n.
References A. O. L. Atkin, P. Bratley, I. G. McDonald and J. K. S. McKay,
Some computations for
m-dimensional partitions, Proc. Camb. Phil. Soc., 63 (1967),
1097-1100.
P. A. MacMahon, Combinatory Analysis. Cambridge Univ. Press,
London and New York, Vol.
1, 1915 and Vol. 2, 1916; see vol. 2, p 332.
L. Carlitz, Generating functions and partition problems, pp.
144-169 of A. L. Whiteman,
ed., Theory of Numbers, Proc. Sympos. Pure Math., 8 (1965). Amer.
Math. Soc., see p. 145,
eq. (1.6).
Knuth, D. E.; A Note on Solid Partitions. Math. Comp. 24,
955-961, 1970.
Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge,
MA: MIT Artificial
Intelligence Laboratory, Memo AIM-239, Item 18, Feb. 1972.
Bender, E. A. and Knuth, D. E. ``Enumeration of Plane
Partitions.'' J. Combin. Theory A.
13, 40-54, 1972.
G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976, p.
241.
Formula: G.f.: prod from k = 1 to inf ( 1 - x^k )^(-k).
Keywords: nonn,nice
Offset: 0
Author(s): njas
R.P. Stanley here counts my " 2 (nosym-mirrsym)" or "6a+2r+2s" (but with
offset =0)
ID Number: A005987 (Formerly M0562)
Sequence: 1,1,1,2,3,4,6,8,12,16,22,29,41,53,71,93,125,160,211,270,354,450,581,
735,948,1191,1517,1902,2414,3008,3791,4709,5909,7311,9119,11246,1
3981,
17178,21249
Name: Symmetric plane partitions of n.
References R. P. Stanley, Theory and application of plane partitions II,
Studies in Appl. Math., 50
(1971), 259-279.
Keywords: nonn,nice
Offset: 0
Author(s): njas
Other sequences by R.P. Stanley are beyond me. Maybe he could comment himself.
========================================================================
*** how it was done. ***
========================================================================
The 34 terms in A000219 allow the calculation of my "mirrsym";
Too bad no prescription is given of the method of calculation.
(Rest[A000219]+Take[Rest[A005987],34]) /2 == mirrsym
{1,2,4,8,14,27,47,86,149,261,444,760,1269,2119,3486,5711,9247,14906,23800,
37816,59622,93528,145759,226071,348612,535131,817280,1242824,1881310,
2836377,4258509,6369669,9491142,14092537}
Now that we know "nosym" and "mirrsym", we only need to generate the rare C3
and C3v pilings (my "r" and "b") to get the complete picture.
building up the C3v and C3 pilings from the rotations of the
balanced partitions of k<= 26, "balanced" meaning that the length should be
equal
to its first element.
Next, selecting the C3 & C3v pilings with n <= 34 should be complete for n<=34.
The procedure includes "adding" smaller rotation symmetric structures to
bigger ones until fixed point (needs 3 passes).
{{1,1},{4,1},{7,2},{8,1},{10,2},{11,1},{13,2},{14,1},{16,3},{17,2},{19,4},{20,
4},{22,4},{23,5},{25,5},{26,7},{27,1},{28,6},{29,9},{30,1},{31,6},{32,
11},{33,1},{34,8},{35,15},{36,2},{38,11},{39,3},{41,8},{42,4},{44,3},{45,
2},{50,1},{51,1},{54,1}}
{{13,2},{14,2},{16,2},{17,2},{19,4},{20,4},{22,6},{23,6},{25,10},{26,12},{28,
14},{29,18},{31,22},{32,32},{33,2},{34,28},{35,46},{36,4},{38,32},{39,8},{
41,20},{42,14},{44,6},{45,6},{47,4},{48,4}}
this gives
c3v: b={1,0,0,1,0,0,2,1,0,2,1,0,2,1,0,3,2,0,4,4,0,4,5,0,5,7,1,6,9,1,6,11,1,8}
c3 :{0,0,0,0,0,0,0,0,0,0,0,0,2,2,0,2,2,0,4,4,0,6,6,0,10,12,0,14,18,0,22,32,2,28}
and r= "c3"/2 , so
r={0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,2,2,0,3,3,0,5,6,0,7,9,0,11,16,1,14}
Solving the system of equations gives:
bothsym == (b+3 mirrsym-nosym+2 r)/3
rotasym == (2 b+nosym +4 r)/3
s == -b+2 mirrsym-nosym
a == (b-3 mirrsym+2 nosym-r)/3
================================================================================
(* the gory underside of things, or why it took a while *)
tools used: very ugly, only for my archive. (no peaches, no shake tree)
(* functions galore *)
pilings[par_List]:=
Module[{},tel=Length[par];alles= List/@Partitions[par[[1]] ];
Do[ alles=
Flatten[
Function[parit,
Flatten[{parit,{#}},1]& /@(
Select[Partitions[
par[[i]] ],(
Length[#]<=Length[Last at parit]&&
And@@Thread[ #<=Take[Last at parit,Length[#]]])& ])]/@
alles,1]
,{i,2,tel}];alles ]
ferrers[par_List]:=
Module[{maks,wide,it},wide=Length[par[[1]]];
maks=Max[Length[par],wide,Flatten[par]];
it=Join[#,Table[0,{wide-Length[#]}]]&/@
( par/. i_Integer :>Table[If[w>i,0,1],{w,maks}]);
DeleteCases[DeleteCases[Transpose[Apply[Plus,it,1]],0 |{},-1],0 |{},-1]]
flip[pile_List]:=
Module[{wide,it},wide=Length[pile[[1]]];
it=Join[#,Table[0,{wide-Length[#]}]]&/@pile;
DeleteCases[ Transpose[it] ,0|{},-1]]
majorpiling[pile_List]:=
First[Sort[Flatten[{#,flip[#]}&/@NestList[ferrers,pile ,2],1]]]
rotapiling[pile_List]:=First[Sort[ NestList[ferrers,pile ,2] ]]
allmajorpilings[pile_List]:=
Union[Sort[Flatten[{#,flip[#]}&/@NestList[ferrers,pile ,2],1]]]
allrotapilings[pile_List]:=Union[Sort[ NestList[ferrers,pile ,2] ]]
fullferrers[par_List]:=
Module[{maks,wide,it},wide=Length[par[[1]]];
maks=Max[Length[par],wide,Flatten[par]];
it=Join[#,Table[0,{wide-Length[#]}]]&/@
( par/. i_Integer :>Table[If[w>i,0,1],{w,maks}]);
Transpose[Apply[Plus,it,1]] ]
makerotor[par_List]:=Module[{size,work},size=Length[par];If[size===First at par,
work=Join[{par},Table[0,{size-1},{size}]];
work=NestList[fullferrers,work,2];
DeleteCases[MapThread[Max,work, 2 ],0|{},-1]]]
********** the program itself starts here *********
Timing[balanced=
Flatten[Table[Select[ Partitions[n] ,Length[#]==First[#]&],{n,26}]~
Drop~{2},1];]
Select[balanced,3Plus@@# -3First[#]+1<=34&];
tris=makerotor/@%;
c3v=Select[tris,Length[allmajorpilings[#]]==1&] ;
c3 =Select[tris,Length[allmajorpilings[#]]==2& ];
*******************************************************
the following sequence is repeated until fixed point : tris renames to
newtris, and back to tris.
*******************************************************
Function[pile,
z[pile,Select[tris ,
((Length[pile]>=2) &&(Length[First[#]]<=Length[Rest at First[pile]]) &&
And@@Thread[
Take[Rest at First[pile], Length[First[#]]]>=First[#]+1] )&
] ] ]/@tris;
%/.z[p_,{}] ->p ;
%/.{p :{__Integer}..}->w[p];
(% /.( argu:z[item__]):> Thread[ argu ])/.w->List ;
% /.z[ist1_,ist2_]:>(
ist=Map[Join[#1,Table[0,{Length[ist1] -Length[#1]}]]&,ist1 ];
z@ Join[ {First[ist]} , Transpose[Join[{Rest[First/@ ist] },
Transpose[ Rest[Rest/@ist] +(
waw=Join[
Map[Join[ #1 ,Table[0,{Length[ist]-1-Length[#1]}]]&,
ist2 ],
Table[0,{Length[ist]-1-Length[ist2]},{
Length[ist]-1}]]) ]] ]]);
%/. {p:__z}->z[p] //.z->Sequence;
Select[%,( Sort[Sort/@#]===Reverse[Reverse/@#] )&];
Union[DeleteCases[%,0,-1]];
newtris=Union[ % ,tris];
newc3v=Select[newtris ,Length[allmajorpilings[#]]==1&];
newc3 =Select[newtris ,Length[allmajorpilings[#]]==2&];
newtris=Union[newc3v,newc3];
{Length[newtris],Length[newc3v],Length[newc3]}
(* check for fixed point : *)
newtris==tris
(* else reiterate *)
tris= newtris ;
*******************************************************
Dr. Wouter L. J. MEEUSSEN
w.meeussen.vdmcc at vandemoortele.be
eu000949 at pophost.eunet.be
More information about the SeqFan
mailing list