Search

A permutation of the multiset { 1 , 1 , 2 , 2 , … , n , n } is called a Stirling permutation of order n if every entry between the two occurrences of i is greater than i for each i ∈ { 1 , 2 , … , n } . In this paper, we introduce the definitions of block, even indexed entry, odd indexed entry, Stirling derangement, marked permutation and bicolored increasing binary tree. We first study the joint distribution of ascent plateaux, even indexed entries and left-to-right minima over the set of Stirling permutations of order n . We then present an involution on Stirling derangements.

The γ -coefficients of Eulerian polynomials were first considered by Foata and Schutzenberger. In this paper, we provide combinatorial interpretations for the γ -coefficients arising from the segmented permutations and segmented derangements via Branden’s modified Foata–Strehl action. We also give the combinatorial interpretations of γ -coefficients for the ( > , ≤ , − ) -avoiding inversion sequences via continued fractions.

A classical problem in enumerative combinatorics is to count the number of derangements, i.e., permutations with no fixed point. In this paper, we study the cyclic derangement polynomials, which count the number of derangements in the wreath product C r ≀ S n . We first establish the relation between the cyclic Eulerian polynomials and the cyclic derangement polynomials. Then we show that the coefficients of the cyclic derangement polynomials have the asymptotic normality and the spiral property. Finally, we show the continued fraction expression of the generating function of the cyclic derangement polynomials.

In this paper, we study the distribution of the number of occurrences of the simplest frame pattern, called the $��$ pattern, in $n$-cycles. Given an $n$-cycle $C$, we say that a pair $\langle i,j \rangle$ matches the $��$ pattern if $i < j$ and as we traverse around $C$ in a clockwise direction starting at $i$ and ending at $j$, we never encounter a $k$ with $i < k < j$. We say that $ \langle i,j \rangle$ is a nontrivial $��$-match if $i+1 < j$. Also, an $n$-cycle $C$ is incontractible if there is no $i$ such that $i+1$ immediately follows $i$ in $C$. We show that the number of incontractible $n$-cycles in the symmetric group $S_n$ is $D_{n-1}$, where $D_n$ is the number of derangements in $S_n$. Further, we prove that the number of $n$-cycles in $S_n$ with exactly $k$ $��$-matches can be expressed as a linear combination of binomial coefficients of the form $\binom{n-1}{i}$ where $i \leq 2k+1$. We also show that the generating function $NTI_{n,��}(q)$ of $q$ raised to the number of nontrivial $��$-matches in $C$ over all incontractible $n$-cycles in $S_n$ is a new $q$-analogue of $D_{n-1}$, which is different from the $q$-analogues of the derangement numbers that have been studied by Garsia and Remmel and by Wachs. We show that there is a rather surprising connection between the charge statistic on permutations due to Lascoux and Sch��zenberger and our polynomials in that the coefficient of the smallest power of $q$ in $NTI_{2k+1,��}(q)$ is the number of permutations in $S_{2k+1}$ whose charge path is a Dyck path. Finally, we show that $NTI_{n,��}(q)|_{q^{\binom{n-1}{2} -k}}$ and $NT_{n,��}(q)|_{q^{\binom{n-1}{2} -k}}$ are the number of partitions of $k$ for sufficiently large $n$.

A selection of points drawn from a convex polygon, no two with the same vertical or horizontal coordinate, yields a permutation in a canonical fashion. We characterise and enumerate those permutations which arise in this manner and exhibit some interesting structural properties of the permutation class they form. We conclude with a permutation analogue of the celebrated Happy Ending Problem. Preprint

We investigate the notion of almost avoiding a permutation: $\pi$ almost avoids $\beta$ if one can remove a single entry from $\pi$ to obtain a $\beta$-avoiding permutation.

Riordan paths are Motzkin paths without horizontal steps on the x-axis. We establish a correspondence between Riordan paths and $(321,3\bar{1}42)$-avoiding derangements. We also present a combinatorial proof of a recurrence relation for the Riordan numbers in the spirit of the Foata-Zeilberger proof of a recurrence relation on the Schr\"oder numbers., Comment: 9 pages, 2 figures

We discover the spiral property of the q -derangement numbers arising from q -counting of derangements by the major index. The spiral property implies that the polynomial is unimodal and the maximum coefficient appears exactly in the middle, which confirms a conjecture of Chen and Rota.

