Jump to content

User:Sophie Hofmanninger/Plane Partitions Test

From Wikipedia, the free encyclopedia
Plane partition (parts as heights)

In mathematics and especially in combinatorics, a plane partition is a two-dimensional array of nonnegative integers (with positive integer indices i and j) that is nonincreasing in both indices. This means that

and for all i and j.

Moreover only finitely many of the i,j are nonzero. A plane partitions may be represented visually by the placement of a stack of unit cubes above the point (i,j) in the plane, giving a three-dimensional solid as shown in the picutre.

The sum of a plane partition is

The sum describes the number of cubes of which the plane partition consists. PL(n) denotes the number of plane partitions with sum n.

For example, there are six plane partitions with sum 3:

so PL(3) = 6. (Here the plane partitions are drawn using matrix indexing for the coordinates and the entries equal to 0 are suppressed for readability.) Let be the total number of plane partitions in which r is the number of rows that are unequal to zero, s is the number of columns that are non-zero, and t is the largest integer of the matrix. Plane partitions are often described by the positions of the unit cubes. Therefore a plane partition is defined as a finite subset of positive integer lattice points (i,j,k), such that if (r,s,t) lies in and if (i,j,k) satisfies , and , then (i,j,k) also lies in .

Overview

[edit]
Name Example A-number[1] Total number of plane partitions
Plane partitions (PP)
1, 2, 20, 980,... A008793
Symmetric plane partition (SPP)
1, 2, 10, 112,... A049505
Cyclically symmetric plane partition (CSPP)
1, 2, 5, 20, 132,... A006366
Totally symmetric plane partition (TSPP)
1, 2, 5, 16, 66,... A005157
Self-complementary plane partition (SCPP)
1, 4, 400,... A259049

Cyclically symmetric self-complementary plane partitions (CSSCPP)
1, 1, 4, 49,... A049503
Totally symmetric self-complementary plane partitions (TSSCPP)
1, 1, 2, 7, 42,... A005130


Theorem Formula conjectured by proved by
Theorem PP P. A. MacMahon [2] P. A. MacMahon [3]
Theorem SPP: The MacMahon conjecture P. A. MacMahon [4] G. Andrews [5]
Theorem CSPP:The Macdonald conjecture I. G. Macdonald [6] G. Andrews (q=1)[7]; W. H. Mills, D. Robbins, H. Rumsey[8]
Theorem TSPP: The TSPP conjecture I. G. Macdonald [6] J. R. Stembridge[9]; G. Andrews, P. Paule, C. Schneider[10]
Theorem TSPP: The q-TSPP conjecture G. Andrews, D. Robbins C. Koutschan, M. Kauers, D. Zeilberger [11]
Theorem SCPP: symmetric function analogue R. P. Stanley[12] R. P. Stanley[12]
Corollary SCPP R. P. Stanley[12]
Theorem CSSCPP R. Stanley, D. Robbins[12] G. Kuperberg[13]
Theorem TSSCPP W. H. Mills, D. Robbins, H. Rumsey[14] G. Andrews[15]

Generating function of plane partitions

[edit]

By a result of Percy A. MacMahon, the generating function for PL(n) is given by

[16]

This is sometimes referred to as the MacMahon function.

This formula may be viewed as the 2-dimensional analogue of Euler's product formula for the number of integer partitions of n. There is no analogous formula known for partitions in higher dimensions (i.e., for solid partitions)[17]. The asymptotics of plane partitions was worked out by E. M. Wright [18]. One obtains, for large :

