All Questions
32 questions
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 ...
- 12.9k
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 $...
- 63.9k
15
votes
5
answers
7k
views
infinite permutations
This question is related to this one: Continued fractions using all natural integers. Suppose we have the set of natural numbers $N$ with order and we perform permutation on it. So we obtain the same ...
- 1,446
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 ...
- 18.4k
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$ ...
CommunityBot
- 1
0
votes
1
answer
284
views
Given the index of two permutations, Is there a direct way to compute the index of their composition? [closed]
Suppose you are given two indexed permutations, (7 followed by 4, for instance)
What is the best way to go about finding their composition, given the indices themselves? I'd imagine that the answer ...
- 6,237
5
votes
1
answer
201
views
An Indepth Look at Isoperimetry in the Cayley Graph Generated by All Transpositions
Let $\Omega_n$ denote the symmetric/permutation group on $n$ objects.
Let $T_n \subseteq \Omega_n$ denote the set of transpositions.
Drop the $n$-subscripts.
Define the Cayley graph $G = (\Omega, E)$ ...
- 14.2k
1
vote
1
answer
590
views
The number of permutations of given order
I want to count the number of permutations of the given order $k$ in $S_n\;(\sigma^k=id,\sigma^l\neq id\;for\;l<k)$. I found some works about that problem, but they are more general than necessary. ...
- 17k
28
votes
1
answer
2k
views
Multiplying all the elements in a group
Let $G = \{ g_i | i = 1, ...,n \}$ be a finite group and denote by $G!$ the multiset consisting of all the products of all different elements of $G$ in any order, that is
$$ G! = [ \prod_i g_{\sigma(i)...
- 1,889
0
votes
0
answers
126
views
Combinatorics of merging sequences from multinomial coefficients
If you have $m$ sequences $a_{11},\dots,a_{1n_1}$ through $a_{m1},\dots,a_{mn_m}$ each sorted in ascending order (assume there are no duplicates) then there is an unique way to merge them.
How many ...
- 1,826
40
votes
1
answer
2k
views
Orders of products of permutations
Let $p$ be a prime, $n\gg p$ not divisible by $p$ (say, $n>2^{2^p}$). Are there two permutations $a, b$ of the set $\{1,...,n\}$ which together act transitively on $\{1,2,...,n\}$ and such that all ...
CommunityBot
- 1
3
votes
1
answer
158
views
Multiplication in $Z(\mathbb{C}S_n)$ [duplicate]
I am trying to multiply two generators of center $Z(\mathbb{C}[S_n])$ of ring algebra of symmetric group of $n$ elements. We know that these generators are given by sums of conjugacy classes in $S_n,$ ...
- 2,821
-3
votes
1
answer
961
views
Maximum element order in $S_n$ [closed]
Denote by $S_n$ the group of permutations of the set $\{1,\ldots,n\}$ with composition as binary operation. Let $m_n$ denote the maximum order that an element of $S_n$ can have. What is the smallest ...
- 105k
3
votes
4
answers
654
views
A generalization of Landau's function
For a given $n > 0$ Landau's function is defined as $$g(n) := \max\{ \operatorname{lcm}(n_1, \ldots, n_k) \mid n = n_1 + \ldots + n_k \mbox{ for some $k$}\},$$
the least common multiple of all ...
- 13k
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
2
votes
0
answers
85
views
Permutation factorizations according to number of generated orbits
Let $\pi$ be a permutation in $S_n$ with cycle type $\lambda$.
How many factorizations into two factors $\pi=\sigma_1\sigma_2$ are there, such that the subgroup $\langle \sigma_1,\sigma_2\rangle$ ...
- 2,552
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 $\...
- 2,552
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
13
votes
1
answer
409
views
When is the union of a graph and a random permutation thereof connected?
First things first: in what follows, a "random permutation" of a set $\Omega$ with $n$ elements does not necessarily mean an element chosen uniformly at random from $\textrm{Sym}(\Omega)$. Rather, and ...
- 30.1k
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
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
2
votes
2
answers
243
views
$n$-distant permutations more than not
Let $\mathfrak{S}_{2n}$ be the permutation group of the letters $[2n]=\{1,2,\dots,2n\}$. Call a permutation $\pi\in\mathfrak{S}_{2n}$ has an $n$-distant pair if there is some $j\in [2n-1]$ such that $\...
- 34.3k
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 ...
- 33.8k
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 $\...
- 34.3k
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
3
votes
1
answer
200
views
Braid group: Can a left-twist increase the number of right twists?
Disclaimer: This question was first posted on math.se without any answer.
This is something that naturally occurs in my research, but I am no expert on this - it feels like a natural question so I am ...
CommunityBot
- 1
4
votes
1
answer
325
views
Hyperoctahedral group acting on a special permutation
Let $[n]=\{1,...,n\}$ and $[\hat n]=\{\hat 1,...,\hat n\}$. Realize the hyperoctahedral group $H_n$ as the centralizer of the permutation $(1\hat 1)\cdots (n \hat n)$. It has $2^n n!$ elements.
Let $...
- 525
7
votes
2
answers
751
views
Looking for deterministic criteria to generate the symmetric group?
So let $S_N$ be the symmetric group of degree $N$. We think of it as a permutation group via its
natural action on the set $T=\{1,2,\ldots,N\}$.
Say that $H\leq S_N$ is a subgroup which acts ...
- 6,357
15
votes
2
answers
512
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 $\pi.(\sigma_1,\...
CommunityBot
- 1
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 ...
CommunityBot
- 1
4
votes
2
answers
462
views
Distinguishing finite-orbit permutation groups by action on tuples
Let $G$ and $H$ be permutation groups on the natural numbers such that the orbits of $G$ and $H$ are all finite. Suppose that for all $\pi \in Sym(\mathbb{N})$, there is some $N$ (depending on $\pi$) ...
- 4,728
11
votes
2
answers
3k
views
Algorithm for decomposing permutations
Is there an algorithm for solving the following problem: let $g_1,\ldots,g_n$ be permutations in some (large) symmetric group, and $g$ be a permutation that is known to be in the subgroup generated by ...
- 18.6k