A Rogers-Ramanujan bijection

In this paper we give a bijection between the partitions of n with parts congruent to 1 or 4 (mod 5) and the partitions of n with parts differing by at least 2. This bijection is obtained by a cut-and-paste procedure which starts with a partition in one class and ends with a partition in the other class. The whole construction is a combination of a bijection discovered quite early by Schur and two bijections of our own. A basic principle concerning pairs of involutions provides the key for connecting all these bijections. It appears that our methods lead to an algorithm for constructing bijections for other identities of Rogers-Ramanujan type such as the Gordon identities.     

Euler's partition theorem and the combinatorics of ℓ-sequences

Euler's partition theorem states that the number of partitions of an integer N into odd parts is equal to the number of partitions of N in which the ratio of successive parts is greater than 1. It was shown by Bousquet-Mélou and Eriksson in [M. Bousquet-Mélou, K. Eriksson, Lecture hall partitions II, Ramanujan J. 1 (2) (1997) 165–185] that a similar result holds when “odd parts” is replaced by “parts that are sums of successive terms of an ℓ-sequence” and the ratio “1” is replaced by a root of the characteristic polynomial of the ℓ-sequence. This generalization of Euler's theorem is intrinsically different from the many others that have appeared, as it involves a family of partitions constrained by the ratio of successive parts.In this paper, we provide a surprisingly simple bijection for this result, a question suggested by Richard Stanley. In fact, we give a parametrized family of bijections, that include, as special cases, Sylvester's bijection and a bijection for the lecture hall theorem. We introduce Sylvester diagrams as a way to visualize these bijections and deduce their properties.In proving the bijections, we uncover the intrinsic role played by the combinatorics of ℓ-sequences and use this structure to give a combinatorial characterization of the partitions defined by the ratio constraint. Several open questions suggested by this work are described.     

Balanced partitions

A famous theorem of Euler asserts that there are as many partitions of n into distinct parts as there are partitions into odd parts. We begin by establishing a less well-known companion result, which states that both of these quantities are equal to the number of partitions of n into even parts along with exactly one triangular part. We then introduce the characteristic of a partition, which is determined in a simple way by the placement of odd parts within the list of all parts. This leads to a refinement of the aforementioned result in the form of a new type of partition identity involving characteristic, distinct parts, even parts, and triangular numbers. Our primary purpose is to present a bijective proof of the central instance of this new type of identity, which concerns balanced partitions—partitions in which odd parts occupy as many even as odd positions within the list of all parts. The bijection is accomplished by means of a construction that converts balanced partitions of 2n into unrestricted partitions of n via a pairing of the squares in the Young tableau.     

Cranks andt-cores

Summary New statistics on partitions (calledcranks) are defined which combinatorially prove Ramanujan's congruences for the partition function modulo 5, 7, 11, and 25. Explicit bijections are given for the equinumerous crank classes. The cranks are closely related to thet-core of a partition. Usingq-series, some explicit formulas are given for the number of partitions which aret-cores. Some related questions for self-conjugate and distinct partitions are discussed.This work was partially supported by NSF grant DMS: 8700995Oblatum 16-IX-1989     

A symmetrical plane partition correspondence

MacMahon conjectured the form of the generating function for symmetrical plane partitions, and as a special case deduced the following theorem. The set of partitions of a number n whose part magnitude and number of parts are both no greater than m is equinumerous with the set of symmetrical plane partitions of 2n whose part magnitude does not exceed 2 and whose largest axis does not exceed m. This theorem, together with a companion theorem for the symmetrical plane partitions of odd numbers, are proved by establishing 1-1 correspondences between the sets of partitions.     

Parity in partition identities

This paper considers a variety of parity questions connected with classical partition identities of Euler, Rogers, Ramanujan and Gordon. We begin by restricting the partitions in the Rogers-Ramanujan-Gordon identities to those wherein even parts appear an even number of times. We then take up questions involving sequences of alternating parity in the parts of partitions. This latter study leads to: (1) a bi-basic q-binomial theorem and q-binomial series, (2) a new interpretation of the Rogers-Ramanujan identities, and (3) a new natural interpretation of the fifth-order mock theta functions f ₀(q) along with a new proof of the Hecke-type series representation.     

A continuous family of partition statistics equidistributed with length

