Solid partitions

This article needs more work.

Please help by expanding it!

An ordinary (i.e. one-dimensional) partition is a row of nonnegative integers in nonincreasing (weakly decreasing) order whose sum is $\scriptstyle n\,$. A plane partition is a two-dimensional arrangement of nonnegative integers, nonincreasing (weakly decreasing) in the x- and y-directions, which sum to $\scriptstyle n\,$.

A solid partition of $\scriptstyle n\,$ is a three-dimensional arrangement of nonnegative integers

$n_{0,0,0}\,$	$n_{0,1,0}\,$	$n_{0,2,0}\,$	$n_{0,3,0}\,$	$\cdots$
$n_{1,0,0}\,$	$n_{1,1,0}\,$	$n_{1,2,0}\,$	$n_{1,3,0}\,$	$\cdots$
$n_{2,0,0}\,$	$n_{2,1,0}\,$	$n_{2,2,0}\,$	$n_{2,3,0}\,$	$\cdots$
$n_{3,0,0}\,$	$n_{3,1,0}\,$	$n_{3,2,0}\,$	$n_{3,3,0}\,$	$\cdots$
$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$

$n_{0,0,1}\,$	$n_{0,1,1}\,$	$n_{0,2,1}\,$	$n_{0,3,1}\,$	$\cdots$
$n_{1,0,1}\,$	$n_{1,1,1}\,$	$n_{1,2,1}\,$	$n_{1,3,1}\,$	$\cdots$
$n_{2,0,1}\,$	$n_{2,1,1}\,$	$n_{2,2,1}\,$	$n_{2,3,1}\,$	$\cdots$
$n_{3,0,1}\,$	$n_{3,1,1}\,$	$n_{3,2,1}\,$	$n_{3,3,1}\,$	$\cdots$
$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$

$n_{0,0,2}\,$	$n_{0,1,2}\,$	$n_{0,2,2}\,$	$n_{0,3,2}\,$	$\cdots$
$n_{1,0,2}\,$	$n_{1,1,2}\,$	$n_{1,2,2}\,$	$n_{1,3,2}\,$	$\cdots$
$n_{2,0,2}\,$	$n_{2,1,2}\,$	$n_{2,2,2}\,$	$n_{2,3,2}\,$	$\cdots$
$n_{3,0,2}\,$	$n_{3,1,2}\,$	$n_{3,2,2}\,$	$n_{3,3,2}\,$	$\cdots$
$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$

$n_{0,0,3}\,$	$n_{0,1,3}\,$	$n_{0,2,3}\,$	$n_{0,3,3}\,$	$\cdots$
$n_{1,0,3}\,$	$n_{1,1,3}\,$	$n_{1,2,3}\,$	$n_{1,3,3}\,$	$\cdots$
$n_{2,0,3}\,$	$n_{2,1,3}\,$	$n_{2,2,3}\,$	$n_{2,3,3}\,$	$\cdots$
$n_{3,0,3}\,$	$n_{3,1,3}\,$	$n_{3,2,3}\,$	$n_{3,3,3}\,$	$\cdots$
$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$

$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$

which are nonincreasing (weakly decreasing) in all rows, columns and stacks:

$n_{i+1,j,k}\leq n_{i,j,k},\ n_{i,j+1,k}\leq n_{i,j,k},\ n_{i,j,k+1}\leq n_{i,j,k}\,$

and which sum to $\scriptstyle n\,$:

$n=\sum _{i,j,k}n_{i,j,k}.\,$

Number of solid partitions of n

The number of solid partitions of a positive integer is an unsolved problem in combinatorial number theory.

The number of solid partitions of $\scriptstyle n,\,n\,\geq \,0\,$ gives the sequence (Cf. A000293)

{1, 1, 4, 10, 26, 59, 140, 307, 684, 1464, 3122, 6500, 13426, 27248, 54804, 108802, 214071, 416849, 805124, 1541637, 2930329, 5528733, 10362312, 19295226, 35713454, 65715094, 120256653, 218893580, ...}

Recurrence

