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

learn more… | top users | synonyms

2
votes
0answers
124 views

Permutation equivalence classes with kendall-tau distance

I asked this question on Stack Exchange a few days ago with no help. I am not sure if the question seems too trivial or of not enough general interest to get any attention. Anyway, any sort of ...
0
votes
1answer
201 views

A question on permutations

Given integers $1$ through $n$, let $S$ be set of ordering of integers that respect even alternating or reverse alternating permutations (https://en.wikipedia.org/wiki/Alternating_permutation) up to ...
2
votes
0answers
50 views

Even cycle constrained edge coloring

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...
0
votes
0answers
64 views

A constrained minimum edge coloring

Is minimum number of colors needed to color edges of complete graph $K_n$ so that every even simple cycle contains at least one color assigned to odd number of edges at most $\beta n$ where ...
5
votes
0answers
132 views

Extrapolation between longest increasing and longest alternating subsequences

The question When should we expect Tracy-Widom? motivated me to post the following question, in which I have been interested for a while. Let $f(n)$ be a function from the positive integers to ...
2
votes
0answers
23 views

Terminology for research on distributions of inner products

Consider a set of vectors $M$ from an inner product space $V$. The ordered set of inner products of all pairs of elements in $M$ uniquely characterizes $M$ up to isomorphism. Suppose now that $V$ is ...
5
votes
3answers
475 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
38 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
82 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
129 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
161 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 ...
26
votes
3answers
1k 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
241 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
297 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
80 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
104 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
367 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
50 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
63 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
135 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
524 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
72 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
220 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
321 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
230 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
208 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
852 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
169 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
318 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
2answers
220 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
378 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
168 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
477 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
322 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
219 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
257 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
726 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
131 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
738 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
241 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
188 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
229 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
114 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
889 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
717 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
120 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 ...