The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
88 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$ ...
6
votes
1answer
205 views

Primitive, non-2-transitive groups with very large orbitals?

Let $G$ be a transitive permutation group on a set $X$ with $n$ elements. Assume that $G$ is primitive, i.e., $G$ preserves no non-trivial partition of $X$. Assume as well that $G$ is not ...
17
votes
5answers
488 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
48 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 ...
9
votes
3answers
528 views

How do most people write permutations?

I'd like to know how people prefer to write permutations, or elements of the symmetric group $S_n$ for $n\ge0$. The most natural way to define a permutation in $S_n$ is as a bijection on the set ...
0
votes
1answer
113 views

Permutations of letters under some conditions

Let $W(p,q,r,s)$ be the number of permutations of the letters which satisfy the following conditions : Condition 1 : The letters are consist of $P,Q,R,S$. Condition 2 : The number of letter ...
10
votes
1answer
176 views

Effective Camille Jordan

It is a well-known (and frequently used) theorem of C. Jordan that a proper subgroup $H$ of a finite group $G$ can not intersect every conjugacy class. This is used most frequently for $G=S_n.$ Now, ...
6
votes
1answer
217 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
276 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
68 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
106 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
827 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 ...
13
votes
2answers
521 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, ...
8
votes
1answer
106 views

GOE Version of Longest Increasing Subsequence

Let $S_n$ be the symmetric group equipped with uniform measure. For any $\pi\in S_n$, let $L_n=L_n(\pi)$ denote the longest increasing subsequence. A celebrated result of Baik, Deift and Johansson ...
20
votes
1answer
729 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 ...
30
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
292 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
341 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
170 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
219 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
95 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
187 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
119 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
279 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
335 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
145 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
431 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
222 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. ...
1
vote
2answers
211 views

Is it an integer for all positive integer n ? [closed]

I am trying to figure out if the following expression $$\frac{(n^2 - n)! }{ n! ((n-1)!)^n }$$ is an integer for all positive integer $n.$ I tried the induction, but induction case is running ...
2
votes
2answers
181 views

Graph of $S_n$ with respect to transposition

Consider the graph $G_n$, with $V(G_n) = S_n$ (the set of permutations of a set of size $n$) and having an edge $\sigma\sigma'$ iif $\sigma'$ can be obtained from $\sigma$ by applying a transposition. ...
5
votes
2answers
388 views

Permuting Racked Pool Balls with a Single Break

Given reasonable physical assumptions (on friction, collisions, etc.), would it be possible to "break" in a pool game such that when all the balls come to rest, the only difference is that the racked ...
7
votes
4answers
543 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
400 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
100 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
148 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 ...
0
votes
0answers
80 views

Proving that a property holds for random sequences with given marginal distribution by rearrangement

I am currently investigating the property of random sequences with a special marginal distribution function $F(x)$. Given any random sequence $X_1, X_2, \cdots, X_n$, supposing their joint ...
3
votes
1answer
233 views

Distances on generalizations of the symmetric group

I'm a computer vision student, and I'm looking for some symmetric group literature guidance. I'm going to provide some context, and finally ask two questions. The Cayley distance and other distances ...
2
votes
1answer
378 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
193 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 ...
2
votes
1answer
533 views

Hamming distance approximates Cayley distance on permutations: citation wanted

Suppose we have two permutations x and y, represented as rank vectors. The Hamming distance between them is the number of entries in the two vectors which disagree. The Cayley distance is the minimum ...
3
votes
1answer
596 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
609 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
434 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 ...
2
votes
1answer
187 views

perfect shuffle of 2n cards

permutation is given by f(i) = 2i if i<=n and 2(i-n)-1 if i>n where i denotes the position of cards. eg pack of cards (1,2,3,4)-->(3,1,4,2) Basically trying to find the multiplicative order of 2 ...
3
votes
0answers
90 views

Permutation function repeated application

Suppose we have a function that permutes a string of symbols according to a rule that we define recursively $f(s_1s_2s_3s_4s_5...)$ = $f(s_1s_3s_5...)+f(s_2s_4s_6...)$ with $f(s_1)=s_1$ (plus denotes ...
6
votes
0answers
195 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
1answer
160 views

Sequence of transpositions that generates the set of permutations

So I think it's possible to create an infinite sequence of transpositions T = { ti, i ≥ 2 ...
6
votes
2answers
490 views

Two groups acting on a set.

Suppose we are given a set S of points on which two different groups G and G' (given by sets of generating permutations) act. Is there an efficient algorithm for finding generators the largest pair ...
1
vote
2answers
267 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 ...