Given a permutation statistic $\operatorname {\mathrm {st}}$, define its inverse statistic $\operatorname {\mathrm {ist}}$ by . We give a general approach, based on the theory of symmetric functions, for finding the joint distribution of $\operatorname {\mathrm {st}}_{1}$ and $\operatorname {\mathrm {ist}}_{2}$ whenever $\operatorname {\mathrm {st}}_{1}$ and $\operatorname {\mathrm {st}}_{2}$ are descent statistics: permutation statistics that depend only on the descent composition. We apply this method to a number of descent statistics, including the descent number, the peak number, the left peak number, the number of up-down runs and the major index. Perhaps surprisingly, in many cases the polynomial giving the joint distribution of $\operatorname {\mathrm {st}}_{1}$ and $\operatorname {\mathrm {ist}}_{2}$ can be expressed as a simple sum involving products of the polynomials giving the (individual) distributions of $\operatorname {\mathrm {st}}_{1}$ and $\operatorname {\mathrm {st}}_{2}$. Our work leads to a rederivation of Stanley’s generating function for doubly alternating permutations, as well as several conjectures concerning real-rootedness and $\gamma $-positivity.

The goal of this paper is to go further in the analysis of the behavior of the number of descents in a random permutation. Via two different approaches relying on a suitable martingale decomposition or on the Irwin–Hall distribution, we prove that the number of descents satisfies a sharp large-deviation principle. A very precise concentration inequality involving the rate function in the large-deviation principle is also provided.

The factorially normalized Bernoulli polynomials $b_n(x) = B_n(x)/n!$ are known to be characterized by $b_0(x) = 1$ and $b_n(x)$ for $n \gt 0$ is the anti-derivative of $b_{n-1}(x)$ subject to $\int _0^1 b_n(x) dx = 0$. We offer a related characterization: $b_1(x) = x - 1/2$ and $({-}1)^{n-1} b_n(x)$ for $n \gt 0$ is the $n$-fold circular convolution of $b_1(x)$ with itself. Equivalently, $1 - 2^n b_n(x)$ is the probability density at $x \in (0,1)$ of the fractional part of a sum of $n$ independent random variables, each with the beta$(1,2)$ probability density $2(1-x)$ at $x \in (0,1)$. This result has a novel combinatorial analog, the Bernoulli clock: mark the hours of a $2 n$ hour clock by a uniformly random permutation of the multiset $\{1,1, 2,2, \ldots, n,n\}$, meaning pick two different hours uniformly at random from the $2 n$ hours and mark them $1$, then pick two different hours uniformly at random from the remaining $2 n - 2$ hours and mark them $2$, and so on. Starting from hour $0 = 2n$, move clockwise to the first hour marked $1$, continue clockwise to the first hour marked $2$, and so on, continuing clockwise around the Bernoulli clock until the first of the two hours marked $n$ is encountered, at a random hour $I_n$ between $1$ and $2n$. We show that for each positive integer $n$, the event $( I_n = 1)$ has probability $(1 - 2^n b_n(0))/(2n)$, where $n! b_n(0) = B_n(0)$ is the $n$th Bernoulli number. For $ 1 \le k \le 2 n$, the difference $\delta _n(k)\,:\!=\, 1/(2n) -{\mathbb{P}}( I_n = k)$ is a polynomial function of $k$ with the surprising symmetry $\delta _n( 2 n + 1 - k) = ({-}1)^n \delta _n(k)$, which is a combinatorial analog of the well-known symmetry of Bernoulli polynomials $b_n(1-x) = ({-}1)^n b_n(x)$.

Recently, Hong and Li launched a systematic study of length-four pattern avoidance in inversion sequences, and in particular, they conjectured that the number of 0021-avoiding inversion sequences can be enumerated by the OEIS entry A218225. Meanwhile, Burstein suggested that the same sequence might also count three sets of pattern-restricted permutations. The objective of this paper is not only a confirmation of Hong and Li’s conjecture and Burstein’s first conjecture but also two more delicate generating function identities with the $\mathsf{ides}$ statistic concerned in the restricted permutation case and the $\mathsf{asc}$ statistic concerned in the restricted inversion sequence case, which yield a new equidistribution result.

Let $k \geqslant 2$ be an integer. We prove that factorisation of integers into k parts follows the Dirichlet distribution $\mathrm{Dir}\left({1}/{k},\ldots,{1}/{k}\right)$ by multidimensional contour integration, thereby generalising the Deshouillers–Dress–Tenenbaum (DDT) arcsine law on divisors where $k=2$. The same holds for factorisation of polynomials or permutations. Dirichlet distribution with arbitrary parameters can be modelled similarly.

We study (asymmetric) $U$-statistics based on a stationary sequence of $m$-dependent variables; moreover, we consider constrained $U$-statistics, where the defining multiple sum only includes terms satisfying some restrictions on the gaps between indices. Results include a law of large numbers and a central limit theorem, together with results on rate of convergence, moment convergence, functional convergence, and a renewal theory version.

