Solid partition

<h2 id="ferrers-diagrams-for-solid-partitions">Ferrers diagrams for solid partitions</h2>
Another representation for solid partitions is in the form of <a href="/facts/Norman_Macleod_Ferrers/5LcJv1lR">Ferrers</a> diagrams. The Ferrers diagram of a solid partition of 
 
 
 
 n
 
 
 {\displaystyle n}
 
 is a collection of 
 
 
 
 n
 
 
 {\displaystyle n}
 
 points or nodes, 
 
 
 
 λ
 =
 (
 
 
 y
 
 
 1
 
 
 ,
 
 
 y
 
 
 2
 
 
 ,
 …
 ,
 
 
 y
 
 
 n
 
 
 )
 
 
 {\displaystyle \lambda =(\mathbf {y} _{1},\mathbf {y} _{2},\ldots ,\mathbf {y} _{n})}
 
, with 
 
 
 
 
 
 y
 
 
 i
 
 
 ∈
 
 
 Z
 
 
 ≥
 0
 
 
 4
 
 
 
 
 {\displaystyle \mathbf {y} _{i}\in \mathbb {Z} _{\geq 0}^{4}}
 
 satisfying the condition:<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

Condition FD: If the node 
 
 
 
 
 a
 
 =
 (
 
 a
 
 1
 
 
 ,
 
 a
 
 2
 
 
 ,
 
 a
 
 3
 
 
 ,
 
 a
 
 4
 
 
 )
 ∈
 λ
 
 
 {\displaystyle \mathbf {a} =(a_{1},a_{2},a_{3},a_{4})\in \lambda }
 
, then so do all the nodes 
 
 
 
 
 y
 
 =
 (
 
 y
 
 1
 
 
 ,
 
 y
 
 2
 
 
 ,
 
 y
 
 3
 
 
 ,
 
 y
 
 4
 
 
 )
 
 
 {\displaystyle \mathbf {y} =(y_{1},y_{2},y_{3},y_{4})}
 
 with 
 
 
 
 0
 ≤
 
 y
 
 i
 
 
 ≤
 
 a
 
 i
 
 
 
 
 {\displaystyle 0\leq y_{i}\leq a_{i}}
 
 for all 
 
 
 
 i
 =
 1
 ,
 2
 ,
 3
 ,
 4
 
 
 {\displaystyle i=1,2,3,4}
 
.
For instance, the Ferrers diagram

(
          
            
              
                
                  
                    
                      0
                    
                  
                  
                    
                      0
                    
                  
                  
                    
                      0
                    
                  
                  
                    
                      0
                    
                  
                
              
            
            
              
                
                  
                    
                      0
                    
                  
                  
                    
                      0
                    
                  
                  
                    
                      1
                    
                  
                  
                    
                      0
                    
                  
                
              
            
            
              
                
                  
                    
                      0
                    
                  
                  
                    
                      1
                    
                  
                  
                    
                      0
                    
                  
                  
                    
                      0
                    
                  
                
              
            
            
              
                
                  
                    
                      1
                    
                  
                  
                    
                      0
                    
                  
                  
                    
                      0
                    
                  
                  
                    
                      0
                    
                  
                
              
            
            
              
                
                  
                    
                      1
                    
                  
                  
                    
                      1
                    
                  
                  
                    
                      0
                    
                  
                  
                    
                      0
                    
                  
                
              
            
          
          )
        
         
        ,
      
    
    {\displaystyle \left({\begin{smallmatrix}0\\0\\0\\0\end{smallmatrix}}{\begin{smallmatrix}0\\0\\1\\0\end{smallmatrix}}{\begin{smallmatrix}0\\1\\0\\0\end{smallmatrix}}{\begin{smallmatrix}1\\0\\0\\0\end{smallmatrix}}{\begin{smallmatrix}1\\1\\0\\0\end{smallmatrix}}\right)\ ,}

where each column is a node, represents a solid partition of 
 
 
 
 5
 
 
 {\displaystyle 5}
 
. There is a natural action of the permutation group 
 
 
 
 
 S
 
 4
 
 
 
 
 {\displaystyle S_{4}}
 
 on a Ferrers diagram – this corresponds to permuting the four coordinates of all nodes. This generalises the operation denoted by conjugation on usual partitions.

<h3>Equivalence of the two representations</h3>
Given a Ferrers diagram, one constructs the solid partition (as in the main definition) as follows.

Let 
 
 
 
 
 n
 
 i
 ,
 j
 ,
 k
 
 
 
 
 {\displaystyle n_{i,j,k}}
 
 be the number of nodes in the Ferrers diagram with coordinates of the form 
 
 
 
 (
 i
 −
 1
 ,
 j
 −
 1
 ,
 k
 −
 1
 ,
 ∗
 )
 
 
 {\displaystyle (i-1,j-1,k-1,*)}
 
 where 
 
 
 
 ∗
 
 
 {\displaystyle *}
 
 denotes an arbitrary value. The collection 
 
 
 
 
 n
 
 i
 ,
 j
 ,
 k
 
 
 
 
 {\displaystyle n_{i,j,k}}
 
 form a solid partition. One can verify that condition FD implies that the conditions for a solid partition are satisfied.
