Questions related to permutations, bijections from a finite (or sometimes infinite) set to itself.

learn more… | top users | synonyms

5
votes
3answers
424 views

Permutations with all cycles odd length and permutations with all cycles even length

If $n$ is even, then the number of permutations of $n$ in which all cycles have odd length equals the number of permutations of $n$ in which all cycles have even length. This fact is easily proved, ...
2
votes
0answers
34 views

Smooth bivariate functions identifiable under permutations

Consider a "smooth" $f : [0,1]^2 \to [0,1]$ and let $\pi : [n] \to [n]$ be a permutation of $[n] =\{1,\dots,n\}$. Let us define $$ A^{f,\pi} := \Big( f\Big(\frac{\pi(i)}{n},\frac{\pi(j)}{n}\Big) ...
2
votes
0answers
60 views

Permutation-invariant matrix representation

The question guide says that Mathoverflow is for research level mathematics. While I do not perform research in mathematics (I study quantum chemistry), I believe this question is research-level ...
3
votes
1answer
124 views

Regarding left-to-right minima

Let $\rho$ be a permutation on $[1,n]$ and $l_i$ be the number of left-to-right minima in $\rho_{i\ldots n}$, I know that for a random permutation $E[l_1] = H_n$ (the $n$-th Harmonic number) but is ...
-1
votes
1answer
157 views

The name of a group of order 24 [closed]

I encountered a group $G =\langle(1,3,2,4),(3,5,4,6)\rangle\subseteq S_6$ in my study, but I do not know its name. Let $f=(1,3,2,4)$ and $g=(3,5,4,6)$. We have $g^2=fg^2f$, and thus $\langle ...
24
votes
2answers
781 views

Arranging numbers from $1$ to $n$ such that the sum of every two adjacent numbers is a perfect power

I've known that one can arrange all the numbers from $1$ to $\color{red}{15}$ in a row such that the sum of every two adjacent numbers is a perfect square. $$8,1,15,10,6,3,13,12,4,5,11,14,2,7,9$$ ...
4
votes
1answer
224 views

Permutation polynomials mod $p$ of the form $(x+1)^n-x^n$

Among some permutation polynomials I've been studying, $f(x)=(x+1)^n-x^n$ is one of the polynomials that I cannot grasp. Question : For a given odd prime $p$, how can we find every positive ...
5
votes
1answer
258 views

When is a linear combination of permutation matrices unitary?

Question: Let $P_\pi$ denote the matrix representation of permutation $\pi$. Consider a linear combination of all $n \times n$ permutation matrices $$U := \sum_{\pi \in S_n} c_\pi P_\pi$$ where ...
2
votes
0answers
74 views

Exact growth rate of Longest Increasing Subsequence expectation

Let $S_n$ be the symmetric group, $\pi\in S_n$ a uniformly random permutation and $L_n:=L_n(\pi)$ denoting the length of the longest increasing subsequence (LIS). We know that ...
1
vote
0answers
99 views

Classifying 1 cycle permutation matrices

Given a permutation matrix that is not full rank, is there a linear algebraic and corresponding algebraic criterion to tell if matrix contains more than one disjoint non-trivial cycle or exactly one ...
11
votes
3answers
363 views

Sets of points containing permutations - a Ramsey-type question

The following question arised as a side-question in a geometric problem. It has a "feel" similar to problems in Ramsey-theory, but I have not found any mention of it (also I'm not very familiar with ...
3
votes
0answers
47 views

Is $LIS(\pi)+LIS(\sigma)+LIS(\sigma\pi^{-1})$ lower bounded?

In the title, $LIS$ stands for the length of longest increasing subsequence and Greek letters stand for permutations from symmetric group $S_n$. Considering some cases such as ...
1
vote
1answer
60 views

Are certain normal matrices circulant? (Part 2)

Let $\mathcal{F}$ denote the family of real normal matrices $A$ such that $ A^TA=\begin{pmatrix} a & b \\ b & \ddots \end{pmatrix}$, for $b>0$. As a user observed in the solution of Part 1 ...
2
votes
1answer
126 views

Hopf structures on “pictorial” descriptions of permutations

There is a well-known Hopf structure on permutations, due to Malvenuto and Reutenauer. Here, the F basis elements are permutations in one-line notation, the product of two permutations is their ...
7
votes
2answers
495 views

Numbers with all N-digit prefixes divisible by N

In base 10, the number 3816547290 contains every digit exactly once. When I take the first N digits, that substring is divisible by N. For example, 381 is divisible by 3, 38165 is divisible by 5, etc. ...
4
votes
0answers
67 views

Name for class of flattening permutations

Let $S_n$ be the symmetric group. For any sequence of numbers $y=[y_1,y_2,\cdots,y_k]$, define the flattening operation as $\mbox{flatt}_{k}(y)$ as a relabeling of $y_1,y_2,\cdots,y_k$ in terms of ...
12
votes
1answer
215 views

Number of orders of $k$-sums of $n$-numbers

Suppose we have a $n$-element set $S$. Denote the set of its $k$-element subsets by $K$ ($|K|=\binom{n}{k}$). If the elements of $S$ are real numbers then to each $k$-element subset we can associate ...
14
votes
2answers
313 views

Does a classification of simultaneous conjugacy classes in a product of symmetric groups exist?

Let the symmetric group $S_n$ on $n$ letters act on $S_n^d=S_n\times\cdots\times S_n$ by simultaneous conjugation, i.e. $\pi\in S_n$ acts on $(\sigma_1,\ldots,\sigma_d)\in S_n^d$ by ...
4
votes
0answers
229 views

Polynomial dynamical systems

The question is somewhat related to the theory of permutation polynomials. Let $\mathbb{F}_p$ be a finite field of $p$ elements ($p$ is prime) and $\mathcal{V} = \mathbb{F}_p^2 = \{ (t_1,t_2)\::\: ...
4
votes
1answer
207 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 ...
25
votes
2answers
844 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
1answer
162 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 ...
1
vote
0answers
316 views

Conjectures on fractions where each digit appears once in numerator and denominator

This is a highly redacted version of a question that was asked before. Please see Criteria of considering relevance of the question to the domain of research topics for details. Some numerical ...
6
votes
1answer
184 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 ...
10
votes
1answer
373 views

Categorical interpretation of disjoint cycle notation for tracing permutations

For a natural number $n\in\mathbb{N}$, let $\underline{n}$ denote the finite set $$\underline{n}:=\{1,2,\ldots,n\}.$$ A permutation $\sigma\in Aut(\underline{n})$ can be uniquely written (up to order) ...
10
votes
5answers
1k views

Probability of a pair of memory cards ending up as neighbors

I am trying to compute the probability that after a perfect shuffling of a deck of memory cards (n pairs) none of the pairs end up with the two members next to each other. I get into a messy ...
5
votes
0answers
162 views

Inverse moment of the number of inversions of a permutation

Let $\pi$ be a permutation of $\{1,2,...,n\}$. A pair of elements ($\pi_i$,$\pi_j$) is called an inversion if $i$ $>$ $j$ and $\pi_i$ $<$ $\pi_j$. The total number of inversions in $\pi$ is ...
18
votes
2answers
444 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
151 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
312 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
214 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
255 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 ...
18
votes
6answers
693 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 ...
1
vote
1answer
124 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
693 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
228 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
185 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, ...
5
votes
1answer
228 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\}|$. ...
4
votes
1answer
285 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
80 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
113 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
880 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 ...
18
votes
2answers
687 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
118 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 ...
29
votes
1answer
1k 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 ...
34
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
315 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 ...
5
votes
2answers
363 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
0answers
183 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
362 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 ...