Questions tagged [permutations]

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

Filter by
Sorted by
Tagged with
160 votes
37 answers
15k views

Conceptual reason why the sign of a permutation is well-defined?

Teaching group theory this semester, I found myself laboring through a proof that the sign of a permutation is a well-defined homomorphism $\operatorname{sgn} : \Sigma_n \to \Sigma_2$. An insightful ...
Tim Campion's user avatar
  • 60.6k
45 votes
5 answers
3k 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 ...
Michael Hardy's user avatar
38 votes
3 answers
5k 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$$ Also,...
mathlove's user avatar
  • 4,727
37 votes
2 answers
3k 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 ...
Jean-Marc Schlenker's user avatar
30 votes
1 answer
1k 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 ...
Michael Hardy's user avatar
3 votes
0 answers
190 views

A conjectural lower bound for $|\{\sum_{k=1}^nka_k:\ a_1,\ldots,a_n\ \text{are distinct elements of }\ A\}|$

Motivated by Question 315568 of mine, I'm interested in the set $$S(n):=\bigg\{\sum_{k=1}^n k\pi(k):\ \pi\in S_n\bigg\}.$$ It is easy to see that $$S(1)=\{1\},\ S(2)=\{4,5\}\ \text{and}\ S(3)=\{10,...
Zhi-Wei Sun's user avatar
  • 14.4k
35 votes
1 answer
2k 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 ...
Mohammad Al-Turkistany's user avatar
21 votes
2 answers
1k 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 ...
Jonah Blasiak's user avatar
12 votes
2 answers
721 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 ...
Gwyn Whieldon's user avatar
9 votes
0 answers
392 views

Number of sets $S$ for which number of permutations in $S_n$ with descent set $S$ is odd

The descent set $D(w)$ of a permutation $w=a_1 a_2\cdots a_n\in\frak{S}_n$ is defined by $D(w)=\{ 1\leq i\leq n-1\,:\, a_i>a_{i+1}\}$. Given a set $S$, let $\beta_n(S)$ denote the number of ...
Richard Stanley's user avatar
8 votes
1 answer
1k views

Is there an efficient algorithm to check whether two matrices are the same up to row and column permutations?

Define $\mathcal M_n$ as the set of all $n\times n$ matrices with each entry either 1 or $x$. Two such matrices are equivalent iff they can be obtained from each other by swapping pairs of rows and ...
Wolfgang's user avatar
  • 13.2k
8 votes
3 answers
3k 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, ...
Timothy Chow's user avatar
  • 78.1k
7 votes
1 answer
520 views

Primes arising from permutations