This article investigates a remarkable generalization of the generating function that enumerates partitions by area and number of parts. This generating function is given by the infinite product _∏i?11/(1−tqi). We give uncountably many new combinatorial interpretations of this infinite product involving partition statistics that arose originally in the context of Hilbert schemes. We construct explicit bijections proving that all of these statistics are equidistributed with the length statistic on partitions of n. Our bijections employ various combinatorial constructions involving cylindrical lattice paths, Eulerian tours on directed multigraphs, and oriented trees.     

Some sieves for partition theory

A Combinatorial lemma due to Zolnowsky is applied to partition theory in a new way. Several even-odd formulas are derived. A combinatorial proof of the Jacobi triple-product identity is given. Some sieve formulas are proved which relate to the Euler pentagonal number theorem and the Rogers-Ramanujan identities and their generalizations. A formula is given for the number of partitions of n into parts not congruent to 0, ±x (mod y).     

Weighted forms of Euler's theorem

In answer to a question of Andrews about finding combinatorial proofs of two identities in Ramanujan's “lost” notebook, we obtain weighted forms of Euler's theorem on partitions with odd parts and distinct parts. This work is inspired by the insight of Andrews on the connection between Ramanujan's identities and Euler's theorem. Our combinatorial formulations of Ramanujan's identities rely on the notion of rooted partitions. Pak's iterated Dyson's map and Sylvester's fish-hook bijection are the main ingredients in the weighted forms of Euler's theorem.     

Enumeration of M-partitions

An M-partition of a positive integer m is a partition of m with as few parts as possible such that every positive integer less than m can be written as a sum of parts taken from the partition. This type of partition is a variation of MacMahon's perfect partition, and was recently introduced and studied by O’Shea, who showed that for half the numbers m, the number of M-partitions of m is equal to the number of binary partitions of 2ⁿ⁺¹-1-m, where . In this note we extend O’Shea's result to cover all numbers m.     

On the weighted enumeration of alternating sign matrices and descending plane partitions

We prove a conjecture of Mills, Robbins and Rumsey [Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A 34 (3) (1983) 340-359] that, for any n, k, m and p, the number of n×n alternating sign matrices (ASMs) for which the 1 of the first row is in column k+1 and there are exactly m −1?s and m+p inversions is equal to the number of descending plane partitions (DPPs) for which each part is at most n and there are exactly k parts equal to n, m special parts and p nonspecial parts. The proof involves expressing the associated generating functions for ASMs and DPPs with fixed n as determinants of n×n matrices, and using elementary transformations to show that these determinants are equal. The determinants themselves are obtained by standard methods: for ASMs this involves using the Izergin-Korepin formula for the partition function of the six-vertex model with domain-wall boundary conditions, together with a bijection between ASMs and configurations of this model, and for DPPs it involves using the Lindström-Gessel-Viennot theorem, together with a bijection between DPPs and certain sets of nonintersecting lattice paths.     

Symmetries on the Lattice of <Emphasis Type="Italic">k</Emphasis>-Bounded Partitions

In 2002, Suter [25] identified a dihedral symmetry on certain order ideals in Young’s lattice and gave a combinatorial action on the partitions in these order ideals. Viewing this result geometrically, the order ideals can be seen to be in bijection with the alcoves in a 2- fold dilation in the geometric realization of the affine symmetric group. By considering the m-fold dilation we observe a larger set of order ideals in the k-bounded partition lattice that was considered by Lapointe, Lascoux, and Morse [14] in the study of k-Schur functions. We identify the order ideal and the cyclic action on it explicitly in a geometric and combinatorial form.     

A Note on Partitions into Distinct Parts and Odd Parts

Bousquet-Mélou and Eriksson showed that the number of partitions of n into distinct parts whose alternating sum is k is equal to the number of partitions of n into k odd parts, which is a refinement of a well-known result by Euler. We give a different graphical interpretation of the bijection by Sylvester on partitions into distinct parts and partitions into odd parts, and show that the bijection implies the above statement.     

On flushed partitions and concave compositions

In this work, we give combinatorial proofs for generating functions of two problems, i.e., flushed partitions and concave compositions of even length. We also give combinatorial interpretation of one problem posed by Sylvester involving flushed partitions and then prove it. For these purposes, we first describe an involution and use it to prove core identities. Using this involution with modifications, we prove several problems of different nature, including Andrews’ partition identities involving initial repetitions and partition theoretical interpretations of three mock theta functions of third order f(q), ?(q) and ψ(q). An identity of Ramanujan is proved combinatorially. Several new identities are also established.     