The derangement problem for a ‘two-dimensional’ version of the ‘probléme des rencontres’ is formulated and solved by Fisk (1988). In this follow-up we find the complete probability distribution of the ‘hit’ variable, with which the Bell numbers appear to be connected, as the kth binomial moments multiplied by k!.

Chen, W.Y.C. and R.P. Stanley, Derangements on the n-cube, Discrete Mathematics 115 (1993) 65-15. Let Q. be the n-dimensional cube represented by a graph whose vertices are sequences of O’s and l’s of length n, where two vertices are adjacent if and only if they differ only at one position. A k-dimensional subcube or a k-face of Q. is a subgraph of Q. spanned by all the vertices u1 u2 u, with constant entries on n-k positions. For a k-face Gx of Q. and a symmetry w of Q., we say that w fixes Gt if w induces a symmetry of Gt; in other words, the image of any vertex of G,, is still a vertex in Gk. A symmetry w of Q. is said to be a k-dimensional derangement if w does not fix any k-dimensional subcube of Q.; otherwise, w is said to be a k-dimensional rearrangement. In this paper, we find a necessary and sufficient condition for a symmetry of Q. to have a fixed kdimensional subcube. We find a way to compute the generating function for the number of k-dimensional rearrangements on Q.. This makes it possible to compute explicitly such generating functions for small k. Especially, for k =O, we have that there are 1.3 . (2n- 1) symmetries of Q. with at least one fixed vertex. A combinatorial proof of this formula is also given.

We give a bijective proof that the number of even and odd derangements in S n differs by n −1.

We define a new combinatorial statistic, maximal-inversion, on a permutation. We remark that the number M(n,k) of permutations in Sn with k maximal-inversions is the signless Stirling number c(n,n−k) of the first kind. A permutation π in Sn is uniquely determined by its maximal-inversion set MI(π). We prove it by making an algorithm for retrieving the permutation from its maximal-inversion set. Also, we remark on how the algorithm can be used directly to determine whether a given set is the maximal-inversion set of a permutation. As an application of the algorithm, we characterize the maximal-inversion set for pattern-avoiding permutations. Then we give some enumerative results concerning permutations with forbidden patterns.

We make use of the notion of ‘doubled fixed point’ in the graph of an exceeding mapping, to give new combinatorial interpretations (a) for the Euler finite-difference tableau relating the sequence n ! to the sequence of derangement numbers, and (b) for the Seidel tableau generating the Genocchi numbers of first and second kind. Further consequences are derived for the combinatorial theory of Genocchi numbers and allied polynomials.

We characterize all pairs F = ( F ( n , k )) and G = ( G ( n , k )) of inverse infinite, lower-triangular matrices by a ‘dual’ pair of recurrence relations that their entries F ( n , k ) and G ( n , k ) must satisfy. This characterization provides a unified approach towards all inverse relations based on such inversion problems. The computation of the inverse of a given infinite, lower-triangular matrix F is reduced to finding a recurrence of the required form that its entries must satisfy. The inverse matrix G is then determined in a similar way by the dual recurrence. We provide historical motivation, and then use our characterization theorem to invert a number of important infinite, lower-triangular matrices. These include matrix inversions of Gould and Hsu, Krattenthaler, Carlitz, Bressoud, as well as Andrews' matrix formulation of the Bailey Transform. These examples illustrate how shift operators or summation theorems such as the q -Chu-Vandermonde summation are used to help find recurrence relations of the required type for the entries of F and G .

An analogue of the exponential generating function for derangement numbers in the symmetric group algebras is introduced. It leads to n mutually orthogonal idempotents in the group algebra of the symmetric group Sn, for all n. The corresponding representations of Sn have dimensions equal to the number of permutations with given number of fixed points. They are closely related to the higher Lie representations of Sn. As a consequence, new proofs are obtained for a number of results on derangement numbers due to Désarménien, Gessel, Reutenauer and Wachs.

We consider the derangements graph in which the vertices are permutations of {1… n }. Two vertices are joined by an edge if the corresponding permutations differ in every position. The derangements graph is known to be hamiltonian and it follows from a recent result of Jung that every pair of vertices is joined by a Hamiltonian path. We use this result to settle an open question, by showing that it is possible, for any n and k satisfying 2⩽ k ⩽ n and k ≠3, to generate permutations of {1... n } so that successive permutations differ in k consecutive positions. In fact, the associated k -consecutive derangements graph is also Hamilton-connected.