2
votes
1answer
128 views

counting the number of ordered pairs in a permutohedron

Recall that a permutohedron is a graph on the set of permutations $S_n$ with an edge between $\sigma$ and $\tau$ if they differ by one adjacent transposition: $\tau = (i,i+1) \circ \sigma$ for some $i ...
4
votes
1answer
128 views

Principal Order Ideals in the Weak Bruhat Order

Let $\sigma\in S_n$ be a permutation on $n$ elements, and $\mathrm{Inv}(\sigma):=\{(i,j) : 1\leq i<j\leq n\text{ and }\sigma(i)>\sigma(j)\}$ be its set of inversions. In the weak order on ...
16
votes
2answers
334 views

Shortest supersequence of all permutations of $n$ elements

Given an alphabet with $n$ characters, what is the shortest sequence that contains all $n!$ permutations as subsequences? A subsequence can be obtained from a sequence by deleting any characters, ...
7
votes
1answer
129 views

Distribution of entries of a doubly-sorted random matrix

Take an $n \times n$ random matrix whose entries are i.i.d. with uniform distribution in $[0,1]$. Look at the sums of the elements of each row and then permute the rows so that these sums form an ...
10
votes
1answer
272 views

Explicit algorithm for composing permutations in factorial notation

Given two permutations p1 and p2 in factorial notation, is there an algorithm which computes their composition directly, i.e. without translating to a different notation (like Cauchy's 2-line ...
3
votes
2answers
166 views

Combinatorial design for minimization problem over binary strings

Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...
17
votes
5answers
537 views

Why is the right permutohedron order (aka weak order) on $S_n$ a lattice?

This is one of those things I never expected to be hard until I tried to prove it. Why is the right permutohedron order (a.k.a. weak Bruhat order, a.k.a. weak order -- not to be confused with the ...
0
votes
0answers
60 views

Cycles of Permutation Related to Rectangular Matrix Transposition

let the entries of a rectangular matrix $A\in\mathbb{C}^{m\times n}; m,n\in\mathbb{N}$ be stored in row-order in a linear vector $v$, i.e. $A_{i,j}=v_{i*m+j}$ Question: How can the first element ...
6
votes
1answer
219 views

Unimodality of length of longest increasing subsequence

For $w \in S_n$, the symmetric group on $n$ letters, let $\mathrm{is}(w)$ denote the length of the longest increasing subsequence of $w$. Define, $g_n(p) := |\{w \in S_n \colon \mathrm{is}(w) = p\}|$. ...
3
votes
1answer
278 views

Combinatorial Technique Needed

The following problem is likely too special for MO. However I have no clue how to deal with it, so I'll just try. Nevertheless it is a combinatorial problem and a discussion about general methods in ...
1
vote
1answer
76 views

Probability of seeing m nonzero bits in off any d consecutive bits in a circle of n bits

Suppose n bits are arranged circularly with given condition that random k of them are 1 and rest 0, and all possible d consecutive bits (total n possibilities) are looked at, what is the probability ...
1
vote
2answers
107 views

Draws from multiple non-disjoint urns

Let $C = \{1,...,n\}$ be a set of $n$ colors. Let $S_1,...,S_k$ be non-empty subsets of $C$, that is, $S_i \subseteq C$ for all $i \in \{1,...,k\}$. It is helpful to think of the $S_i$ as urns with ...
9
votes
4answers
848 views

Number of Permutations?

Edit: This is a modest rephrasing of the question as originally stated below the fold: for $n \geq 3$, let $\sigma \in S_n$ be a fixed-point-free permutation. How many fixed-point-free permutations ...
12
votes
2answers
556 views

Laws of Iterated Logarithm for Random Matrices and Random Permutation

The law of iterated logarithm asserts that if $x_1,x_2,\dots$ are i.i.d $\cal N(0,1)$ random variables and $S_n=x_1+x_2+\cdots+x_n$, then $$\limsup_{n \to \infty} S_n/\sqrt {n \log \log n} = \sqrt 2, ...
20
votes
1answer
755 views

How hard is reconstructing a permutation from its differences sequence?

My interest in combinatorially motivated computational problems led me to search for simple problems that turn out to be computationally hard. In this pursuit, I came up with a problem which I hope is ...
31
votes
2answers
1k views

A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself

Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...
7
votes
1answer
297 views

Non-enumerative proof that there are many simple permutations?

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 family of ...
4
votes
2answers
347 views

The proportion between permutations and derangements.

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 this approximation and ...
8
votes
0answers
175 views

A duality on partial permutations

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. Some boxes get ...
1
vote
1answer
226 views

The distribution of cycle length in random derangement

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 regarding the length of ...
0
votes
0answers
97 views

Notation for substructure, especially for permutations?

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\implies ...
8
votes
1answer
215 views

Permutations of prescribed cycle types that multiply to the identity

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_3$ is the identity; ...
3
votes
0answers
120 views

Citation for subset complement result

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 reflection* ...
10
votes
0answers
316 views

3D generalizations of permutations, RSK correspondence, contingency tables, etc.

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 potentially related ...
6
votes
2answers
347 views

Distribution of distances in permutations

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 would have ...
1
vote
1answer
146 views

Statistics on Lehmer codes

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 on the positive ...
5
votes
1answer
515 views

Number of Permutations with k-inversions and with a single clamped value

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 $\sigma\in S_n$ is the ...
5
votes
2answers
238 views

Maximum distance within a subset of permutations

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 finite queue. ...
7
votes
4answers
557 views

Properties of permutations with unknown pattern avoidance descriptions

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 permutation ...
17
votes
1answer
412 views

Salié permutations and fair permutations

In October 2010, I published a Monthly problem that introduced the concept of a fair permutation, which is a permutation $\pi$ such that for every $i$, either $\pi(i) > i$ and $\pi^{-1}(i) > i$, ...
0
votes
1answer
101 views

What are the number of possible ways to build up a certain path?

What are the number of possible ways to build up a certain path? I was working on a graph problem and was trying to find out in how many possible ways can you build/grow a given path. With ...
2
votes
0answers
159 views

Permutations & Balanced Distribution

I would like to implement a form of consistent hashing using a set of permutations. The rules are as follows: I have Y=~32 buckets and X items. Buckets may be "alive" or "dead". Items are to be ...
2
votes
1answer
426 views

inversion vector for multiset permutation

The definition of inversion vector for permutation is very well defined. Each permutation can be mapped to a unique inversion vector. So is there a well defined inversion vector for each multiset ...
0
votes
1answer
196 views

Sequence of permutations without a fixed point

I need to find $m$ permutations $A_1,..,A_m$ where each $A_i$ is a permutation on $n$ objects such that any of the compositions $A_jA_{j+1}..A_{j+k}$; $1 \leq j \leq n-1$ and $j+k \leq m$ does not ...
3
votes
1answer
611 views

Probabilty of two permutations having common elements?

What is the probability of two permutations on set X of size m (i.e. |X|=m) having at least n points of intersection? By this I mean that if two permutations, which I'll call g(x) and h(x), map a ...
10
votes
1answer
616 views

Sliding blocks puzzle

Consider a 'game' played on a subset $S$ of an $n^2$ square grid as follows. There are 3 types of pieces, each occupying a square of $S$, 1 green, some red and the rest are blue, a move consists of ...
10
votes
1answer
447 views

Analogues of the Knuth and Forgotten equivalences on permutations: have they been studied?

Consider a totally ordered alphabet $A$ of $n$ letters. Let $W$ be the set of all words over $A$ which have no two letters equal. Then, for example, we can define the Knuth equivalence on $W$ as the ...
6
votes
0answers
199 views

Counting Selections of Entries such having an Extremal Permutation of length n^2+1

Let $S_{n^2+1}$ be permutations of length $n^2+1$. By Erdos-Szekeres Theorem. any $s \in S_{n^2+1}$ would have a monotone subsequence(increasing or decreasing)of length $n+1$. Say a permutation $s$ of ...
1
vote
2answers
279 views

Complement to part of a permutation matrix

Consider a rectangular $(m \times n)$ matrix $\underline E_1$ with $m < n$ that has only $0$ or $1$ entries. It has exactly one $1$ entry in each row and not more than one $1$ entry in each column. ...
17
votes
4answers
1k views

An n!xn! determinant.

Let us consider the matrix $A$ with its rows and columns enumerated by the elements of $S_n$ with $A_{\sigma\tau}=x^{c(\sigma\tau^{-1})}$ where $c()$ is the number of cycles in a permutation's ...
36
votes
6answers
3k views

Non-enumerative proof that there are many derangements?

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-exclusion principle ...
4
votes
0answers
151 views

Bound on coefficients in Young tableuax

The following may be known, but I didn't find anything in the literature. Background: The irreducible representations of $S_n$ correspond to shapes of Young tableaux with $n$ elements. Let $\lambda$ ...
0
votes
2answers
833 views

non negative integer solutions : Diophantine Equations [closed]

I want to know the exact number of non-negative integer solutions of a1x1+a2x2+...akxk = n ... I know that it is the co-efficient of x^n in (1-x^a1)^-1 * (1-x^a2)^-1 * ... (1-x^ak)^-1 ... but whats ...
0
votes
3answers
420 views

Computing Permutations with Partial Duplicates

I am looking for a way to compute the number of $K$ permutations of a multiset with $N*D$ elements where each group has exactly $D$ equal elements (and typically $D < N$ ). I've got an application ...
5
votes
1answer
298 views

Counting the (additive) decompositions of a quadratic, symmetric, empty-diagonal and constant-line matrix into permutation matrices

Dear community, I have the following combinatorial question which I will explain in short first and then with some more detail. At the end you will find a very simple example. Short version Le $A ...
7
votes
0answers
216 views

Are plactic classes convex under the right weak Bruhat order?

For those who are unfamiliar with the terminology, I'll explain a little. The symmetric group $S_n$, as a type A Coxeter group, has generators $\{s_1,\ldots,s_{n-1}\}$ with relations (1) $s_i^2$ for ...
3
votes
1answer
230 views

Stricter permutation patterns

(I asked this ten days ago on math.SE, but I received no reply, so I'm trying again here.) A lot of work has been done on patterns in permutations, where a permutation is said to match a given ...
4
votes
0answers
176 views

restricting “dances of minimal cost” (optimization on braids/permutations?)

Consider applying the permutation (1,3,0,5,2,7,4,6) to the integers (0,1,2,3,4,5,6,7) three times. I call this a "dance of minimal cost" because all unordered pairs in {0..7} meet each other, and the ...
19
votes
0answers
853 views

Do all possible trees arise as orbit trees of some permutation groups?

I.Motivation from descriptive set theory (Contains some quotes from Maciej Malicki's paper.) The classical theorem of Birkhoff-Kakutani implies that every metrizable topological group G admits a ...
1
vote
1answer
562 views

Generating fixtures for a chess league, with a twist

Hello, I am in the process of building some software to generate fixtures for a chess league. Which has a little twist which complicates matters. I would like to introduce a constraint. Where by a ...