Search

In this article, we introduce some identities obtained from the inner products of some symmetric polynomials including the Macdonald polynomials. These identities are obtained not only from the inner products, but also by constructing certain bijections. The bijections are constructed through transforming the Young diagrams of partitions.

We characterize the palindromic generalized Riordan arrays and their Sheffer sequences showing that, apart from a trivial case, these arrays all arise from a given array P ( q , t , u ) by suitably choosing the parameters q , t , u . Remarkably, well-known polynomial and numerical sequences arise as special cases of such Sheffer sequences, including classical orthogonal polynomials. After a suitable normalization, both the palindromic Sheffer sequences and their gamma polynomials have non-negative integer coefficients. We prove that these coefficients count a family of directed graphs, then through this combinatorial setting we obtain a bijective proof of the palindromic property of P ( q , t , u ) , and we recover the combinatorial expansion of orthogonal polynomials due to F. Bergeron. Finally, we state explicit connections between the inverse Q ( q , t , u ) of P ( q , t , u ) and an array C ( q , t ) which generalizes Aigner's array of ballot numbers, the Pascal triangle and the Catalan triangle of Shapiro.

Edelman and Greene generalized the Robinson--Schensted--Knuth correspondence to reduced words in order to give a bijective proof of the Schur positivity of Stanley symmetric functions. Stanley symmetric functions may be regarded as the stable limits of Schubert polynomials, and similarly Schur functions may be regarded as the stable limits of Demazure characters for the general linear group. We modify the Edelman--Greene correspondence to give an analogous, explicit formula for the Demazure character expansion of Schubert polynomials. Our techniques utilize dual equivalence and its polynomial variation, but here we demonstrate how to extract explicit formulas from that machinery which may be applied to other positivity problems as well.

This paper is the 2nd in a series of planned papers that provide 1st bijective proofs of alternating sign matrix (ASM) results. Based on the main result from the 1st paper, we construct a bijective proof of the enumeration formula for ASMs and of the fact that ASMs are equinumerous with descending plane partitions. We are also able to refine these bijections by including the position of the unique $1$ in the top row of the matrix. Our constructions rely on signed sets and related notions. The starting point for these constructions were known “computational” proofs, but the combinatorial point of view led to several drastic modifications. We also provide computer code where all of our constructions have been implemented.

By using the generating tree technique and the obstinate kernel method, Kim and Lin confirmed a conjecture due to Martinez and Savage which asserts that inversion sequences e = ( e 1 , e 2 , … , e n ) containing no three indices i j k such that e i ≥ e j , e j ≥ e k and e i > e k are counted by Baxter numbers. In this paper, we provide a bijective proof of this conjecture via an intermediate structure of open partition diagrams, in answer to a problem posed by Beaton-Bouvel-Guerrini-Rinaldi. Moreover, we show that two new classes of pattern-avoiding inversion sequences are also counted by Baxter numbers.

In 2013, Bringmann and Mahlburg defined a new type of partitions by adding a different restriction on the smallest parts in Gleissberg’s generalization of partitions considered by Schur. The generating function of this new Schur-type partitions is a mixed mock modular form, more precisely, it equals the product of the generating function of Gleissberg’s generalization and a specialization of a universal mock theta function $$g_3(x;q)$$ , where $$g_3(x;q)$$ is Hickerson’s universal mock theta function of odd order. Gordon and McIntosh also found a second universal mock theta function of even order $$g_2(x;q)$$ . To give an analogue of Bringmann and Mahlburg’s result of these two Schur-type identities, with respect to $$g_2(x;q)$$ , Bringmann, Lovejoy and Mahlburg investigated two kinds of overpartitions and obtained two overpartition theorems which can be viewed as the overpartition analogues of Gleissberg’s generalization and Bringmann and Mahlburg’s theorem. The quotient of the generating functions of these two kinds of overpartitions is a specialization of $$g_2(x;q)$$ . At the end of their article, Bringmann et al. asked for a bijective proof of their first theorem. In this paper, we construct a bijection by employing the d-modular Ferrers diagram to prove their first theorem and also derive a new bi-parameter generating function for the second set of overpartitions. By this new generating function and a $$_3\phi _2$$ transformation, we rediscover their second identity and a corollary. Inspired by a generalization of Schur’s theorem due to Andrews, we also give a generalization of Bringmann et al.’s first theorem which extends r, $$d-r$$ to an integer set A and the modulus from 2d to td.