New bijective links on planar maps via orientations

This article presents new bijections on planar maps. At first a bijection is established between bipolar orientations on planar maps and specific “transversal structures” on triangulations of the 4-gon with no separating 3-cycle, which are called irreducible triangulations. This bijection specializes to a bijection between rooted non-separable maps and rooted irreducible triangulations. This yields in turn a bijection between rooted loopless maps and rooted triangulations, based on the observation that loopless maps and triangulations are decomposed in a similar way into components that are respectively non-separable maps and irreducible triangulations. This gives another bijective proof (after Wormald’s construction published in 1980) of the fact that rooted loopless maps with n edges are equinumerous to rooted triangulations with n inner vertices.     

A bijection of the set of 3-regular partitions

A bijection of the set of 3-regular partitions of an integer n is constructed. It is shown that this map has order 2 and that the 3-cores of a partition and its image have diagrams which are mutual transposes. It is conjectured that this is the same bijection as the one induced, using the labeling of Farahat, Müller, and Peel, from the action of the alternating character upon the 3-modular irreducible representations of the symmetric group of degree n.     

Com plete p-elli ptic integrals and a com putation formula of $$\ pi _ p$$π p for $$ p=4$$ p=4

We study the q-bracket operator of Bloch and Okounkov, recently examined by Zagier and other authors, when applied to functions defined by two classes of sums over the parts of an integer partition. We derive convolution identities for these functions and link both classes of q-brackets through divisor sums. As a result, we generalize Euler’s classic convolution identity for the partition function and obtain an analogous identity for the totient function. As corollaries, we generalize Stanley’s Theorem on the number of ones in all partitions of n, and provide several new combinatorial results.     

Bijective proofs of some classical partition identities

A bijective proof of a general partition theorem is given which has as direct corollaries many classical partition theorems due to Euler, Glaisher, Schur, Andrews, Subbarao, and others. It is shown that the bijective proof specializes to give bijective proofs of these classical results and moreover the bijections which result often coincide with bijections which have occurred in the literature. Also given are some sufficient conditions for when two classes of words omitting certain sequences of words are in bijection.     

Multiple partitions, lattice paths and a Burge-Bressoud-type correspondence

A bijection is presented between (1): partitions with conditions f_j+f_j+1≤k−1 and f₁≤i−1, where f_j is the frequency of the part j in the partition, and (2): sets of k−1 ordered partitions (n⁽¹⁾,n⁽²⁾,…,n^(k−1)) such that and , where m_j is the number of parts in n^(j). This bijection entails an elementary and constructive proof of the Andrews multiple-sum enumerating partitions with frequency conditions. A very natural relation between the k−1 ordered partitions and restricted paths is also presented, which reveals our bijection to be a modification of Bressoud’s version of the Burge correspondence.     

Permutation tableaux and permutation patterns

In this paper we introduce and study a class of tableaux which we call permutation tableaux; these tableaux are naturally in bijection with permutations, and they are a distinguished subset of the -diagrams of Alex Postnikov [A. Postnikov, Webs in totally positive Grassmann cells, in preparation; L. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005) 319-342]. The structure of these tableaux is in some ways more transparent than the structure of permutations; therefore we believe that permutation tableaux will be useful in furthering the understanding of permutations. We give two bijections from permutation tableaux to permutations. The first bijection carries tableaux statistics to permutation statistics based on relative sizes of pairs of letters in a permutation and their places. We call these statistics weak excedance statistics because of their close relation to weak excedances. The second bijection carries tableaux statistics (via the weak excedance statistics) to statistics based on generalized permutation patterns. We then give enumerative applications of these bijections. One nice consequence of these results is that the polynomial enumerating permutation tableaux according to their content generalizes both Carlitz' q-analog of the Eulerian numbers [L. Carlitz, q-Bernoulli and Eulerian numbers, Trans. Amer. Math. Soc. 76 (1954) 332-350] and the more recent q-analog of the Eulerian numbers found in [L. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005) 319-342]. We conclude our paper with a list of open problems, as well as remarks on progress on these problems which has been made by A. Burstein, S. Corteel, N. Eriksen, A. Reifegerste, and X. Viennot.