Nonintersecting paths, pfaffians, and plane partitions.(English)Zbl 0790.05007
Gessel and Viennot have developed a powerful technique for enumerating various classes of plane partitions. There are two fundamental ideas behind this technique. The first is the observation that most classes of plane partitions that are of interest—either by association with the representation theory of the classical groups, or for purely combinatorial reasons—can be interpreted as configurations of nonintersecting paths in a digraph (usually the lattice \(\mathbb{Z}^ 2)\). The second is the observation that the number of \(r\)-tuples of nonintersecting paths between two sets of \(r\) vertices can (often) be expressed as a determinant.
The purpose of this article is to show by similar means that one may use pfaffians to enumerate configurations of nonintersecting paths in which the initial and/or terminal vertices of the path are allowed to vary over specified regions of the digraph. This leads to the possibility of enumerating classes of plane partitions in which the shape is allowed to vary, whereas the previous applications of Gessel and Viennot were largely confined to plane partitions of a given shape.
We have made no attempt to catalogue all possible classes of plane partitions that one could enumerate by these techniques; rather, we have confined ourselves to providing new, simple, unified proofs of a diverse collection of known results, including identities of Gansner, Józefiak and Pragacz, Gordon, Gordon and Houten, Goulden, Lascoux and Pragacz, and Okada. In one instance, we give a new result; namely, a pfaffian for the number of totally symmetric, self-complementary plane partitions. It seems likely that the number of plane partitions belonging to the other symmetry classes for which there are only conjectured formulas could also be expressed as pfaffians. We will not pursue this further here, except to note that Okada has already done this for the totally symmetric case.
The purpose of this article is to show by similar means that one may use pfaffians to enumerate configurations of nonintersecting paths in which the initial and/or terminal vertices of the path are allowed to vary over specified regions of the digraph. This leads to the possibility of enumerating classes of plane partitions in which the shape is allowed to vary, whereas the previous applications of Gessel and Viennot were largely confined to plane partitions of a given shape.
We have made no attempt to catalogue all possible classes of plane partitions that one could enumerate by these techniques; rather, we have confined ourselves to providing new, simple, unified proofs of a diverse collection of known results, including identities of Gansner, Józefiak and Pragacz, Gordon, Gordon and Houten, Goulden, Lascoux and Pragacz, and Okada. In one instance, we give a new result; namely, a pfaffian for the number of totally symmetric, self-complementary plane partitions. It seems likely that the number of plane partitions belonging to the other symmetry classes for which there are only conjectured formulas could also be expressed as pfaffians. We will not pursue this further here, except to note that Okada has already done this for the totally symmetric case.
MSC:
| 05A15 | Exact enumeration problems, generating functions |
| 05A17 | Combinatorial aspects of partitions of integers |
| 05A19 | Combinatorial identities, bijective combinatorics |
| 05E10 | Combinatorial aspects of representation theory |
| 11P83 | Partitions; congruences and congruential restrictions |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C38 | Paths and cycles |
Cite
References:
| [1] | Andrews, G. E., Plane partitions (I): The MacMahon conjecture, (Studies in Foundations and Combinatorics. Studies in Foundations and Combinatorics, Adv. in Math. Suppl. Stud., Vol. 1 (1978), Academic Press: Academic Press New York), 131-150 ·Zbl 0462.10010 |
| [2] | Bender, E. A.; Knuth, D. E., Enumeration of plane partitions, J. Combin. Theory Ser. A, 13, 40-54 (1972) ·Zbl 0246.05010 |
| [3] | Désarménien, J., Une généralisation des formules de Gordon et de MacMahon, C. R. Acad. Sci. Paris Sér. I Math., 309, 269-272 (1989) ·Zbl 0721.05007 |
| [4] | W. F. Doran;W. F. Doran ·Zbl 0795.05008 |
| [5] | Egẽciog̃lu, Ö. N.; Remmel, J. B., A combinatorial proof of the Giambelli identity for Schur functions, Adv. in Math., 70, 59-86 (1988) ·Zbl 0659.05006 |
| [6] | Gansner, E. R., The Hillman-Grassl correspondence and the enumeration of reverse plane partitions, J. Combin. Theory Ser. A, 30, 71-89 (1981) ·Zbl 0474.05008 |
| [7] | Gessel, I. M., Symmetric functions and \(P\)-recursiveness, J. Combin. Theory Ser. A, 53, 257-285 (1990) ·Zbl 0704.05001 |
| [8] | Gessel, I. M.; Viennot, G., Binomial determinants, paths, and hook length formulae, Adv. in Math., 58, 300-321 (1985) ·Zbl 0579.05004 |
| [9] | I. M. Gessel and G. Viennot;I. M. Gessel and G. Viennot ·Zbl 0579.05004 |
| [10] | Gordon, B.; Houten, L., Notes on plane partitions II, J. Combin. Theory, 4, 81-99 (1968) ·Zbl 0153.32803 |
| [11] | Gordon, B., Notes on plane partitions V, J. Combin. Theory Ser. B, 11, 157-168 (1971) ·Zbl 0245.05006 |
| [12] | Gordon, B., A proof of the Bender-Knuth conjecture, Pacific J. Math., 108, 99-113 (1983) ·Zbl 0533.05005 |
| [13] | I. P. GouldenDiscrete Math.;I. P. GouldenDiscrete Math. ·Zbl 0782.05087 |
| [14] | T. Józefiak and P. Pragacz\(Q\);T. Józefiak and P. Pragacz\(Q\) |
| [15] | King, R. C., Modification rules and products of irreducible representations of the unitary, orthogonal, and symplectic groups, J. Math. Phys., 12, 1588-1598 (1971) ·Zbl 0239.20061 |
| [16] | Koike, K.; Terada, I., Young diagrammatic methods for the representation theory of the classical groups of type \(B_n, C_{n\) ·Zbl 0622.20033 |
| [17] | Lascoux, A.; Pragacz, P., Équerres et fonctions de Schur, C. R. Acad. Sci. Paris Sér. Math. I, 299, 955-958 (1984) ·Zbl 0579.05012 |
| [18] | Lindström, B., On the vector representations of induced matroids, Bull. London Math. Soc., 5, 85-90 (1973) ·Zbl 0262.05018 |
| [19] | Littlewood, D. E., On certain symmetric functions, Proc. London Math. Soc., 11, 3, 485-498 (1961) ·Zbl 0099.25102 |
| [20] | Macdonald, I. G., Symmetric Functions and Hall Polynomials (1979), Oxford Univ. Press: Oxford Univ. Press Oxford ·Zbl 0487.20007 |
| [21] | Mills, W. H.; Robbins, D. P.; Rumsey, H., Self-complementary totally symmetric plane partitions, J. Combin. Theory Ser. A, 42, 277-292 (1986) ·Zbl 0615.05011 |
| [22] | Okada, S., On the generating functions for certain classes of plane partitions, J. Combin. Theory Ser. A, 51, 1-23 (1989) ·Zbl 0678.05003 |
| [23] | R. A. ProctorEurop. J. Combin.;R. A. ProctorEurop. J. Combin. ·Zbl 0726.05008 |
| [24] | R. A. Proctor;R. A. Proctor ·Zbl 0809.20030 |
| [25] | Sagan, B. E., Enumeration of partitions with hooklengths, European J. Combin., 3, 85-94 (1982) ·Zbl 0483.05010 |
| [26] | Sagan, B. E., Shifted tableaux, Schur \(Q\)-functions and a conjecture of R. Stanley, J. Combin. Theory Ser. A, 45, 62-103 (1987) ·Zbl 0661.05010 |
| [27] | de Sainte-Catherine, M.; Viennot, G., Enumeration of certain Young tableaux with bounded height, (Labelle, G.; Leroux, P., Combinatoire Énumérative. Combinatoire Énumérative, Lecture Notes in Mathematics, Vol. 1234 (1985), Springer-Verlag: Springer-Verlag Berlin), 58-67 ·Zbl 0615.05009 |
| [28] | Schur, I., Über die Darstellung der symmetrischen und der alternierenden Gruppe durch gebrochene lineare Substitutionen, J. Reine Angew. Math., 139, 155-250 (1911) ·JFM 42.0154.02 |
| [29] | Stanley, R. P., Ordered structures and partitions, Mem. Amer. Math. Soc., 119 (1972) ·Zbl 0246.05007 |
| [30] | Stanley, R. P., (Enumerative Combinatorics, Vol. I (1986), Wadsworth: Wadsworth Monterey, CA) ·Zbl 0608.05001 |
| [31] | Stanley, R. P., Symmetries of plane partitions, J. Combin. Theory Ser. A, 43, 103-113 (1986) ·Zbl 0602.05007 |
| [32] | Stembridge, J. R., Shifted tableaux and the projective representations of symmetric groups, Adv. in Math., 74, 87-134 (1989) ·Zbl 0677.20012 |
| [33] | J. R. StembridgeTrans. Amer. Math. Soc.;J. R. StembridgeTrans. Amer. Math. Soc. ·Zbl 0707.05006 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