...

Generating function

Conjectured (but false at n=6) by MacMahon

The generating function of point (degenerate) partitions is

$G_{\{p_{0}(n)\}}(x)\equiv \sum _{n=0}^{\infty }p_{0}(n)x^{n}={\frac {1}{(1-x)^{1}(1-x^{2})^{0}(1-x^{3})^{0}(1-x^{4})^{0}\cdots }}={\frac {1}{1-x}}=1+1x+1x^{2}+1x^{3}+1x^{4}+1x^{5}+1x^{6}+\cdots .\,$

The generating function of ordinary or line (one-dimensional) partitions is the reciprocal of Euler's function

$G_{\{p_{1}(n)\}}(x)\equiv \sum _{n=0}^{\infty }p_{1}(n)x^{n}={\frac {1}{(1-x)^{1}(1-x^{2})^{1}(1-x^{3})^{1}(1-x^{4})^{1}\cdots }}={\frac {1}{\prod _{n=1}^{\infty }(1-x^{n})}}=1+1x+2x^{2}+3x^{3}+5x^{4}+7x^{5}+11x^{6}+\cdots .\,$

In 1912, Major Percy A. MacMahon proved that the generating function for plane partitions is

$G_{\{p_{2}(n)\}}(x)\equiv \sum _{n=0}^{\infty }p_{2}(n)x^{n}={\frac {1}{(1-x)^{1}(1-x^{2})^{2}(1-x^{3})^{3}(1-x^{4})^{4}\cdots }}={\frac {1}{\prod _{n=1}^{\infty }(1-x^{n})^{n}}}=1+1x+3x^{2}+6x^{3}+13x^{4}+24x^{5}+48x^{6}+\cdots .\,$

MacMahon conjectured, but doubted it later, (but it was shown to disagree at $\scriptstyle n\,$ = 6) that the generating function for solid partitions is

$G_{\{p_{3}(n)\}}(x)\equiv \sum _{n=0}^{\infty }p_{3}(n)x^{n}\neq {\frac {1}{(1-x)^{1}(1-x^{2})^{3}(1-x^{3})^{6}(1-x^{4})^{10}\cdots }}={\frac {1}{\prod _{n=1}^{\infty }(1-x^{n})^{t_{n}}}}=1+1x+4x^{2}+10x^{3}+26x^{4}+59x^{5}+\mathbf {141} x^{6}+\cdots ,\,$

where $\scriptstyle t_{n}={\frac {n(n+1)}{2}}\,$ is the $\scriptstyle n\,$^th triangular number.

Very tempting conjecture indeed, but false for $\scriptstyle n\,$ = 6. MacMahon had actually guessed the following formula for the generating function of $\scriptstyle d\,$-dimensional partitions

$G_{\{p_{d}(n)\}}(x)~{\stackrel {?}{=}}~{\frac {1}{\prod _{n=1}^{\infty }(1-x^{n})^{\binom {n+d-2}{d-1}}}},\,$

where $\scriptstyle {\binom {n+d-2}{d-1}}\,$ is the $\scriptstyle n\,$^th ($\scriptstyle d-1\,$)-dimensional simplex number.

However, Rajesh and Mustonen seem to claim that the formula nevertheless captures the asymptotics correctly.

Asymptotic behaviour

Asymptotic behaviour of p_3(n)

...

Asymptotic behaviour log(p_3(n))

$\lim _{n\to \infty }{\frac {\log(p_{3}(n))}{n^{\frac {3}{4}}}}=1.79\pm 0.01,\,$

where $\scriptstyle p_{3}(n)\,$ is the number of solid partitions of the integer $\scriptstyle n\,$.

Noting that

$\log(6)=1.791759469228055\ldots ,\,$

could this be the actual limit? (Cf. A016629 Decimal expansion of ln(6).)

This would produce the result (if true...)

$\lim _{n\to \infty }{\frac {\log(p_{3}(n))}{n^{\frac {3}{4}}\log(6)}}=\lim _{n\to \infty }{\frac {\log(p_{3}(n))}{\log(6^{n^{3/4}})}}~{\stackrel {?}{=}}~1.\,$

