Define a permutation to be any sequence of distinct positive integers. Given two permutations π and σ on disjoint underlying sets, we denote by π⧢σ the set of shuffles of π and σ (the set of all ...permutations obtained by interleaving the two permutations). A permutation statistic is a function St whose domain is the set of permutations such that St(π) only depends on the relative order of the elements of π. A permutation statistic is shuffle compatible if the distribution of St on π⧢σ depends only on St(π) and St(σ) and their lengths rather than on the individual permutations themselves. This notion is implicit in the work of Stanley in his theory of P-partitions. The definition was explicitly given by Gessel and Zhuang who proved that various permutation statistics were shuffle compatible using mainly algebraic means. This work was continued by Grinberg. The purpose of the present article is to use bijective techniques to give demonstrations of shuffle compatibility. In particular, we show how a large number of permutation statistics can be shown to be shuffle compatible using a few simple bijections. Our approach also leads to a method for constructing such bijective proofs rather than having to treat each one in an ad hoc manner. Finally, we are able to prove a conjecture of Gessel and Zhuang about the shuffle compatibility of a particular statistic.
Counting monomer-dimers, or equivalently, matchings of a graph G, is an interesting but intriguing question with great difficulties in statistical physics. Let Z(G) denote the number of ...monomer-dimers of G. In this paper, we propose a new combinatorial method to solve this problem in some special kind of graphs R(G;D;Haibi), which are obtained from a graph G with edge set E by replacing each edge e=uivi∈E﹨D with a graph Haibi having two root vertices ai and bi by identifying ui with ai and vi with bi for i=1,2,…,|E|−|D|, where D is a matching of G, and Haibi satisfies: Z(Haibi)Z(Haibi−ai−bi)=Z(Haibi−ai)Z(Haibi−bi). As an application, we obtain the exact solution of the monomer-diner problem on a fractal scale-free lattice, which answers a question posed by Zhang et al. in 2011.
We prove a conjecture of Haglund which can be seen as an extension of the equidistribution of the inversion number and the major index over permutations to ordered set partitions. Haglund's ...conjecture implicitly defines two statistics on ordered set partitions and states that they are equidistributed. The implied inversion statistic is equivalent to a statistic on ordered set partitions studied by Steingrímsson, Ishikawa, Kasraoui, and Zeng and is known to have a nice distribution in terms of q-Stirling numbers. The resulting major index exhibits a combinatorial relationship between q-Stirling numbers and the Euler–Mahonian distribution on the symmetric group, solving a problem posed by Steingrímsson.
Given an Eulerian digraph, we consider the genus distribution of its face-oriented embeddings. We prove that such distribution is log-concave for two families of Eulerian digraphs, thus giving a ...positive answer for these families to a question asked in Bonnington et al. (2002) 1. Our proof uses real-rooted polynomials and the representation theory of the symmetric group Sn. The result is also extended to some factorizations of the identity in Sn that are rotation systems of some families of one-face constellations.
Lower density operators. Φ_{f} versus Φ_{d} Gertruda Ivanova; Elżbieta Wagner-Bojakowska; Władysław Wilczyński
Rocznik Akademii Górniczo-Hutniczej im. Stanisława Staszica. Opuscula Mathematica,
03/2023, Letnik:
43, Številka:
2
Journal Article
Recenzirano
Odprti dostop
Using the new method of the construction of lower density operator introduced in the earlier paper of the first two authors, we study how much the new operator can be different from the classical ...one. The aim of this paper is to show that if \(f\) is a good adjusted measure-preserving bijection then the lower density operator generated by \(f\) can be really different from the classical density operator.
We show that, up to multiplication by a factor 1(cq;q)∞, the weighted words version of Capparelli's identity is a particular case of the weighted words version of Primc's identity. We prove this ...first using recurrences, and then bijectively. We also give finite versions of both identities.
An involution on increasing trees Liu, Shao-Hua
Discrete mathematics,
December 2019, 2019-12-00, Letnik:
342, Številka:
12
Journal Article
Recenzirano
Odprti dostop
We introduce a method to construct bijections on increasing trees. Using this method, we construct an involution on increasing trees, from which we obtain the equidistribution of the statistics ...‘number of odd vertices’ and ‘number of even vertices at odd levels’. As an application, we deduce that the expected value of the number of even vertices is twice the expected value of the number of odd vertices in a random recursive tree of given size.
In 1977 Foata proved bijectively, among other things, that the joint distribution of ascent and distinct nonzero value numbers on the set of subexcedant sequences is the same as that of descent and ...inverse descent numbers on the set of permutations, and the generating function of the corresponding bistatistics is the double Eulerian polynomial. In 2013 Foata’s result was rediscovered by Visontai as a conjecture, and then reproved by Aas in 2014.
In this paper, we define a permutation code (that is, a bijection between permutations and subexcedant sequences) and show the more general result that two 5-tuples of set-valued statistics on the set of permutations and on the set of subexcedant sequences, respectively, are equidistributed. In particular, these results give another bijective proof of Foata’s result.
PDF