Special attention is paid to degenerate cases where, after the standard normalization, the asymptotic variance vanishes; in these cases non-normal limits occur after a different normalization.

The results are motivated by applications to pattern matching in random strings and permutations. We obtain both new results and new proofs of old results.

Let p be a prime with $p\equiv 1\pmod {4}$ . Gauss first proved that $2$ is a quartic residue modulo p if and only if $p=x^2+64y^2$ for some $x,y\in \Bbb Z$ and various expressions for the quartic residue symbol $(\frac {2}{p})_4$ are known. We give a new characterisation via a permutation, the sign of which is determined by $(\frac {2}{p})_4$ . The permutation is induced by the rule $x \mapsto y-x$ on the $(p-1)/4$ solutions $(x,y)$ to $x^2+y^2\equiv 0 \pmod {p}$ satisfying $1\leq x < y \leq (p-1)/2$ .

We investigate random minimal factorizations of the n-cycle, that is, factorizations of the permutation $(1 \, 2 \cdots n)$ into a product of cycles $\tau_1, \ldots, \tau_k$ whose lengths $\ell(\tau_1), \ldots, \ell(\tau_k)$ satisfy the minimality condition $\sum_{i=1}^k(\ell(\tau_i)-1)=n-1$ . By associating to a cycle of the factorization a black polygon inscribed in the unit disk, and reading the cycles one after another, we code a minimal factorization by a process of colored laminations of the disk. These new objects are compact subsets made of red noncrossing chords delimiting faces that are either black or white. Our main result is the convergence of this process as $n \rightarrow \infty$ , when the factorization is randomly chosen according to Boltzmann weights in the domain of attraction of an $\alpha$ -stable law, for some $\alpha \in (1,2]$ . The limiting process interpolates between the unit circle and a colored version of Kortchemski’s $\alpha$ -stable lamination. Our principal tool in the study of this process is a new bijection between minimal factorizations and a model of size-conditioned labeled random trees whose vertices are colored black or white, as well as the investigation of the asymptotic properties of these trees.

A classical result for the simple symmetric random walk with 2n steps is that the number of steps above the origin, the time of the last visit to the origin, and the time of the maximum height all have exactly the same distribution and converge when scaled to the arcsine law. Motivated by applications in genomics, we study the distributions of these statistics for the non-Markovian random walk generated from the ascents and descents of a uniform random permutation and a Mallows(q) permutation and show that they have the same asymptotic distributions as for the simple random walk. We also give an unexpected conjecture, along with numerical evidence and a partial proof in special cases, for the result that the number of steps above the origin by step 2n for the uniform permutation generated walk has exactly the same discrete arcsine distribution as for the simple random walk, even though the other statistics for these walks have very different laws. We also give explicit error bounds to the limit theorems using Stein’s method for the arcsine distribution, as well as functional central limit theorems and a strong embedding of the Mallows(q) permutation which is of independent interest.

A set S of permutations is forcing if for any sequence $\{\Pi_i\}_{i \in \mathbb{N}}$ of permutations where the density $d(\pi,\Pi_i)$ converges to $\frac{1}{|\pi|!}$ for every permutation $\pi \in S$ , it holds that $\{\Pi_i\}_{i \in \mathbb{N}}$ is quasirandom. Graham asked whether there exists an integer k such that the set of all permutations of order k is forcing; this has been shown to be true for any $k\ge 4$ . In particular, the set of all 24 permutations of order 4 is forcing. We provide the first non-trivial lower bound on the size of a forcing set of permutations: every forcing set of permutations (with arbitrary orders) contains at least four permutations.

Let $p=3n+1$ be a prime with $n\in \mathbb {N}=\{0,1,2,\ldots \}$ and let $g\in \mathbb {Z}$ be a primitive root modulo p. Let $0<a_1<\cdots <a_n<p$ be all the cubic residues modulo p in the interval $(0,p)$ . Then clearly the sequence $a_1 \bmod p,\, a_2 \bmod p,\ldots , a_n \bmod p$ is a permutation of the sequence $g^3 \bmod p,\,g^6 \bmod p,\ldots , g^{3n} \bmod p$ . We determine the sign of this permutation.

We prove that most permutations of degree $n$ have some power which is a cycle of prime length approximately $\log n$. Explicitly, we show that for $n$ sufficiently large, the proportion of such elements is at least $1-5/\log \log n$ with the prime between $\log n$ and $(\log n)^{\log \log n}$. The proportion of even permutations with this property is at least $1-7/\log \log n$.

Necklaces are the equivalence classes of words under the action of the cyclic group. Let a transition in a word be any change between two adjacent letters modulo the word’s length. We present a closed-form solution for the enumeration of necklaces in n beads, k colours and t transitions. We show that our result provides a more general solution to the problem of counting alternating (proper) colourings of the vertices of a regular n-gon.

For an indifference graph G, we define a symmetric function of increasing spanning forests of G. We prove that this symmetric function satisfies certain linear relations, which are also satisfied by the chromatic quasisymmetric function and unicellular $\textrm {LLT}$ polynomials. As a consequence, we give a combinatorial interpretation of the coefficients of the $\textrm {LLT}$ polynomial in the elementary basis (up to a factor of a power of $(q-1)$), strengthening the description given in [4].

