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

**3**

votes

**2**answers

168 views

### Can all the sporadic groups be expressed as permutation groups based on a single big cycle?

Working on M11, I came up with that it can be generated using the following permutations:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[[2, 0, 1, 7], [3, 4, 5, 6]]
[[4, 0, 6, 7], [2, 3, 1, 5]]
[[0, 7], [4, 6], ...

**4**

votes

**2**answers

306 views

### Why does iterated indexing avoid cycles of length 5?

Start with a permutation $s_0$ of the numbers
$(1,\ldots,n)$, e.g., for $n=10$,
$s_0=(8,2,1,6,9,7,10,5,4,3)$.
Form $s_1$ by using the numbers in $s_0$ as indices into $s_0$.
So $s_1$ is composed of ...

**2**

votes

**2**answers

133 views

### $k$-th subset in order of increasing sum

I have an array of integers T[N] indexed from 1. For example T[1] = 1, T[2] = 4, T[3] = 5, T[4] = 9. Let's enumerate all subsets of this set in a certain order: increasing sum of the elements. In case ...

**3**

votes

**3**answers

131 views

### Characterizing (up to permutations) finite sequences of real numbers

Let $S=\{x_1,\cdots, x_N\}$ be a finite sequence of real numbers.
I am interested in characterizing the family of functions $F$ such that for any $f\in F$ the function
$$
c(\lambda) ...

**4**

votes

**1**answer

80 views

### Weights on cyclic orderings

Are there standard or known weights/metrics on cyclic orders?
Cyclic orderings are different ways of listing elements from a finite set, where you call two lists the same if they differ only by a ...

**5**

votes

**1**answer

94 views

### What is the criterion for a matrix containing vectors and their permutations being invertible?

Consider the matrix $A\in\mathbb{R}^{m\times 2m}$. Let any arbitrary choice of $m$ columns of $A$ be linearly independent. Together with a permutation $P\in\mathcal{P_{2m}}$, one can build the matrix ...

**7**

votes

**1**answer

114 views

### Weighted Permutation Sum

I am trying to find out a closed-form formula (or a generating function at least) for the number of permutations $\sigma$ that satisfy $$ S = \sum_{i = 1}^{n} i\sigma(i)$$ for a given value of $S$. We ...

**2**

votes

**0**answers

111 views

### How hard is recognizing a permutation that is a square for the shift product?

This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation ...

**8**

votes

**3**answers

452 views

### Is the Number of Carries in Integer-Addition Associative?

Is it true that the number of carries, when calculating the sum of a finite set of finite positive integers, is constant (i.e. independent of their permutation and the order in which the additions ...

**2**

votes

**0**answers

51 views

### symmetric points on symmetric spaces

Let $M$ by an $m$-dimensional symmetric space (or a general Riemannian manifold). The finite distinct points $p_1,p_2,\cdots,p_n\in M$ are said symmetric, if for any permutation $\sigma$ on ...

**1**

vote

**0**answers

36 views

### Finding optimal set of permutations [closed]

I have the following data set of a human population. The data set captures households and relationships of the persons living in those households. My problem is how to group the individuals into ...

**3**

votes

**1**answer

63 views

### convex hull of the set of permutations with one cycle

is there a way to describe the convex hull of the set of permutation matrices with exactly one non-trivial cycle?
or maybe I should ask for the convex hull of cycle matrices :
let $(i_{1},..,i_{k})$ ...

**0**

votes

**0**answers

39 views

### Sparse Matrix Reordering

Matrix reorderings are important for many direct solvers. Sometimes the objective
is to reduce the bandwith or the generated fill in by LU Decomposition.
I am interested in a reordering which reduces ...

**25**

votes

**5**answers

941 views

### How many rearrangements must fail to alter the value of a sum before you conclude that none do?

This will not be altogether unrelated to this earlier question.
For which classes $C$ of bijections from $\{1,2,3,\ldots\}$ to itself is it the case that for all sequences $\{a_i\}_{i=1}^\infty$ of ...

**0**

votes

**0**answers

58 views

### Efficient recognition of sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, I got interested in this sorting problem:
Input: a sequence $A$ of $2N$ positive integers.
...

**11**

votes

**1**answer

198 views

### A Collatz-like question about permutations

An answer to this question would provide an explicit counterexample to this question, but otherwise I don't know if it is interesting.
Consider all permutations $\pi$ on the natural numbers such that ...

**18**

votes

**1**answer

451 views

### Rearrangements that never change the value of a sum

I posted this question on math.stackexchange.com and so far the only answer posted (also mentioned in the comments under the question) shows that one of my rash initial guesses about the bottom-line ...

**0**

votes

**1**answer

211 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

**0**answers

63 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

**0**answers

79 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

**0**answers

138 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

**0**answers

27 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

**3**answers

641 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

**0**answers

39 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

**0**answers

101 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

**1**answer

135 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

**1**answer

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

**27**

votes

**3**answers

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

**1**answer

251 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

**1**answer

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

**3**

votes

**0**answers

87 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

**0**answers

125 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

**3**answers

378 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

**0**answers

52 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

**1**answer

65 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

**1**answer

145 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

**2**answers

567 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

**0**answers

74 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

**1**answer

222 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

**2**answers

328 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

**0**answers

235 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

**1**answer

211 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

**2**answers

871 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

177 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

**0**answers

322 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

**2**answers

239 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

**1**answer

391 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

**5**answers

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

**0**answers

190 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

**2**answers

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