Given a set of 
 
 
 
 
 n
 
 i
 ,
 j
 ,
 k
 
 
 
 
 {\displaystyle n_{i,j,k}}
 
 that form a solid partition, one obtains the corresponding Ferrers diagram as follows.

Start with the Ferrers diagram with no nodes. For every non-zero 
 
 
 
 
 n
 
 i
 ,
 j
 ,
 k
 
 
 
 
 {\displaystyle n_{i,j,k}}
 
, add 
 
 
 
 
 n
 
 i
 ,
 j
 ,
 k
 
 
 
 
 {\displaystyle n_{i,j,k}}
 
 nodes 
 
 
 
 (
 i
 −
 1
 ,
 j
 −
 1
 ,
 k
 −
 1
 ,
 
 y
 
 4
 
 
 )
 
 
 {\displaystyle (i-1,j-1,k-1,y_{4})}
 
 for 
 
 
 
 0
 ≤
 
 y
 
 4
 
 
 <
 
 n
 
 i
 ,
 j
 ,
 k
 
 
 
 
 {\displaystyle 0\leq y_{4}<n_{i,j,k}}
 
 to the Ferrers diagram. By construction, it is easy to see that condition FD is satisfied.
For example, the Ferrers diagram with 
 
 
 
 5
 
 
 {\displaystyle 5}
 
 nodes given above corresponds to the solid partition with

n
          
            1
            ,
            1
            ,
            1
          
        
        =
        
          n
          
            2
            ,
            1
            ,
            1
          
        
        =
        
          n
          
            1
            ,
            2
            ,
            1
          
        
        =
        
          n
          
            1
            ,
            1
            ,
            2
          
        
        =
        
          n
          
            2
            ,
            2
            ,
            1
          
        
        =
        1
      
    
    {\displaystyle n_{1,1,1}=n_{2,1,1}=n_{1,2,1}=n_{1,1,2}=n_{2,2,1}=1}

with all other 
 
 
 
 
 n
 
 i
 ,
 j
 ,
 k
 
 
 
 
 {\displaystyle n_{i,j,k}}
 
 vanishing.

<h2 id="generating-function">Generating function</h2>
Let 
 
 
 
 
 p
 
 3
 
 
 (
 0
 )
 ≡
 1
 
 
 {\displaystyle p_{3}(0)\equiv 1}
 
. Define the generating function of solid partitions, 
 
 
 
 
 P
 
 3
 
 
 (
 q
 )
 
 
 {\displaystyle P_{3}(q)}
 
, by

P
 
 3
 
 
 (
 q
 )
 :=
 
 ∑
 
 n
 =
 0
 
 
 ∞
 
 
 
 p
 
 3
 
 
 (
 n
 )
 
 q
 
 n
 
 
 =
 1
 +
 q
 +
 4
 
 q
 
 2
 
 
 +
 10
 
 q
 
 3
 
 
 +
 26
 
 q
 
 4
 
 
 +
 59
 
 q
 
 5
 
 
 +
 140
 
 q
 
 6
 
 
 +
 ⋯
 
 
 {\displaystyle P_{3}(q):=\sum _{n=0}^{\infty }p_{3}(n)q^{n}=1+q+4q^{2}+10q^{3}+26q^{4}+59q^{5}+140q^{6}+\cdots }
 
 (sequence A000293 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>).
The generating functions of <a href="/facts/Integer_partition/LtyXWqwH">integer partitions</a> and <a href="/facts/Plane_partition/erlrREf2">plane partitions</a> have simple product formulae, due to <a href="/facts/Leonhard_Euler/z2fsbjgj">Euler</a> and <a href="/facts/Percy_Alexander_MacMahon/scUegUSn">MacMahon</a>, respectively. However, a guess of <a href="/facts/Percy_Alexander_MacMahon/scUegUSn">MacMahon</a> fails to correctly reproduce the solid partitions of 6.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> It appears that there is no simple formula for the generating function of solid partitions; in particular, there cannot be any formula analogous to the product formulas of Euler and MacMahon.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<h2 id="exact-enumeration-using-computers">Exact enumeration using computers</h2>
Given the lack of an explicitly known generating function, the enumerations of the numbers of solid partitions for larger integers have been carried out numerically. There are two algorithms that are used to enumerate solid partitions and their higher-dimensional generalizations. The work of Atkin. et al. used an algorithm due to Bratley and McKay.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> In 1970, Knuth proposed a different algorithm to enumerate topological sequences that he used to evaluate numbers of solid partitions of all integers 
 
 
 
 n
 ≤
 28
 
 
 {\displaystyle n\leq 28}
 
.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> Mustonen and Rajesh extended the enumeration for all integers 
 
 
 
 n
 ≤
 50
 
 
 {\displaystyle n\leq 50}
 
.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> In 2010, S. Balakrishnan proposed a parallel version of Knuth's algorithm that has been used to extend the enumeration to all integers 
 
 
 
 n
 ≤
 72
 
 
 {\displaystyle n\leq 72}
 
.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> One finds