In the study of a cocommutative Hopf algebra PFSym built on parking functions, the author presented two free generating sets of PFSym which are indexed by atomic parking functions and unsplitable parking functions. The notions of atomic parking function and unsplitable parking function are introduced via two binary operations called the slash product and the split product respectively. It follows that the set of atomic parking functions of length n is equinumerous with the set of unsplitable parking functions of length n. In this paper, we will give a bijective proof of this fact in the more general setting of endofunctions. We generalize the slash product and the split product to endofunctions, and then propose the notions of atomic endofunction and unsplitable endofunction. We show that this leads to two free monoid structures on endofunctions, whose free generators are atomic endofunctions and unsplitable endofunctions respectively. Moreover, it is shown that for each $$n\ge 1$$, the set of atomic endofunctions of length n is in bijection with the set of unsplitable endofunctions of length n.

In 1986, Shi derived the famous formula $(n+1)^{n-1}$ for the number of regions of the Shi arrangement, a hyperplane arrangement in $\mathbb{R}^n$. There are at least two different bijective explanations of this formula, one by Pak and Stanley, another by Athanasiadis and Linusson. In 1996, Athanasiadis used the finite field method to derive a formula for the number of $k$-dimensional faces of the Shi arrangement for any $k$. Until now, the formula of Athanasiadis did not have a bijective explanation. In this paper, we extend a bijection for regions defined by Bernardi to obtain a bijection between the $k$-dimensional faces of the Shi arrangement for any $k$ and a set of decorated binary trees. Furthermore, we show how these trees can be converted to a simple set of functions of the form $f: [n-1] \to [n+1]$ together with a marked subset of $\text{Im}(f)$. This correspondence gives the first bijective proof of the formula of Athanasiadis. In the process, we also obtain a bijection and counting formula for the faces of the Catalan arrangement. All of our results generalize to both extended arrangements., Comment: 45 pages, 13 figures

The Murnaghan–Nakayama rule is a combinatorial rule for the character values of symmetric groups. We give a new combinatorial proof by explicitly finding the trace of the representing matrices in the standard basis of Specht modules. This gives an essentially bijective proof of the rule. A key lemma is an extension of a straightening result proved by the second author to skew tableaux. Our module theoretic methods also give short proofs of Pieri’s rule and Young’s rule.

A famous theorem of Euler asserts that there are as many partitions of n into distinct parts as there are partitions into odd parts. The even parts in partitions of n into distinct parts play an important role in the Euler–Glaisher bijective proof of this result. In this paper, we investigate the number of even parts in all partitions of n into distinct parts providing new combinatorial interpretations for this number.

The Fibonacci cube of dimension n, denoted as $$\Gamma _n$$ , is the subgraph of the hypercube induced by vertices with no consecutive 1s. The Lucas cube $$\Lambda _n$$ is the cyclic version of $$\Gamma _n$$ . The irregularity of a graph G is the sum of $$|d(x)-d(y)|$$ over all edges $$\{x,y\}$$ of G. In two recent papers based on the recursive structure of $$\Gamma _n$$ , it is proved that the irregularity of $$\Gamma _n$$ and $$\Lambda _n$$ is two times the number of edges of $$\Gamma _{n-1}$$ and 2n times the number of vertices of $$\Gamma _{n-4}$$ , respectively. Using an interpretation of the irregularity in terms of couples of incident edges of a special kind, we give a bijective proof of both results. For these two graphs, we deduce also a constant time algorithm for computing the imbalance of an edge. In the last section using the same approach, we determine the number of edges and the sequence of degrees of the cube complement of $$\Gamma _n$$ .