Recently, Paul Bradley proved in arXiv:1809.01012 that for any positive integer $n$ there is a permutation $\pi_n$ of $\{1,\ldots,n\}$ such that $k+\pi_n(k)$ is prime for every $k=1,\ldots,n$ (cf. ...
Zhi-Wei Sun's user avatar
  • 14.4k
2 votes
1 answer
151 views

Permutation and its binary analog

Let $f(n)$ be A000045(n), i.e., Fibonacci numbers: $f(n)=f(n-1)+f(n-2)$ for $n>1$ with $f(0)=0$ and $f(1)=1$. Let $g(n)$ be A072649, i.e., $n$ occurs $f(n)$ times. The sequence begins with $$1, 2, ...
Notamathematician's user avatar
1 vote
0 answers
106 views

Hard instances for this graph isomorphism algorithm based on powers of weighted adjacency matrices?

In short, I found an algorithm for GI and the only hard instances I found so far are non-isomorphic strongly regular graphs with large automorphism groups. Q1 What are hard instances for the ...
joro's user avatar
  • 24.2k
47 votes
6 answers
5k 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 ...
Terry Tao's user avatar
  • 108k
28 votes
3 answers
3k views

Sum over permutations is 1

This might be easy, but let's see. Question 1. If $\mathfrak{S}_n$ is the group of permutations on $[n]$, then is the following true? $$\sum_{\pi\in\mathfrak{S}_n}\prod_{j=1}^n\frac{j}{\pi(1)+\pi(...
T. Amdeberhan's user avatar
24 votes
1 answer
1k views

Why 'excedances' of permutations? [closed]

For a permutation $\pi=\pi_1\pi_2\cdots\pi_n$ written in one-line notation, an index $i$ for which $\pi_i > i$ is usually called an 'excedance.' To me, this seems like a mispelling of what should ...
Sam Hopkins's user avatar
  • 22.7k
22 votes
4 answers
2k views

A necessary and sufficient condition for $(x_1,...,x_n)$ to be a permutation of $(1,...,n)$

Is there an easy proof of the following statement? $\forall$ $n>0 \in \mathbb N$, $ \exists$ $a\geq0 \in \mathbb N$ such that for any set of integers $(x_1,...,x_n)$ and $1\leq x_i \leq n$: $(x_1,...
JPF's user avatar
  • 341
21 votes
1 answer
1k views

Permutations $\pi\in S_n$ with $\sum_{k=1}^n\frac1{k+\pi(k)}=1$

Let $S_n$ be the symmetric group of all the permutations of $\{1,\ldots,n\}$. Motivated by Question 315568 (http://mathoverflow.net/questions/315568), here I pose the following question. QUESTION: ...
Zhi-Wei Sun's user avatar
  • 14.4k
19 votes
1 answer
3k views

A mysterious connection between primes and squares

Motivated by two previous questions of mine (cf. Primes arising from permutations and Primes arising from permutations (II)), here I ask a curious question which connects primes with squares. ...
Zhi-Wei Sun's user avatar
  • 14.4k
16 votes
4 answers
1k views

Determining if some permutation of a vector satisfies a system of linear equations

Let $A$ be a matrix and $x$ a fixed vector. How can we determine whether or not there exists a permutation matrix $P$ such that $APx=0$? Does this problem reduce to anything well-understood?
Jack M's user avatar
  • 633
16 votes
6 answers
13k views

Showing block diagonal structure of matrix by reordering

Suppose we have a block-diagonal matrix $M$, but the block diagonal structure is not immediately apparent from looking at the matrix because the rows/columns are shuffled. I wish to find a reordering ...
Szabolcs Horvát's user avatar
14 votes
1 answer
413 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 ...
Brendan McKay's user avatar
13 votes
1 answer
479 views

What's the dimension of the Lie algebra generated by transpositions on $n$ objects?

Define a Lie bracket on the group algebra of the permutation group $S_n$ in the following way: $$[\sigma, \tau] = \sigma\circ\tau - \tau\circ\sigma,$$ where $\sigma, \tau \in S_n$, and the ...
WunderNatur's user avatar
13 votes
1 answer
631 views

trace and involution permutations: Part I

Let $\operatorname{Inv}(\mathfrak{S}_n):=\{\pi\in\mathfrak{S}_n: \pi^2=1\}$ be the set of involutions in the symmetric group $\mathfrak{S}_n$. Denote $I_n:=\#\operatorname{Inv}(\mathfrak{S}_n)$. Let $\...
T. Amdeberhan's user avatar
13 votes
2 answers
821 views

Cycle generating function of permutations with only odd cycles

Let $\mathrm{ODD}(n)$ be the set of permutations in $\mathfrak{S}_n$ whose cycle lengths are all odd. It is known that $$ \#\mathrm{ODD}(n) = \begin{cases} ((n-1)!!)^2 &\textrm{ if $n$ is even}; \\...
Sam Hopkins's user avatar
  • 22.7k
12 votes
2 answers
286 views

Permutation search problems with no known $o(n!)$ algorithms

I am looking for problems for whose solution no known subfactorial algorithms are known. I am particularly interested in questions of isomorphism; that is, is there a permutation that converts one ...
Bryce Sandlund's user avatar
12 votes
4 answers
1k views

How many non-isomorphic abelian subgroups of the permutation group $S_n$?

I am interested in how many (pairwise non-isomorphic) subgroups of the permutation group $S_n$ are abelian. ($n \in \mathbb{N}$ arbitrary and possibly big) Are you aware of any references which treat ...
user7427029's user avatar
12 votes
0 answers
627 views

Wilf's conjecture: complementary Bell numbers

The complementary Bell numbers or Uppuluri–Carpenter numbers, denoted $\tilde{B}_n$, can be delivered by $$G(x):=\sum_{n\geq0}\tilde{B}_n\frac{x^n}{n!}=e^{1-e^x}.$$ Definition. Fix an integer $m\geq0$....
T. Amdeberhan's user avatar
12 votes
4 answers
2k views

Cyclic Permutations - but not what you think

This question is not about elements of $S_n$ that consist of a single $n$-cycle, though naturally it's related. Instead, consider permutations modulo the action of $(123\ldots n)$. That is, we ...
kcrisman's user avatar
  • 367
11 votes
1 answer
244 views

How many steps are required for double transitivity?

Let $A$ be a set of generators of $S_n$, or of a doubly transitive subgroup of $S_n$. Assume $e\in A$, $A=A^{-1}$. What is the least $k$ such that $A^k$ is doubly transitive as a set? That is, what is ...
H A Helfgott's user avatar
  • 19.3k
10 votes
3 answers
844 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 ...
Manfred Weis's user avatar
  • 12.6k
10 votes
1 answer
455 views

Generalization of symmetric functions

A $n$-variable function $f$ is a symmetric function if $$f(x_1,x_2, \ldots, x_n) = f(x_{\sigma(1)}, x_{\sigma(2)}, \ldots, x_{\sigma(n)})$$ for every permutation $\sigma \in S_n$. In particular, if $f$...
MMM's user avatar
  • 245
10 votes
1 answer
650 views

Existence of solution to these inequalities

They say that all mathematics problems eventually reduce to linear algebra or combinatorics. I have reduced mine to proving a solution exists for the following set of inequalities but have no idea how ...
Abhishek Parab's user avatar
10 votes
5 answers
1k 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 $\...
balli's user avatar
  • 101
10 votes
1 answer
672 views

Prime numbers from permutation

Let $P(n)$ of a sequence $s(1),s(2),s(3),...$ be obtained by leaving $s(1),...,s(n)$ fixed and reverse-cyclically permuting every $n$ consecutive terms thereafter; apply $P(2)$ to $1,2,3,...$ to get $...
Notamathematician's user avatar
9 votes
0 answers
388 views

When do almost all these invariants of tensors vanish?

Let $A,B,C,D$ be $n$-dimensional vector spaces over a field $k$. There is a natural homomorphism from the $mn^m$th tensor power $A^{\otimes (m n^m)} $ of $A$ to $k$ given by the determinant map $A^{\...
Will Sawin's user avatar
  • 135k
9 votes
2 answers
480 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\}|$. ...
Sam Hopkins's user avatar
  • 22.7k
8 votes
1 answer
350 views

Formula for number of permutations less than a given permutation in weak order

Let $w\in S_n$ be a permutation. Is there a reasonable "formula" for the number of elements of the initial interval $[e,w]$ of weak (Bruhat) order from the identity to $w$? In terms of what such a "...
Sam Hopkins's user avatar
  • 22.7k
7 votes
1 answer
1k views

Identity involving sum over permutations

In some work on QFT the following identity has come up: $$ \sum_{\sigma \in S_n}\sum_{j=1}^n \left(\sum_{l=1}^j w_{\sigma_l}\right)\prod_{i=1,i\neq j}^{n}\frac{1}{\sum_{l=1}^j z_{\sigma_l}-\sum_{l=1}^...
Petter's user avatar
  • 237
7 votes
1 answer
495 views

A permutation problem

Here I ask a question on permutations of $n$ distinct real numbers. QUESTION: Let $a_1,a_2,\ldots,a_n\ (n>1)$ be (pairwise) distinct real numbers. Is there a permutation $b_1,\ldots,b_n$ of $a_1,\...
Zhi-Wei Sun's user avatar
  • 14.4k
6 votes
2 answers
369 views

On the parity of $|\{(j,k):\ 1\le j<k\le\frac{p-1}2\ \&\ \ j(j+1)\ \text{mod}\ p\,>\,k(k+1)\ \text{mod}\ p\}|$ with $p$ prime

Let $p=2n+1$ be an odd prime, and let $a_1<\ldots<a_{n}$ be all the quadratic residues mod $p$ among $1,\ldots,p-1$. For $a\in\mathbb Z$ let $\{a\}_p$ be the least nonnegative residue of $a$ ...
Zhi-Wei Sun's user avatar
  • 14.4k
6 votes
1 answer
399 views

Permutations, skew-symmetric forms and degeneracy

Define a skew-symmetric form $(\cdot,\cdot)$ on $\mathbb{R}^{2k}$ by $$(e_i,e_j) = \begin{cases} 1 &\text{if $i<j$},\\ -1 &\text{if $i>j$},\\ 0 & \text{if $i=j$.}\end{cases}$$ Given ...
H A Helfgott's user avatar
  • 19.3k
6 votes
1 answer
578 views

How many permutations are there at a given Cayley distance from the identity?

Permutations $\sigma$ in the symmetric group $S_n$ can be characterized by their Cayley distance $C_\sigma$, being the minimal number of transpositions needed to convert $\{1,2,3,\ldots n\}$ into $\...
Carlo Beenakker's user avatar
6 votes
5 answers
2k views

Convert integer to permutation number

I have no idea how to achieve this, any help would be greatly appreciated and very useful to me. I have a loop in some computer code, that loops through every single combination of 7 on bits in a 64 ...
Tom's user avatar
  • 71
6 votes
1 answer
478 views

Rank and frequency of permutations

(a) Let $[n] = \{1,\dotsc,n\}$, and let $\pi:[n]\to [n]$ be a permutation. Define an $n$-by-$n$ matrix $A=A(\pi)$ as follows: $A_{i,j}=1$ if $j>i$ and $\pi(j)>\pi(i)$, $A_{i,j}=-1$ If $j<i$ ...
H A Helfgott's user avatar
  • 19.3k
5 votes
2 answers
317 views

Permutations $\pi\in S_{p-1}$ with $\frac1{\pi(1)\pi(2)}+\frac1{\pi(2)\pi(3)}+\cdots+\frac1{\pi(p-2)\pi(p-1)}+\frac1{\pi(p-1)\pi(1)}\equiv0\pmod{p^2}$

A well known congruence of Wolstenholme states that $$\frac1{1^2}+\frac1{2^2}+\cdots+\frac1{(p-1)^2}\equiv0\pmod{p}$$ for any prime $p>3$. For each $n=3,4,\ldots$ we clearly have $$\frac1{1\times2}+...
Zhi-Wei Sun's user avatar
  • 14.4k
5 votes
1 answer
778 views

How many normal subgroups a primitive group can have?

Let $G$ be a primitive permutation group of degree $n$, that is $G$ acts transitively and faithfully on a set consisting of $n$ elements and $G$ preserves no nontrivial partition of $X$. In a sense ...
Lior Bary-Soroker's user avatar
5 votes
2 answers
246 views

Neighboring number of a permutation

For any positive integer $n\in\mathbb{N}$ let $S_n$ denote the set of all bijective maps $\pi:\{1,\ldots,n\}\to\{1,\ldots,n\}$. For $n>1$ and $\pi\in S_n$ define the neighboring number $N_n(\pi)$ ...
Dominic van der Zypen's user avatar