Here the typographical error (in Wright's paper) has been corrected, pointed out by Mutafchiev and Kamenov [19]. Evaluating numerically yields

Around 1896 Percy A. MacMahon set up the generating function of plane partitions that are subsets of in his first paper on plane partitions[2]. The formula is given by

A proof of this formula can be found in the book Combinatory Analysis written by Percy A. MacMahon[3]. Percy A. MacMahon also mentions in his book the generating functions of plane partitions in article 429[20]. The formula for the generating function can be written in an alternative way, which is given by

Setting q=1 in the formulas above yields

Percy A. MacMahon obtained that the total number of plane partitions in is given by [21] . The planar case (when t = 1) yields the binomial coefficients:

Ferrers diagrams for plane partitions

[edit]

Another representation for plane partitions is in the form of Ferrers diagrams. The Ferrers diagram of a plane partition of is a collection of points or nodes, , with satisfying the condition:[22]

Condition FD: If the node , then so do all the nodes with for all .

Replacing every node of a plane partition by a unit cube with edges aligned with the axes leads to the stack of cubes representation for the plane partition.

Equivalence of the two representations

[edit]

Given a Ferrers diagram, one constructs the plane partition (as in the main definition) as follows.

Let be the number of nodes in the Ferrers diagram with coordinates of the form where denotes an arbitrary value. The collection form a plane partition. One can verify that condition FD implies that the conditions for a plane partition are satisfied.

Given a set of that form a plane partition, one obtains the corresponding Ferrers diagram as follows.

Start with the Ferrers diagram with no nodes. For every non-zero , add nodes of the form for to the Ferrers diagram. By construction, it is easy to see that condition FD is satisfied.

For instance, below are shown the two representations of a plane partitions of 5.

Above, every node of the Ferrers diagram is written as a column and we have only written only the non-vanishing as is conventional.

Action of S2, S3 and C3 on plane partitions

[edit]

is the group of permutations acting on the first two coordinates of (i,j,k). This group contains the identity (i,j,k) and the transposition (i,j,k)→(j,i,k). The number of elements in an orbit is denoted by ||. denotes the set of orbits of elements of under the action of . The height of an element (i,j,k) is defined by

The height increases by one for each step away from the back right corner. For example the corner position (1,1,1) has height 1 and ht(2,1,1)=2. ht() is the height of an orbit, which is the height of any element in the orbit. This notation of the height differs from the notation of Ian G. Macdonald[6].

There is a natural action of the permutation group on a Ferrers diagram—this corresponds to simultaneously permuting the three coordinates of all nodes. This generalizes the conjugation operation for partitions. The action of can generate new plane partitions starting from a given plane partition. Below there are shown six plane partitions of 4 that are generated by the action. Only the exchange of the first two coordinates is manifest in the representation given below.

is called the group of cyclic permutations and consists of

Symmetric plane partitions

[edit]

A plane partition is called symmetric if i,j = j,i for all i,j . In other words, a plane partition is symmetric if (i,j,k) if and only if (j,i,k). Plane partitions of this type are symmetric with respect to the plane x = y. Below an example of a symmetric plane partition is given. Attached the matrix is visualised.

Symmetric Plane Partition

In 1898, Percy A. MacMahon formulated his conjecture about the generating function for symmetric plane partitions which are subsets of [23]. This conjecture is called The MacMahon conjecture. The generating function is given by

Ian G. Macdonald[6] pointed out that Percy A. MacMahon's conjecture reduces to

In 1972 Edward A. Bender and Donald E. Knuth[24] conjectured a simple closed form for the generating function for plane partition which have at most r rows and strict decrease along the rows. George Andrews[25] showed, that the conjecture of Edward A. Bender and Donald E. Knuth and the MacMahon conjecture are equivalent. MacMahon's conjecture was proven almost simultaneously by George Andrews in 1977[26] and later Ian G. Macdonald presented an alternative proof [6][ example 16–19, p. 83-86]. When setting q = 1 yields the counting function which is given by

For a proof of the case q = 1 please refer to George Andrews' paper MacMahon's conjecture on symmetric plane partitions[27].

Cyclically symmetric plane partitions

[edit]

is called cyclically symmetric, if the i-th row of is conjugate to the i-th column for all i. The i-th row is regarded as an ordinary partition. The conjugate of a partition is the partition whose diagram is the transpose of partition [6]. In other words, the plane partition is cyclically symmetric if whenever (i,j,k) then (k,i,j) and (j,k,i) are as well in . Below an example of a cyclically symmetric plane partition and it's visualization is given.

Cyclically symmetric plane partition

Ian G. Macdonald's conjecture provides a formula for calculating the number of cyclically symmetric plane partitions for a given integer r. This conjecture is called The Macdonald conjecture. The generating function for cyclically symmetric plane partitions which are subsets of is given by

This equation can also be written in another way

In 1979 George Andrews has proven Macdonald's conjecture for the case q=1 as the "weak" Macdonald conjecture[28]. Three years later William. H. Mills, David Robbins and Howard Rumsey proved the general case of Macdonald's conjecture in their paper Proof of the Macdonald conjecture[29]. The formula for is given by the "weak" Macdonald conjecture

Totally symmetric plane partitions

[edit]

A totally symmetric plane partition is a plane partition which is symmetric and cyclically symmetric. This means that the diagram is symmetric at all three diagonal planes. So therefore if (i,j,k) then all six permutations of (i,j,k) are also in . Below an example of a matrix for a totally symmetric plane partition is given. The picture shows the visualisation of the matrix.

Totally symmetric plane partition

Ian G. Macdonald found the total number of totally symmetric plane partitions that are subsets of . The formula is given by

In 1995 John R. Stembridge first proved the formula for [30] and later in 2005 it was proven by George Andrews, Peter Paule, and Carsten Schneider[31]. Around 1983 George Andrews and David Robbins independently stated an explicit product formula for the orbit-counting generating function for totally symmetric plane partitions[32][33]. This formula already alluded to in George E. Andrews' paper Totally symmetric plane partitions which was published 1980[34]. The conjecture is called The q-TSPP conjecture and it is given by:

Let be the symmetric group. The orbit counting function for totally symmetric plane partitions that fit inside is given by the formula

This conjecture turned into a Theorem in 2011. For a proof of the q-TSPP conjecture please refer to the paper A proof of George Andrews' and David Robbins' q-TSPP conjecture by Christoph Koutschan, Manuel Kauers and Doron Zeilberger [35].

Self-complementary plane partitions

[edit]

If for all , , then the plane partition is called self-complementary. It is necessary that the product is even. Below an example of a self-complementary symmetric plane partition and it's visualisation is given.

Self-complementary plane partition

Richard P. Stanley[12] conjectured formulas for the total number of self-complementary plane partitions . According to Richard Stanley, David Robbins also formulated formulas for the total number of self-complementary plane partitions in a different but equivalent form. The total number of self-complementary plane partitions that are subsets of is given by

It is necessary that the product of r,s and t is even. A proof can be found in the paper Symmetries of Plane Partitions which was written by Richard P. Stanley[36][12]. The proof works with Schur functions . Stanley's proof of the ordinary enumeration of self-complementary plane partitions yields the q-analogue by substitutting for [37]. This is a special case of Stanley's hook-content formula[38]. The generating function for self-complementary plane partitions is given by

Substituting this formula in

supplies the desired q-analogue case.

Cyclically symmetric self-complementary plane partitions

[edit]

A plane partition is called cyclically symmetric self-complementary if it is cyclically symmetric and self-complementary. The figure presents a cyclically symmetric self-complementary plane partition and the according matrix is below.

Cyclically symmetric self-complementary plane partition

In a private communication with Richard P. Stanley, David Robbins conjectured that the total number of cyclically symmetric self-complementary plane partitions is given by [33][12] . The total number of cyclically symmetric self-complementary plane partitions is given by

is the number of alternating sign matrices. A formula for is given by

Greg Kuperberg proved the formula for in 1994[39].

Totally symmetric self-complementary plane partitions

[edit]

A totally symmetric self-complementary plane partition is a plane partition which is totally symmetric and self-complementary. For instance such an type of plane partition can look like the matrix below. The picture visualises the matrix.

Totally symmetric self-complementary plane partition

The formula was conjectured by William H. Mills, David Robbins and Howard Rumsey in their work Self-Complementary Totally Symmetric Plane Partitions [40]. The total number of totally symmetric self-complementary plane partitions is given by

George Andrews has proven this formula in 1994 in his paper Plane Partitions V: The TSSCPP Conjecture [41].


References

[edit]
  1. ^ "The On-Line Encyclopedia of Integer Sequences".
  2. ^ a b MacMahon, Percy A. (1896). "XVI. Memoir on the theory of the partition of numbers.-Part I". Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences. 187: Article 52.
  3. ^ a b MacMahon, Major Percy A. (1916). Combinatory Analysis Vol 2. Chambridge: at the University Press. pp. §495.
  4. ^ MacMahon, Percy Alexander (1899). "Partitions of numbers whose graphs possess symmetry". Transactions of the Cambridge Philosophical Society. 17.
  5. ^ Andrews, George (1975). "Plane Partitions (I): The Mac Mahon Conjecture". Adv. Math. Suppl. Stud. 1.
  6. ^ a b c d e f Macdonald, Ian G. (1998). Symmetric Functions and Hall Polynomials. Clarendon Press. pp. 20f, 85f. ISBN 9780198504504.
  7. ^ Andrews, George E. (1979). "Plane Partitions(III): The Weak Macdonald Conjecture". Inventiones Mathematicae. 53 (3): 193–225. doi:10.1007/BF01389763. S2CID 122528418.
  8. ^ Mills, Robbins, Rumsey (1982). "Proof of the Macdonald conjecture". Inventiones Mathematicae. 66: 73–88. doi:10.1007/BF01404757. S2CID 120926391.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  9. ^ Stembridge, John R. (1995). "The Enumeration of Totally Symmetric Plane Partitions". Advances in Mathematics. 111 (2): 227–243. doi:10.1006/aima.1995.1023.
  10. ^ Andrews, Paule, Schneider (2005). "Plane Partitions VI: Stembridge's TSPP theorem". Advances in Applied Mathematics. 34 (4): 709–739. doi:10.1016/j.aam.2004.07.008.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  11. ^ Koutschan, Kauers, Zeilberger (2011). "A proof of George Andrews' and David Robbins' q-TSPP conjecture". PNAS. 108 (6): 2196–2199. doi:10.1073/pnas.1019186108.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  12. ^ a b c d e f g Stanley, Richard P. (1986). "Symmetries of Plane Partitions". Journal of Combinatorial Theory, Series A. 43: 103–113. doi:10.1016/0097-3165(86)90028-2.
  13. ^ Kuperberg, Greg (1994). "Symmetries of plane partitions and the permanent-determinant method". Journal of Combinatorial Theory, Series A. 68: 115–151. doi:10.1016/0097-3165(94)90094-9. S2CID 14538036.
  14. ^ Mills, Robbins, Rumsey (1986). "Self-Complementary Totally Symmetric Plane Partitions". Journal of Combinatorial Theory, Series A. 42 (2): 277–292. doi:10.1016/0097-3165(86)90098-1.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  15. ^ Andrews, George E. (1994). "Plane Partitions V: The TSSCPP Conjecture". Journal of Combinatorial Theory, Series A. 66: 28–39. doi:10.1016/0097-3165(94)90048-5.
  16. ^ Richard P. Stanley, Enumerative Combinatorics, Volume 2. Corollary 7.20.3.
  17. ^ R.P. Stanley, Enumerative Combinatorics, Volume 2. pp. 365, 401–2.
  18. ^ E. M. Wright, Asymptotic partition formulae I. Plane partitions, The Quarterly Journal of Mathematics 1 (1931) 177–189.
  19. ^ L. Mutafchiev and E. Kamenov, "Asymptotic formula for the number of plane partitions of positive integers", Comptus Rendus-Academie Bulgare Des Sciences 59 (2006), no. 4, 361.
  20. ^ MacMahon, Major Percy A. (1916). "Combinatory Analysis". Chambridge: At the University Press. 2: §429.
  21. ^ MacMahon, Major Percy A. (1916). Combinatory Analysis. Chambridge: at the University Press. pp. §429, §494.
  22. ^ A. O. L. Atkin, P. Bratley, I. G. Macdonald and J. K. S. McKay, Some computations for m-dimensional partitions, Proc. Camb. Phil. Soc., 63 (1967), 1097–1100.
  23. ^ MacMahon, Percy Alexander (1899). "Partitions of numbers whose graphs possess symmetry". Transactions of the Cambridge Philosophical Society. 17.
  24. ^ Bender and Knuth (1972). "Enumeration of plane partitions". Journal of Combinatorial Theory, Series A. 13: 40–54. doi:10.1016/0097-3165(72)90007-6.
  25. ^ Andrews, George E. (1977). "Plane partitions II: The equivalence of the Bender-Knuth and MacMahon conjectures". Pacific Journal of Mathematics. 72 (2): 283–291. doi:10.2140/pjm.1977.72.283.
  26. ^ Andrews, George (1975). "Plane Partitions (I): The Mac Mahon Conjecture". Adv. Math. Suppl. Stud. 1.
  27. ^ Andrews, George E. (1977). "MacMahon's conjecture on symmetric plane partitions". Proceedings of the National Academy of Sciences. 74 (2): 426–429. doi:10.1073/pnas.74.2.426. PMC 392301. PMID 16592386.
  28. ^ Andrews, George E. (1979). "Plane Partitions(III): The Weak Macdonald Conjecture". Inventiones Mathematicae. 53 (3): 193–225. doi:10.1007/BF01389763. S2CID 122528418.
  29. ^ Mills, Robbins, Rumsey (1982). "Proof of the Macdonald conjecture". Inventiones Mathematicae. 66: 73–88. doi:10.1007/BF01404757. S2CID 120926391.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  30. ^ Stembridge, John R. (1995). "The Enumeration of Totally Symmetric Plane Partitions". Advances in Mathematics. 111 (2): 227–243. doi:10.1006/aima.1995.1023.
  31. ^ Andrews, Paule, Schneider (2005). "Plane Partitions VI: Stembridge's TSPP theorem". Advances in Applied Mathematics. 34 (4): 709–739. doi:10.1016/j.aam.2004.07.008.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  32. ^ Bressoud, David M. (1999). Proofs and Confirmations. Cambridge University Press. pp. conj. 13. ISBN 9781316582756.
  33. ^ a b Stanley, Richard P. (1970). "A baker's dozon of conjectures concering plane partitions". Combinatoire énumérative: 285–293.
  34. ^ Andrews, George (1980). "Totally symmetric plane partitions". Abstracts Amer. Math. Soc. 1: 415.
  35. ^ Koutschan, Kauers, Zeilberger (2011). "A proof of George Andrews' and David Robbins' q-TSPP conjecture". PNAS. 108 (6): 2196–2199. doi:10.1073/pnas.1019186108.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  36. ^ "Erratum". Journal of Combinatorial Theory. 43: 310. 1986.
  37. ^ Eisenkölbl, Theresia (2008). "A Schur function identity related to the (-1)-enumeration of self complementary plane partitions". Journal of Combinatorial Theory, Series A. 115: 199–212. doi:10.1016/j.jcta.2007.05.004.
  38. ^ Stanley, Richard P. (1971). "Theory and Application of Plane Partitions. Part 2". Advances in Applied Mathematics. 50: 259–279.
  39. ^ Kuperberg, Greg (1994). "Symmetries of plane partitions and the permanent-determinant method". Journal of Combinatorial Theory, Series A. 68: 115–151. doi:10.1016/0097-3165(94)90094-9. S2CID 14538036.
  40. ^ Mills, Robbins, Rumsey (1986). "Self-Complementary Totally Symmetric Plane Partitions". Journal of Combinatorial Theory, Series A. 42 (2): 277–292. doi:10.1016/0097-3165(86)90098-1.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  41. ^ Andrews, George E. (1994). "Plane Partitions V: The TSSCPP Conjecture". Journal of Combinatorial Theory, Series A. 66: 28–39. doi:10.1016/0097-3165(94)90048-5.