A bijective proof of the generating function for the number of reverse plane partitions via lattice paths

Recently, Hillman and Grassl gave a bijective proof for the generating function for the number of reverse plane partitions of a fixed shape λ. We give another bijective proof for this generating function via completelv different methods. Our bijection depends on a lattice path coding of reverse plane partitions and a new method for constructing bisections out of certain pairs of involutions due to Garsia and Milne.     

A bijective proof of Kadell's conjecture on plane partitions

We give a weight-preserving bijection from _{r, µ} ^m to, where _{r, µ} ^m is the set of all plane partitions whose entries are m and whose entries below ther-th row form a column strict plane partition of type, and _µ ^m the set of all column strict plane partitions of type whose entries are m, and the set of all plane partitions with at mostr rows, whose entries are m. This confirms a conjecture of Kadell.     

Enumeration of lattice paths and generating functions for skew plane partitions

n-dimensional lattice paths not touching the hyperplanesX _i–X _i+1=–1,i=1,2,...,n, are counted by four different statistics, one of which is MacMahon's major index. By a reflection-like proof, heavily relying on Zeilberger's (Discrete Math. 44(1983), 325–326) solution of then-candidate ballot problem, determinantal expressions are obtained. As corollaries the generating functions for skew plane partitions, column-strict skew plane partitions, reverse skew plane plane partitions and column-strict reverse skew plane partitions, respectively, are evaluated, thus establishing partly new results, partly new proofs for known theorems in the theory of plane partitions.     

An almost‐bijective proof of an asymptotic property of partitions

Let 𝒫_n be the set of all distinct ordered pairs (λ,λ_i), where λ is a partition of n and λ_i is a part size of λ. The primary result of this note is a combinatorial proof that the probability that, for a pair (λ,λ_i) chosen uniformly at random from 𝒫_n, the multiplicity of λ_i in λ is 1 tends to 1/2 as n →∞. This is inspired by work of Corteel, Pittel, Savage, and Wilf (Random Structures and Algorithms 14 (1999), 185–197). © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

A bijective proof of Jackson's formula for the number of factorizations of a cycle

Factorizations of the cyclic permutation into two permutations with respectively n and m cycles, or, equivalently, unicellular bicolored maps with N edges and n white and m black vertices, have been enumerated independantly by Jackson and Adrianov using evaluations of characters of the symmetric group. In this paper we present a bijection between unicellular partitioned bicolored maps and couples made of an ordered bicolored tree and a partial permutation, that allows for a combinatorial derivation of these results.Our work is closely related to a recent construction of Goulden and Nica for the celebrated Harer-Zagier formula, and indeed we provide a unified presentation of both bijections in terms of Eulerian tours in graphs.     

A bijective proof of the hook-length formula for skew shapes

Recently, Naruse presented a beautiful cancellation-free hook-length formula for skew shapes. The formula involves a sum over objects called excited diagrams, and the term corresponding to each excited diagram has hook lengths in the denominator, like the classical hook-length formula due to Frame, Robinson and Thrall. In this paper, we present a simple bijection that proves an equivalent recursive version of Naruse’s result, in the same way that the celebrated hook-walk proof due to Greene, Nijenhuis and Wilf gives a bijective (or probabilistic) proof of the hook-length formula for ordinary shapes.In particular, we also give a new bijective proof of the classical hook-length formula, quite different from the known proofs.     

A bijective proof of the hook-length formula

A well-known theorem of Frame, Robinson, and, Thrall states that if λ is a partition of n, then the number of Standard Young Tableaux of shape λ is n! divided by the product of the hook-lengths. We give a new combinatorial proof of this formula by exhibiting a bijection between the set of unsorted Young Tableaux of shape λ, and the set of pairs (T, S), where T is a Standard Young Tableau of shape λ and S is a “Pointer” Tableau of shape λ.     

A bijective proof of an identity for noncrossing graphs

We give a bijective proof for the identity a_n+2=8b_n, where a_n is the number of noncrossing simple graphs with n (possibly isolated) vertices and b_n is the number of noncrossing graphs without isolated vertices and with n (possibly multiple) edges.     

The Hillman-Grassl correspondence and the enumeration of reverse plane partitions

Hillman and Grassl have devised a correspondence between reverse plane partitions and nonnegative integer arrays of the same shape that allowed them to easily enumerate reverse plane partitions and provided a combinatorial connection between hook lengths and plane partitions. In this work, a collection of properties of this correspondence are presented, including two characterizations that relate this map to the familiar Schensted-Knuth correspondence. These properties are used to derive simple expressions for the generating functions of reverse plane partitions and symmetric reverse plane partitions with respect to sums along the diagonals. Equally general results are obtained for shifted reverse plane partitions using a new type of hook, thereby proving a conjecture of Stanley.     

Enumeration of strings in Dyck paths: A bijective approach

The statistics concerning the number of appearances of a string τ in Dyck paths as well as its appearances in odd and even level have been studied extensively by several authors using mostly algebraic methods. In this work a different, bijective approach is followed giving some known as well as some new results.     

A bijective proof of the Jacobi identity and reconstruction of Young diagrams

A short combinatorial proof is given of the classical Jacobi identity from the theory of theta-functions.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 155, pp. 3–6, 1986.     

On the number of primitive lattice points in plane domains

We discuss the error term in the asymptotic formula for the number of integral points with coprime coordinates in star like plane domains assuming the validity of the Riemann Hypothesis.     

The number of lattice paths below a cyclically shifting boundary

We count the number of lattice paths lying under a cyclically shifting piecewise linear boundary of varying slope. Our main result can be viewed as an extension of well-known enumerative formulae concerning lattice paths dominated by lines of integer slope (e.g. the generalized ballot theorem). Its proof is bijective, involving a classical “reflection” argument. Moreover, a straightforward refinement of our bijection allows for the counting of paths with a specified number of corners. We also show how the result can be applied to give elegant derivations for the number of lattice walks under certain periodic boundaries. In particular, we recover known expressions concerning paths dominated by a line of half-integer slope, and some new and old formulae for paths lying under special “staircases.”     

THE MAXIMUM NUMBER OF INTERSECTIONS BETWEEN TWO PLANE RECTANGULAR PATHS

We show that the maximum number of intersections between two plane rectangular paths with lengths m and n: 2 ≤ m ≤ n, is 4n 2, if m=4 and n≡1(mod 3); and it is mn 1 otherwise.