p
          
            3
          
        
        (
        72
        )
        =
        3464274974065172792
         
        ,
      
    
    {\displaystyle p_{3}(72)=3464274974065172792\ ,}

which is a 19 digit number illustrating the difficulty in carrying out such exact enumerations.

<h2 id="asymptotic-behavior">Asymptotic behavior</h2>
It is conjectured that there exists a constant 
 
 
 
 c
 
 
 {\displaystyle c}
 
 such that<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a><a class="footnote-ref" id="fnref:11" href="#fn:11">11</a><a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

 
 
 
 
 lim
 
 n
 →
 ∞
 
 
 
 
 
 log
 ⁡
 
 p
 
 3
 
 
 (
 n
 )
 
 
 n
 
 3
 
 /
 
 4
 
 
 
 
 =
 c
 .
 
 
 {\displaystyle \lim _{n\rightarrow \infty }{\frac {\log p_{3}(n)}{n^{3/4}}}=c.}

<h2 id="external-links">External links</h2>
<ul><li>OEIS <a href="https://oeis.org/A000293">sequence A000293 (Solid (i.e., three-dimensional) partitions)</a></li>
<li><a href="http://boltzmann.wikidot.com/solid-partitions">The Solid Partitions Project of IIT Madras</a></li>
<li><a href="http://mathworld.wolfram.com/SolidPartition.html">The Mathworld entry for Solid Partitions</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">MacMahon, P. A. (1916). Combinatory Analysis. Vol. 2. London and New York: Cambridge University Press. p. 332. <a href="/wiki/Percy_Alexander_MacMahon" target="_blank">/wiki/Percy_Alexander_MacMahon</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Andrews, George E. (1984). The theory of partitions. Cambridge University Press. doi:10.1017/CBO9780511608650. <a href="/wiki/George_Andrews_(mathematician)" target="_blank">/wiki/George_Andrews_(mathematician)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Atkin, A. O. L.; Bratley, P.; McDonald, I. G.; McKay, J. K. S. (1967). "Some computations for 
 
 
 
 m
 
 
 {\displaystyle m}
 
-dimensional partitions". Mathematical Proceedings of the Cambridge Philosophical Society. 63 (4): 1097–1100. doi:10.1017/S0305004100042171. <a href="/wiki/A._O._L._Atkin" target="_blank">/wiki/A._O._L._Atkin</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Atkin, A. O. L.; Bratley, P.; McDonald, I. G.; McKay, J. K. S. (1967). "Some computations for 
 
 
 
 m
 
 
 {\displaystyle m}
 
-dimensional partitions". Mathematical Proceedings of the Cambridge Philosophical Society. 63 (4): 1097–1100. doi:10.1017/S0305004100042171. <a href="/wiki/A._O._L._Atkin" target="_blank">/wiki/A._O._L._Atkin</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Stanley, Richard P. (1999). Enumerative Combinatorics, volume 2. Cambridge University Press. p. 402. doi:10.1017/CBO9780511609589. <a href="/wiki/Richard_P._Stanley" target="_blank">/wiki/Richard_P._Stanley</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Bratley, P.; McKay, J. K. S. (1967). "Algorithm 313: Multi-dimensional partition generator". Communications of the ACM. 10 (10): 666. doi:10.1145/363717.363783. <a href="/wiki/John_McKay_(mathematician)" target="_blank">/wiki/John_McKay_(mathematician)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Knuth, Donald E. (1970). "A note on solid partitions". Mathematics of Computation. 24 (112): 955–961. doi:10.1090/S0025-5718-1970-0277401-7. <a href="/wiki/Donald_Knuth" target="_blank">/wiki/Donald_Knuth</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Mustonen, Ville; Rajesh, R. (2003). "Numerical Estimation of the Asymptotic Behaviour of Solid Partitions of an Integer". Journal of Physics A: Mathematical and General. 36 (24): 6651. arXiv:cond-mat/0303607. doi:10.1088/0305-4470/36/24/304. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Balakrishnan, Srivatsan; Govindarajan, Suresh; Prabhakar, Naveen S. (2012). "On the asymptotics of higher-dimensional partitions". Journal of Physics A: Mathematical and General. 45: 055001. arXiv:1105.6231. doi:10.1088/1751-8113/45/5/055001. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Destainville, Nicolas; Govindarajan, Suresh (2015). "Estimating the asymptotics of solid partitions". Journal of Statistical Physics. 158: 950–967. arXiv:1406.5605. doi:10.1007/s10955-014-1147-z. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Mustonen, Ville; Rajesh, R. (2003). "Numerical Estimation of the Asymptotic Behaviour of Solid Partitions of an Integer". Journal of Physics A: Mathematical and General. 36 (24): 6651. arXiv:cond-mat/0303607. doi:10.1088/0305-4470/36/24/304. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Bhatia, D. P.; Prasad, M. A.; Arora, D. (1997). "Asymptotic results for the number of multidimensional partitions of an integer and directed compact lattice animals". Journal of Physics A: Mathematical and General. 30 (7): 2281. doi:10.1088/0305-4470/30/7/010. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
</ol>

Solid partition open-in-new

Solid partition