All Questions
Tagged with co.combinatorics permutations
63 questions
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 ...
161
votes
37
answers
17k
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 ...
- 63.9k
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 ...
- 1,730
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 ...
3
votes
0
answers
193
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,...
- 15.6k
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 ...
- 2,993
22
votes
2
answers
2k
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 ...
- 1,021
12
votes
2
answers
758
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 ...
- 1,324
9
votes
0
answers
409
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 ...
- 50.8k
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, ...
- 82.7k
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 ...
- 13.4k
7
votes
1
answer
531
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. ...
- 15.6k
2
votes
1
answer
172
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, ...
- 4,938
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 ...
- 114k
42
votes
2
answers
2k
views
How decreasing can a bijection $f:\mathbb{N}\to\mathbb{N}$ be?
This is a follow-up to this question by
Dominic van der Zypen. For each bijection $f:\mathbb{N}\to\mathbb{N}$, let
$$\operatorname{rc}(f) := \liminf_{N\to\infty} \frac{\left|\left\{(m,n)\in\{1,\dots,N\...
- 10.6k
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(...
- 43.2k
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 ...
- 24.2k
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,...
- 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: ...
- 15.6k
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.
...
- 15.6k
15
votes
2
answers
481
views
Ehrhart period collapse for $123\ldots k$-avoiding Birkhoff polytope?
For $1 \leq r \leq n$, let $\mathcal{B}^n_r$ denote the polytope of all real matrices
$$ \pi = \begin{pmatrix} \pi_{1,1} & \pi_{1,2} & \cdots & \pi_{1,n} \\
\pi_{2,1} & \ddots & \...
- 24.2k
13
votes
1
answer
637
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 $\...
- 43.2k
13
votes
2
answers
841
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}; \\...
- 24.2k
13
votes
1
answer
497
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 ...
- 593
12
votes
2
answers
292
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 ...
- 333
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 ...
- 367
12
votes
0
answers
643
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$....
- 43.2k
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 ...
- 263
10
votes
1
answer
694
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 $...
- 4,938
10
votes
1
answer
492
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$...
- 325
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 $\...
- 101
9
votes
2
answers
500
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\}|$. ...
- 24.2k
9
votes
0
answers
398
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^{\...
- 148k
9
votes
1
answer
460
views
Min–max reversing bijections $f:\mathbb{N}\to\mathbb{N}$
For any set $X$, let $\newcommand{\N}{\mathbb{N}}[X]^2 = \big\{\{x,y\}:x\neq y \in X\big\}$ and set $[n]^2 = [\{0,\dotsc,n-1\}]^2$ for any positive integer $n$. For $A\subseteq [\N]^2$ we set $$\...
- 48.9k
8
votes
1
answer
358
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 "...
- 24.2k
7
votes
1
answer
509
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,\...
- 15.6k
6
votes
1
answer
703
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 $\...
- 188k
6
votes
1
answer
500
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$ ...
- 20.2k
6
votes
2
answers
394
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$ ...
- 15.6k
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 ...
- 71
6
votes
1
answer
429
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 ...
- 20.2k
5
votes
2
answers
261
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)$ ...
- 48.9k
5
votes
1
answer
175
views
Equivalence class of permutations based on cycle decomposition and their inverses
An equivalence class of permutations has come up in my research, and I'm wondering if anybody knows if it's named or has been studied before. If so, I'd appreciate being pointed towards more ...
- 53
5
votes
2
answers
245
views
Counting transitive generators according to coset type
Let $\sigma=(1\;2)(3\;4)\cdots (n-1\; n)$ be a fixed-point-free involution in $S_{2n}$. I want to count permutations $\pi$ such that the group $\langle \pi,\sigma\rangle$ generated by $\pi$ and $\...
- 1,549
5
votes
1
answer
2k
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 ...
- 4,952
4
votes
2
answers
2k
views
How to compute the rook polynomial of a Ferrers board?
Given a Ferrers board of shape $(b_1,\ldots,b_m)$, we define $r_k$ as number of ways to place $k$ non-attacking rooks (as in Chess). In section 2.4 of Stanley's Enumerative Combinatorics (vol. 1) it's ...
- 1,015
4
votes
1
answer
158
views
Counting "deflected" permutations: Part I
Let $\mathfrak{S}_n$ denote the group of permutations on $\{1,2,\dots,n\}$. Now, introduce the sets
$$\mathcal{A}_n^{(k)}:=\{\pi\in\mathfrak{S}_n: -1\leq \pi(j)-j\leq k,\,\forall j\}.$$
I would like ...
- 43.2k
4
votes
0
answers
206
views
Non-crossing and crossing bijection in higher genus
This is a follow-up question of my SO post I'll briefly mention it here.
So given a $n$ cycle say $(1,2,\ldots,n)$, what are the monotonic 2 -tuples, of the form $(a,b)(c,d)$, monotonicity in on the ...
- 685
4
votes
1
answer
597
views
genus zero permutation and noncrossing partition
Question
Let $g$ to be an element of permutation group $S_n$, and $\tau = (1,2,3,\cdots,n)$ is the circular permutation. $g$ and $\tau g$ have $n+1$ cycles in total(fixed point is also a cycle), ...
- 165
4
votes
0
answers
98
views
Counting cycles after permuting within rows and columns
Consider a rectangular $p \times q$ array, labelled by the numbers $0, \ldots, pq - 1$ for convenience. Let $S_p$ and $S_q$ and $S_{pq}$ denote the symmetric groups. Take a family of permutations:
$...
- 13.3k