This gives the asymptotic behaviour on the number of digits of $\scriptstyle p_{3}(n)\,$ in any fixed radix representation, e.g. base 10, of $\scriptstyle p_{3}(n)\,$

${\log _{10}(p_{3}(n))}~{\stackrel {?}{\sim }}~{\frac {\log(6)}{\log(10)}}n^{\frac {3}{4}},\,$

and in base 6

${\log _{6}(p_{3}(n))}~{\stackrel {?}{\sim }}~n^{\frac {3}{4}}.\,$

Table

Observe that for $\scriptstyle n\,$ = 1, 2 and 3 we obtain the $\scriptstyle d\,$-dimensional simplex numbers (i.e. triangular gnomon numbers, triangular numbers, tetrahedral numbers.) Would this be true for $\scriptstyle p_{d}(n),\,d\,\geq \,4\,$?

Solid, plane, line and point partitions

$n\,$	$p_{3}(n)\,$	$p_{2}(n)\,$	$p_{1}(n)\,$	$p_{0}(n)\,$
0	1	1	1	1
1	1	1	1	1
2	4	3	2	1
3	10	6	3	1
4	26	13	5	1
5	59	24	7	1
6	140	48	11	1
7	307	86	15	1
8	684	160	22	1
9	1464	282	30	1
10	3122	500	42	1
11	6500	859	56	1
12	13426	1479	77	1
13	27248	2485	101	1
14	54804	4167	135	1
15	108802	6879	176	1
16	214071	11297	231	1
17	416849			1
18	805124			1
19	1541637			1
20	2930329			1
21	5528733			1
22	10362312			1
23	19295226			1
24	35713454			1
25	65715094			1
26	120256653			1
27	218893580			1
28	396418699			1
29	714399381			1
30	1281403841			1
31	2287986987			1
32	4067428375			1
33	7200210523			1
34	12693890803			1
35	22290727268			1
36	38993410516			1
37	67959010130			1
38	118016656268			1
39	204233654229			1
40	352245710866			1
41	605538866862			1
42	1037668522922			1
43	1772700955975			1
44	3019333854177			1
45	5127694484375			1
46	8683676638832			1
47	14665233966068			1
48	24700752691832			1
49	41495176877972			1
50	69531305679518			1
51	116221415325837			1
52	193794476658112			1
53	322382365507746			1
54	535056771014674			1
55	886033384475166			1
56	1464009339299229			1
57	2413804282801444			1
58	3971409682633930			1
59	6520649543912193			1
60	10684614225715559			1
61	17472947006257293			1
62	28518691093388854			1

See also

• Partitions (one-dimensional partitions)
• Plane partitions (two-dimensional partitions)
• Solid partitions (three-dimensional partitions)

• Compositions (one-dimensional ordered partitions)
• Plane compositions (two-dimensional ordered partitions)
• Solid compositions (three-dimensional ordered partitions)

• Multiplicative partitions (factorizations)
• Multiplicative compositions (ordered factorizations)

• Prime signature (which may be viewed as a given partition of $\scriptstyle \Omega (n)\,$, the number of prime factors (with repetition) of $\scriptstyle n\,$.)

References

• P. A. MacMahon, Combinatory Analysis, Vol. 2. New York: Chelsea, pp. 75-176, 1960.

External links

• Donald E. Knuth, A Note on Solid Partitions, 1970.
• Boltzmann | Physics enthusiasts at IIT Madras, Counting Solid Partitions.
• Boltzmann | Physics enthusiasts at IIT Madras, Number of solid partitions for N <= 62.
• Boltzmann | Physics enthusiasts at IIT Madras, Solid Partitions using Volunteer Computing.
• Ville Mustonen and R. Rajesh, Numerical estimation of the asymptotic behaviour of solid partitions of an integer, 2003 J. Phys. A: Math. Gen. 36 6651.
• Weisstein, Eric W., Solid Partition, from MathWorld—A Wolfram Web Resource..