# Tagged Questions

**4**

votes

**0**answers

123 views

### Is there a geometric meaning of the Major index?

The actual question I want to ask is whether there is a geometric proof of this famous identity
$$\sum_{\sigma \in S_n} q^{\operatorname{inv} \sigma}=\sum_{\sigma\in ...

**11**

votes

**0**answers

366 views

### Is this graph polynomial known? Can it be efficiently computed?

I am a physicist, so apologies in advance for any confusing notation or terminology; I'll happily clarify. To provide a minimal amount of context, the following graph polynomial came up in my research ...

**2**

votes

**1**answer

135 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

**1**answer

136 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

**2**answers

340 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

**1**answer

136 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

**1**answer

275 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

**2**answers

171 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

**5**answers

545 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

**0**answers

62 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

**1**answer

222 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

**1**answer

279 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

**1**answer

77 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

**2**answers

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

**4**answers

849 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

**2**answers

565 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

**1**answer

762 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

**2**answers

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

**1**answer

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

**2**answers

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 ...

**9**

votes

**0**answers

177 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

**1**answer

229 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

**0**answers

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

**1**answer

220 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

**0**answers

121 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* ...

**11**

votes

**0**answers

326 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

**2**answers

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

**1**answer

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

**1**answer

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

**2**answers

245 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

**4**answers

559 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

**1**answer

417 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

**1**answer

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

**0**answers

160 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

**1**answer

431 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

**1**answer

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

**1**answer

615 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

**1**answer

618 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

**1**answer

450 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

**0**answers

201 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

**2**answers

280 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

**4**answers

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

**6**answers

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

**0**answers

152 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

**2**answers

844 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

**3**answers

427 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

**1**answer

299 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

**0**answers

218 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

**1**answer

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

**0**answers

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
...