Terence Tao asked for a non-enumerative proof that a positive proportion of permutations are derangements and got a great answer. Inspired by this, I'd like to ask about another fa …

Denote the number of derangements by $D_N$. It's known that $D_N/N! \rightarrow 1/e$. Therefore $N!/e$ is an approximation for $D_N$. I'm trying to bound the difference between th …

A partial permutation matrix $\pi$ is one with at most one 1 in any row and column (the rest 0s). Given one, we can cross out to the East and South (but not Southeast) of each 1. S …

Suppose that $\lambda_1,\lambda_2,\lambda_3$ are partititions of $n$. When do there exist permutations $\sigma_1,\sigma_2,\sigma_3 \in S_n$ such that (1) $\sigma_1\sigma_2\sigma_ …

It is known that for a fixed x $\in {0,1,...,N-1}$, the length of the cycle of x in a random permutation in $S_N$ distributes uniformly in ${1, . . . ,N}$. My question is regardin …

Is there a standard notation that expresses substructure? The specific case that I care about is the following: Suppose $\sigma,\tau$ are permutations such that $$\sigma(x)\not=x\ …

I want to gather facts and questions related to 3D generalizations of permutations, RSK correspondence, contingency tables, etc. One reason I am interested in this is because it is …

Let $S=\lbrace s_1,\ldots,s_n \rbrace \subset \lbrace1,\ldots,2n\rbrace$. Consider two operations on $S$: the complement $C(S)=\lbrace 1,\ldots,2n \rbrace \setminus S$ and a reflec …

This question is cross-posted from math.stackexchange because it might be too technical. Let $S_n$ be the symmetric group. Recall that the number of inversions of a permutation $\ …

Given $ 0 < p < 1$, do there exist probability distributions for random variables $ X,Y $ such that all three of following are true: $$ P(X < Y) = p $$ $$ pdf (X) = f(x, …

Let's consider all possible permutations of N numbers. Suppose for each permutation we calculate the sum of absolute differences between consecutive elements. Thus, for (1,2,3) one …

I am looking at words $\alpha_1 \ldots \alpha_n$, where $\alpha_j \in \{ 1, \ldots, j \}$. Thinking of $\alpha_j$ as a height, these words can be interpreted as left-to-right paths …

Background Many properties of permutations can be stated in terms of classical patterns. For example: a permutation is stack-sortable if and only if it avoids 231 (Knuth 1975) a …

I'm modelling a scheduler that accepts a sequence of requests and outputs a sequence of responses, one response per request. It can partially reorder requests, but only within a f …

Recall that a derangement is a permutation $\pi: \{1,\ldots,n\} \to \{1,\ldots,n\}$ with no fixed points: $\pi(j) \neq j$ for all $j$. A classical application of the inclusion-exc …