All Questions
Tagged with co.combinatorics permutations
109 questions with no upvoted or accepted answers
27
votes
0
answers
940
views
A question on simultaneous conjugation of permutations
Given $a,b\in S_n$ such that their commutator has at least $n-4$ fixed points, is there an element $z\in S_n$ such that $a^z=a^{-1}$, and $b^z=b^{-1}$? Here $a^z:=z^{-1}az$.
Magma says that the ...
- 271
23
votes
0
answers
1k
views
Do all possible trees arise as orbit trees of some permutation groups?
I.Motivation from descriptive set theory
(Contains some quotes from Maciej Malicki's paper.)
The classical theorem of Birkhoff-Kakutani implies that every metrizable topological group G admits a ...
- 181
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
10
votes
0
answers
430
views
321-avoiding and parity-alternating permutations
It is classical that 321-avoiding permutations are enumerated by the Catalan numbers.
A permutation is parity-alternating if it sends even integers to even integers, and odd integers to odd. I am ...
- 15.8k
10
votes
0
answers
302
views
Are plactic classes convex under the right weak Bruhat order?
For those who are unfamiliar with the terminology, I'll explain a little.
The symmetric group $S_n$, as a type A Coxeter group, has generators $\{s_1,\ldots,s_{n-1}\}$ with relations (1) $s_i^2$ for ...
- 331
9
votes
0
answers
180
views
Are there fast rank and unrank algorithms for integer vectors under the action of a permutation group?
We are distributing $m$ indistinguishable balls in $k$ numbered boxes $S=\{1,2,\ldots,k\}$. A distribution is a tuple of nonnegative integers $a=(a_1,\ldots,a_k)$ whose sum is $m$. We also have a ...
- 4,219
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
9
votes
0
answers
534
views
Generating $S_n$ with a fundamental transposition and a big cycle
I apologize in advance if this is too amateur, this is not really my area, but I'm very curious.
We have a permutation $\pi \in S_n$ and we want to represent it as a product of $\sigma = (1\;2)$ and $...
- 231
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
0
answers
275
views
pattern-avoiding permutations vs multi-core partitions
Let $\mathfrak{S}_n$ be the permutation group on $[n]$. Given the pattern $\sigma=k(k-1)\cdots321$, let $I_n(\sigma)$ be the number of involutions in $\mathfrak{S}_n$ that avoid the pattern $\sigma$. ...
- 43.2k
9
votes
0
answers
213
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 ...
- 27.8k
8
votes
0
answers
171
views
Inversions for parity preserving presentations
I've gotten stuck on a slightly random combinatorial question, and I'm doing a bit of a shot in the dark here to see if someone else has thoughts about it. I'm interested in studying a permutation of ...
- 44.7k
8
votes
0
answers
331
views
A question related to Young symmetrizers
Let $T$ be an arbitrary Young tableau (i.e., filling of the diagram of an integer partition $\lambda$ of $n$ by the numbers from $1$ to $n$, each appearing once). Let $R(T)$ be the subgroup of ...
7
votes
0
answers
150
views
Question about function on permutations
The following question is motivated by my research.
Let's consider a permutation $\sigma$ of the set $\{1, \ldots, n\}$. We define an element $i \in \{1, \ldots, n\}$ to be locally minimal for $\sigma$...
- 4,736
7
votes
0
answers
116
views
A conjecture on circular permutations of n elements in an abelian group of odd order
In 2013 I formulated the following conjecture in additive combinatorics.
Conjecture. Let $G$ be an additive abelian group of odd order, and let $A$ be a subset of $G$ with $|A|=n>2$. Then, there is ...
- 15.6k
7
votes
0
answers
228
views
How many permutations do you need to force fixed points?
For simplicity let $k$ be given fixed, and $n$ grows large. We are interested in a small set $M_n={g_1,...,g_m}$ of permutations in $S_n$, s.t for all $a\in S_n$, there is $g_i \in M_n$ with $ag_i$ ...
- 515
7
votes
0
answers
120
views
equidistribution of the number of occurrences of a vincular pattern, and a simpler vincular pattern
This is (at least for now) a question out of curiosity, there is no "deeper" meaning to it I know of. In fact, my main question is: is the observation below obvious?
To state the observation I have ...
- 849
7
votes
0
answers
107
views
Smallest set of couples in [n] stable by permutations
I am dealing with the following problem :
I need to create the smallest possible set $\{(x_i,y_i) \in [n]^2, x_i\neq y_i\}$ for $n$ given, such that :
$\forall p \in \mathcal{S}_n, \exists i,j$ such ...
- 189
7
votes
0
answers
204
views
Bound on coefficients in Young tableuax
The following may be known, but I didn't find anything in the literature.
Background:
The irreducible representations of $S_n$ correspond to shapes of Young tableaux with $n$ elements. Let $\lambda$ ...
- 410
6
votes
0
answers
254
views
Maximal bijection-dodging families on $\mathbb{N}$
We say that a family ${\cal S}\subseteq{\cal P}(\mathbb{N})$ is bijection-dodging if there is a bijection $\varphi:\mathbb{N}\to\mathbb{N}$ with $\varphi(T)\notin {\cal S}$ for all $T\in{\cal S}$.
...
- 48.9k
6
votes
0
answers
115
views
Distribution of peaks in permutations, after a sorting operation
Let $S_n$ be the set of permutations on $\{1,2,\dotsc,n\}$.
A peak-value of $\pi$ is some $\pi_i$ such that $\pi_{i-1} < \pi_i > \pi_{i+1}$, where $1<i<n$. Let $PV(\pi)$ denote the set of ...
- 15.8k
6
votes
0
answers
189
views
$X$-rays of permutations
Consider the set of permutations $\mathfrak{S}_n$, on $\{1,2,\dots,n\}$, and identify each element $\pi\in\mathfrak{S}_n$ with the corresponding permutation matrix.
There has been some study (e.g. ...
- 43.2k
6
votes
0
answers
240
views
Factorization of permutations into two factors with fixed number of cycles, plus a placement condition
In my recent work I have been led to consider the following type of permutation factorizations.
Let $\pi_1$ and $\pi_2$ be two fixed permutations, with disjoint support, i.e. $\pi_1$ acts on $\{1,......
- 2,552
6
votes
0
answers
256
views
Counting Selections of Entries such having an Extremal Permutation of length n^2+1
Let $S_{n^2+1}$ be permutations of length $n^2+1$. By Erdos-Szekeres Theorem. any $s \in S_{n^2+1}$ would have a monotone subsequence(increasing or decreasing)of length $n+1$.
Say a permutation $s$ of ...
- 393
5
votes
0
answers
152
views
Variant of the pancake problem
For two permutations $\pi,\tau \in S_n$, we say they are related by a prefix reversal if there exists $t$ such that $\tau(i) = \pi(i)$ for $i\ge t$ and $\tau(i) = \pi(t-i)$ for $i<t$. Similarly, we ...
- 3,499
5
votes
0
answers
350
views
Sum over permutations involving sign
The problem is to evaluate the following sum over all permutations $\sigma\in S_{d}$ of $\{1,2,...,d\}$:
$\displaystyle\sum_{\sigma\in S_{d}}\text{sgn}(\sigma)\displaystyle\frac{1}{\prod_{i=1}^{d}(\...
- 1,538
5
votes
0
answers
158
views
Dirichlet eta function and Stirling Permutations
The Stirling permutations of order $k$ is a permutation of the multiset $1, 1, 2, 2, ..., k, k$. The Dirichlet $\eta$-function is a function closely related to the Riemann $\zeta$-function.
According ...
- 155
5
votes
0
answers
175
views
A close cousin of involutions?
If $\mathfrak{S}_n$ denotes the permutation group on $n$ letters, then $Inv(n)=\{\pi: \pi^2=1\}\subset\mathfrak{S}_n$ is the set of involutions or
self-inverse permutations. The latter is enumerated ...
- 43.2k
5
votes
0
answers
181
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 ...
- 50.8k
4
votes
0
answers
124
views
LIS-based permutation property
Let $S_n$ be the set of all permutations of $\{1, \ldots, n\}$, thereafter treated as integer sequences. Let $A_n$ be the set of all such permutations $\sigma \in S_n$ that we can choose two ...
- 5,590
4
votes
0
answers
91
views
Reference for fact about flags of vexillary permutations
Vexillary permutations are an important family of permutations in Schubert calculus. There are several definitions, for example that they avoid the pattern 2143.
Recall the Lehmer code of a ...
- 1,989
4
votes
0
answers
155
views
Permutation generation problem using swaps
This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input.
We're given as input ...
- 2,993
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
0
answers
167
views
Binary iterations, Fibonacci numbers and permutation of natural numbers
Let $\operatorname{wt}(n)$ be A000120, i.e. the number of $1$'s in binary expansion of $n$ (or the binary weight of $n$).
Also let's consider
$$\ell(n)=\left\lfloor\log_{2} n\right\rfloor$$
and
$$T(n,...
- 4,938
4
votes
0
answers
145
views
Words that give rise to an enumeration of elements of the symmetric group
Let $\mathbb{S}_m$ be the symmetric group on $m$ letters. Let $n=m-1$. Let $\mathbf{w}=a_1\cdots a_r$ be a word on the alphabet $\{1,\ldots,n\}$. We say that $\mathbf{w}$ gives rise to an enumeration ...
- 1,066
4
votes
0
answers
246
views
Distance properties of the permutations of a set of points in a Euclidean space
We are given a set of $n$ distinct points $S=\{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\}$ in a Euclidean space $\mathbb{R}^d$, where the distance between two points $\mathbf{x}_i,\mathbf{x}_j\...
- 1,677
4
votes
0
answers
81
views
Number of orders of distances between points on a line
Points $a_1, a_2, \dots, a_n$ on a line form a set from $n(n-1)/2$ distances between them. Suppose all that distances are different, numerating them from the shortest to the longest one we obtain some ...
- 1,431
4
votes
0
answers
216
views
How frequent are permutations with small interleaving?
For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$.
Let $\pi$ be a permutation of $[n]$. For simplicity, assume that $\pi$ is an $n$-cycle. ...
- 20.2k
4
votes
0
answers
160
views
Is there a permutation $\pi\in S_n$ with $\sum\limits_{0<k<n}\frac1{\pi(k)^2-\pi(k+1)^2}=0$ for each $n>7$?
Let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$.
QUESTION: Is it true that for each $n=8,9,\ldots$ we have
$$\sum_{0<k<n}\frac1{\pi(k)^2-\pi(k+1)^2}=0\tag{$*$}$$
for ...
- 15.6k
4
votes
0
answers
165
views
Counting "deflected" permutations: Part II
This is the second sequel to my earlier question on MO. Although the the current problem appears very similar, the answer is certainly different as experiments indicate.
As usual, let $\mathfrak{S}_n$...
- 43.2k
4
votes
0
answers
207
views
Have wiring diagrams been generalized to arbitrary digraphs?
A "combinatorial wiring diagram" is a way to define a permutation by a drawing of a particular planar digraph. For example, this wiring diagram corresponds to the permutation $(3412)$:
In Coxeter ...
- 1,389
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
4
votes
0
answers
195
views
restricting "dances of minimal cost" (optimization on braids/permutations?)
Consider applying the permutation (1,3,0,5,2,7,4,6) to the integers (0,1,2,3,4,5,6,7) three times.
I call this a "dance of minimal cost" because all unordered pairs in {0..7} meet each other, and the
...
- 121
3
votes
0
answers
92
views
Realized graph of majority of permutations
This question was asked several months ago on Math.SE, but remains unsolved.
For any collection of permutations of $\{1,2,\dots,n\}$, we say that it realizes a directed multigraph with $1,2,\dots,n$ ...
- 277
3
votes
0
answers
121
views
Twisted permutations
We consider a set $E$ with an involution (having perhaps fixed points).
We denote orbits by $\lbrace x,\overline{x}\rbrace$ (with $\overline{x}=x$ in
the case of a fixed point).
We consider sequences $...
- 17.9k
3
votes
0
answers
151
views
Combinatorial interpretation of inverse modulo $2$ binomial transform of A284005
My question is related to the following:
Sum with products turned into subsequences
We have an identity
$$a(n, -1) = \sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}(-1)^{\operatorname{wt}(n)-\...
- 4,938
3
votes
0
answers
80
views
Counting sets whose alternation is preserved by a permutation
Say a set $X \subseteq \{1,\ldots,n\}$ is alternating if successive elements of $X$ are of opposite parity. That is to say for any $x \in X$, if $y = \min \{z \in X \mid x < z\}$ then $x \not\...
- 31
3
votes
0
answers
282
views
A new combinatorial problem for finite groups
In a recent preprint arXiv:1811.10503, I proved that if $a_1,\ldots,a_n$ are distinct elements of a torsion-free additive abelian group $G$, then there is a permutation $\pi\in S_n$ such that all ...
- 15.6k
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
3
votes
0
answers
131
views
Chen primes and permutations
In 1973 the Chinese mathematician J.-R. Chen proved that there are infinitely many primes $p$ such that $p+2$ is a product of at most two primes. Nowadays such primes $p$ are called Chen primes.
For $...
- 15.6k