We launch a systematic study of the refined Wilf-equivalences by the statistics $\mathsf{comp}$ and $\mathsf{iar}$, where $\mathsf{comp}(\pi)$ and $\mathsf{iar}(\pi)$ are the number of components and the length of the initial ascending run of a permutation $\pi$, respectively. As Comtet was the first one to consider the statistic $\mathsf{comp}$ in his book {\em Analyse combinatoire}, any statistic equidistributed with $\mathsf{comp}$ over a class of permutations is called by us a {\em Comtet statistic} over such class. This work is motivated by a triple equidistribution result of Rubey on $321$-avoiding permutations, and a recent result of the first and third authors that $\mathsf{iar}$ is a Comtet statistic over separable permutations. Some highlights of our results are: (1) Bijective proofs of the symmetry of the double Comtet distribution $(\mathsf{comp},\mathsf{iar})$ over several Catalan and Schr\"oder classes, preserving the values of the left-to-right maxima. (2) A complete classification of $\mathsf{comp}$- and $\mathsf{iar}$-Wilf-equivalences for length $3$ patterns and pairs of length $3$ patterns. Calculations of the $(\mathsf{des},\mathsf{iar},\mathsf{comp})$ generating functions over these pattern avoiding classes and separable permutations. (3) A further refinement by the Comtet statistic $\mathsf{iar}$, of Wang's recent descent-double descent-Wilf equivalence between separable permutations and $(2413,4213)$-avoiding permutations., Comment: 39 pages, 2 tables, 2 figures. Comments are welcome

We describe a bijective proof of Macdonald's reduced word identity using pipe dreams and Little's bumping algorithm. The proof extends to a principal specialization of the identity due to Fomin and Stanley. Our bijective tools also allow us to address a problem posed by Fomin and Kirillov from 1997, using work of Wachs, Lenart and Serrano- Stump.

In this paper, we introduce therhombic alternative tableaux, whose weight generating functions providecombinatorial formulae to compute the steady state probabilities of the two-species ASEP. In the ASEP, there aretwo species of particles, oneheavyand onelight, on a one-dimensional finite lattice with open boundaries, and theparametersα,β, andqdescribe the hopping probabilities. The rhombic alternative tableaux are enumerated by theLah numbers, which also enumerate certainassembl ́ees of permutations. We describe a bijection between the rhombicalternative tableaux and these assembl ́ees. We also provide an insertion algorithm that gives a weight generatingfunction for the assemb ́ees. Combined, these results give a bijective proof for the weight generating function for therhombic alternative tableaux.

Reiner–Stanton–White (Reiner et al., 2004) defined the cyclic sieving phenomenon (CSP) associated to a finite cyclic group action and a polynomial. A key example arises from the length generating function for minimal length coset representatives of a parabolic quotient of a finite Coxeter group. In type A , this result can be phrased in terms of the natural cyclic action on words of fixed content. There is a natural notion of refinement for many CSP’s. We formulate and prove a refinement, with respect to the major index statistic, of this CSP on words of fixed content by also fixing the cyclic descent type. The argument presented is completely different from Reiner–Stanton–White’s representation-theoretic approach. It is combinatorial and largely, though not entirely, bijective in a sense we make precise with a “universal” sieving statistic on words, flex. A building block of our argument involves cyclic sieving for shifted subset sums, which also appeared in Reiner–Stanton–White. We give an alternate, largely bijective proof of a refinement of this result by extending some ideas of Wagon–Wilf (Wagon and Wilf, 1994).

Amdeberhan conjectured that the number of ( s , s + 2 ) -core partitions with distinct parts for an odd integer s is 2 s − 1 . This conjecture was first proved by Yan, Qin, Jin and Zhou, then subsequently by Zaleski and Zeilberger. Since the formula for the number of such core partitions is so simple one can hope for a bijective proof. We give the first direct bijective proof of this fact by establishing a bijection between the set of ( s , s + 2 ) -core partitions with distinct parts and a set of lattice paths.

Set partitions avoiding $k$-crossing and $k$-nesting have been extensively studied from the aspects of both combinatorics and mathematical biology. By using the generating tree technique, the obstinate kernel method and Zeilberger's algorithm, Lin confirmed a conjecture due independently to the author and Martinez-Savage that asserts inversion sequences with no weakly decreasing subsequence of length 3 and enhanced 3-nonnesting partitions have the same cardinality. In this paper, we provide a bijective proof of this conjecture. Our bijection also enables us to provide a new bijective proof of a conjecture posed by Duncan and Steingr\'{\i}msson, which was proved by the author via an intermediate structure of growth diagrams for $01$-fillings of Ferrers shapes.

In an approach to the Cayley formula for counting trees, Shor discovered a refined recurrence relation concerning the number of improper edges. Chen and the author gave a bijection for the Shor recurrence based on the combinatorial interpretations of Zeng, answering a question of Shor. In this paper, we present a new bijective proof of the Shor recurrence by applying Shor’s formula for counting forests of rooted trees with roots 1 , … , r and with a given number of improper edges.