We show that the Mallows measure on permutations of $1,\dots ,n$ arises as the law of the unique Gale–Shapley stable matching of the random bipartite graph with vertex set conditioned to be perfect, where preferences arise from the natural total ordering of the vertices of each gender but are restricted to the (random) edges of the graph. We extend this correspondence to infinite intervals, for which the situation is more intricate. We prove that almost surely, every stable matching of the random bipartite graph obtained by performing Bernoulli percolation on the complete bipartite graph $K_{{\mathbb Z},{\mathbb Z}}$ falls into one of two classes: a countable family $(\sigma _n)_{n\in {\mathbb Z}}$ of tame stable matchings, in which the length of the longest edge crossing k is $O(\log |k|)$ as $k\to \pm \infty $ , and an uncountable family of wild stable matchings, in which this length is $\exp \Omega (k)$ as $k\to +\infty $ . The tame stable matching $\sigma _n$ has the law of the Mallows permutation of ${\mathbb Z}$ (as constructed by Gnedin and Olshanski) composed with the shift $k\mapsto k+n$ . The permutation $\sigma _{n+1}$ dominates $\sigma _{n}$ pointwise, and the two permutations are related by a shift along a random strictly increasing sequence.

The Brownian separable permuton is a random probability measure on the unit square, which was introduced by Bassino, Bouvel, Féray, Gerin and Pierrot (2016) as the scaling limit of the diagram of the uniform separable permutation as size grows to infinity. We show that, almost surely, the permuton is the pushforward of the Lebesgue measure on the graph of a random measure-preserving function associated to a Brownian excursion whose strict local minima are decorated with independent and identically distributed signs. As a consequence, its support is almost surely totally disconnected, has Hausdorff dimension one, and enjoys self-similarity properties inherited from those of the Brownian excursion. The density function of the averaged permuton is computed and a connection with the shuffling of the Brownian continuum random tree is explored.

For $$\tau \in {S_3}$$, let $$\mu _n^\tau $$ denote the uniformly random probability measure on the set of $$\tau $$-avoiding permutations in $${S_n}$$. Let $${\mathbb {N}^*} = {\mathbb {N}} \cup \{ \infty \} $$ with an appropriate metric and denote by $$S({\mathbb{N}},{\mathbb{N}^*})$$ the compact metric space consisting of functions $$\sigma {\rm{ = }}\{ {\sigma _i}\} _{i = 1}^\infty {\rm{ }}$$ from $$\mathbb {N}$$ to $${\mathbb {N}^ * }$$ which are injections when restricted to $${\sigma ^{ - 1}}(\mathbb {N})$$; that is, if $${\sigma _i}{\rm{ = }}{\sigma _j}$$, $$i \ne j$$, then $${\sigma _i} = \infty $$. Extending permutations $$\sigma \in {S_n}$$ by defining $${\sigma _j} = j$$, for $$j \gt n$$, we have $${S_n} \subset S({\mathbb{N}},{{\mathbb{N}}^*})$$. For each $$\tau \in {S_3}$$, we study the limiting behaviour of the measures $$\{ \mu _n^\tau \} _{n = 1}^\infty $$ on $$S({\mathbb{N}},{\mathbb{N}^*})$$. We obtain partial results for the permutation $$\tau = 321$$ and complete results for the other five permutations $$\tau \in {S_3}$$.

Let (X, Y) = (Xn, Yn)n≥1 be the output process generated by a hidden chain Z = (Zn)n≥1, where Z is a finite-state, aperiodic, time homogeneous, and irreducible Markov chain. Let LCn be the length of the longest common subsequences of X1,..., Xn and Y1,..., Yn. Under a mixing hypothesis, a rate of convergence result is obtained for E[LCn]/n.

We construct a shifted version of the Turán sieve method developed by R. Murty and the second author and apply it to counting problems on tournaments. More precisely, we obtain upper bounds for the number of tournaments which contain a fixed number of restricted $r$-cycles. These are the first concrete results which count the number of cycles over “all tournaments”.

The goal of property testing is to quickly distinguish between objects which satisfy a property and objects that are ε-far from satisfying the property. There are now several general results in this area which show that natural properties of combinatorial objects can be tested with ‘constant’ query complexity, depending only on ε and the property, and not on the size of the object being tested. The upper bound on the query complexity coming from the proof techniques is often enormous and impractical. It remains a major open problem if better bounds hold.

Maybe surprisingly, for testing with respect to the rectangular distance, we prove there is a universal (not depending on the property), polynomial in 1/ε query complexity bound for two-sided testing hereditary properties of sufficiently large permutations. We further give a nearly linear bound with respect to a closely related metric which also depends on the smallest forbidden subpermutation for the property. Finally, we show that several different permutation metrics of interest are related to the rectangular distance, yielding similar results for testing with respect to these metrics.