For questions related to permutations, which can be viewed as re-ordering a collection of objects.

learn more… | top users | synonyms (1)

14
votes
0answers
457 views

Sorting of prime gaps

Let $g_i $ be the $i^{th}$ prime gap $p_{i+1}-p_i.$ If we re-arrange the sequence $ (g_{n,i})_{i=1}^n$ so that for any finite $n$ the gaps are arranged from smallest to largest we have a new sequence ...
8
votes
0answers
178 views

Functoriality of the correspondence between oligomorphic actions and $\aleph_0$-categorical theories

If a group $G$ acts on a set $X$, then the action is said to be oligomorphic if the number of orbits of $X^n$ under the action is finite for each $n$. There is a classic theorem in model theory that ...
7
votes
0answers
137 views

Expression of basis vectors of permutation modules in different bases.

Write $[n]:=\{1,\ldots,n\}$. For a partition $\lambda\vdash n$, I will write $[\lambda]$ for the Specht module that corresponds to $\lambda$, i.e. the complex vector space spanned by all standard ...
7
votes
0answers
194 views

Citation for subset complement result

Let $S = \{s_1, \ldots, s_n\} \subset \{1, \ldots, 2n\}$. Consider two operations on $S$, unfortunately both called complement in different setting: let $A(S) = \{1, \ldots, 2n\} \setminus S$ (set ...
6
votes
0answers
101 views

How many ways are there to fill up a $2n \times 2n$ matrix with $1, -1$?

How many ways are there to fill up a $2n \times 2n$ matrix with $1, -1$ so that each column and each row has exactly $n $ $1$'s and $n$ $-1$'s ? I tried for cases $n=1 , 2$ but the solutions were ...
6
votes
0answers
127 views

Knuth equivalence of unshuffles

For any permutation $\sigma\in S_k$ and any $i\in\left\lbrace 1,2,...,k\right\rbrace$, I will denote $\sigma\left(i\right)$ by $\sigma_i$. For any word $w$, I will denote by $\mathrm{st}w$ the ...
5
votes
0answers
222 views

Factorizations in the symmetric group

Notation notes: The cycle $(i,i+1,\dots,j)\in S_n$ is the permutation $(1)(2)...(i,i+1,\dots,j)\dots(n)$ in cycle notation. Motivation Given a factorization of a permutation into certain cycles ...
5
votes
0answers
73 views

largest permutation group of odd order

For general $n$, what is the largest subgroup of the symmetric group $S_n$ that has odd order? I have a feeling that it might be the Sylow 3-subgroup...ADDED: but it isn't, as Mark Bennet points out ...
5
votes
0answers
136 views

How find this $aA_{m+1}=\overline{\sigma_{0}\sigma_{1}\sigma_{2}\cdots\sigma_{m}}$

Question let $m$ is positive numbers,and such $m\ge 5$,and $$A_{m+1}=\overline{1234\cdots m}=1\times (m+1)^{m-1}+2\times (m+1)^{m-2}+\cdots+(m-1)\times (m+1)+m$$(or see ...
5
votes
0answers
147 views

Number of ways to order a list of permutations by swapping

I want to solve a problem and I have no idea how or where to begin. I don't even know if it's possible to solve. I tried to find any clues in books about discrete maths but I didn't find anything that ...
4
votes
0answers
68 views

Every non-regular minimal normal subgroup of a doubly transitive group is primitive and simple

Prove that every non-regular minimal normal subgroup $N$, of a doubly transitive permutation group $G$, is primitive and simple. I proved that $N$ is primitive; but how I can prove that $N$ is ...
4
votes
0answers
105 views

Cayley's theorem — more than one isomorphism

I've just been learning about Cayley's theorem and a couple of things occurred to me: We know that every finite group of order $n$ is isomorphic to some subgroup of $S_n$. But perhaps there are ...
4
votes
0answers
63 views

Permutation order statistics integral

Let $U_i$ be $[0,1]$ i.i.d. uniform random variables, for $i=1,\ldots,n$. As an example, let $n=3$. Now pick an ordering, say $x_1>x_2<x_3$. and consider the order statistics integral ...
4
votes
0answers
113 views

Proof “correctness” : Cycle structure of conjugate permutations

My Algebra lecturer is a very strict about proofs(w.r.t Completeness , correctness and format ) more so than I have encountered in the past or any of my lecturers of the courses I am take concurrent. ...
4
votes
0answers
93 views

Sign of some permutation.

I trying to find the sign of this permutation: $\left(\begin{array}{cccccccccc} 1 & 2 & 3 & \cdots & \cdots & \cdots & \cdots & \cdots & n-1 & n\\ 2 & 4 & ...
4
votes
0answers
82 views

Selecting k numbers out of N sorted numbers to a minimize a condition/Formula

A sorted list of $\mathbf N$ numbers is given. $X_1$ $\le$ $X_2$ $\le$ $X_3$ $\le$ .... $\le$ $X_N$ Select $\mathbf K$ Numbers - $Y_1$ , $Y_2$ , $Y_3$ , ..... , $Y_K$ - Such that the following ...
4
votes
0answers
125 views

Is there a name for such matrices

Let $Z$ be a $K \times K$ matrix. All its left diagonal elements are zero. Further it satisfies the following properties: 1.) $Z[ i ][ j ] = Z[j][i] > 0$ for $1 ≤ i < j ≤ K$. 2.) $Z[i][j]$ ...
4
votes
0answers
48 views

Classification of $n \times n$ matrix in which each two components differ in each row and column up to automorphism

Suppose, we define a class $A$ of $n \times n$ matrix as follows: $$\text{In each Row }i, \text{for any} j,k\ (1 \leq j,k \leq n )\ a_{ij} \neq a_{ik} $$ $$\text{In each Column }l, \text{for any } ...
4
votes
0answers
75 views

Expectation of Reciprocals Involving Permutations

Let $a_i$ be $n$ distinct real numbers. What is the expectation: $$\mathbb E_\sigma \left[ \sum_{i=1}^{n} \frac {1} {a_{\sigma(i)} - \sum_{j=1}^{i-1}a_{\sigma(j)}} \right] $$ where the expectation ...
3
votes
0answers
30 views

Minimal polynomial of endomorphism of permutation module

Let $G$ be a transitive permutation group on a set $\Omega$. If $n$ is the degree and $M\in\mathbb{Z}^{n\times n}$ is a symmetric matrix that is also contained in ...
3
votes
0answers
28 views

How many symmetries does the Cauchy-Schwarz inequality have?

The symmetries of the Cauchy-Schwarz inequality $(x_1^2 + \cdots + x_n^2)(y_1^2 + \cdots + y_n^2) \ge (x_1y_1 + \cdots + x_ny_n)$, as a subgroup of the symmetric group on the $2n$ letters $x_1,\ldots, ...
3
votes
0answers
38 views

Identity element of a group as a factorization of group elements.

For any group $G$ we readily verify that if $a,b,c\in G$ and $a*b*c=e$ , where $e$ denotes the identity element,then also: $b*c*a=e$ Indeed,let $b*c=x$.Then our problem amounts to: $a*x=e⇒x*a=e$ This ...
3
votes
0answers
35 views

Conjugation of permutations

In the group $S_n$ I usually use the fact that if $(a_1 a_2 \dots a_r) \in S_n$ is an r-cycle and $\sigma \in S_n$ then $\sigma (a_1 a_2 \dots a_r)\sigma^{-1} = (\sigma(a_1)\sigma(a_2) \dots ...
3
votes
0answers
82 views

Number of $n$-permutations for which ${\tau}^k = id$

I am curious about the formula(any closed form) for the number of $n$-permutations $\tau$ such that ${\tau}^{n-1} = id$. How about for the case ${\tau}^n = id$ ?
3
votes
0answers
42 views

On transitive constituents of a permuation group

Assume that the intransitive permutation group G has degree n and minimal degree n−1. If no transitive constituent of G has degree 1, then they all are faithful and all except one are regular. I ...
3
votes
0answers
41 views

Total number of possible graphs in a network with $m$ edges and $n$ vertices?

How do you calculate the total number of possible graphs in a network with $m$ undirected edges and $n$ vertices? No self-loops. For instance, if I have a network with $7$ vertices in it, I want to ...
3
votes
0answers
82 views

What is the motivation behind the study of pattern-avoiding permutations?

There is a ton of research on pattern-avoiding permutations (permutations that do not contain some designated permutation pattern). We're figuring out how to enumerate them, what random ones are ...
3
votes
0answers
64 views

Is there away to swap adjacent items in a sequence, such that each permutation occurs once?

Let's us say you have a finite sequence of things. Some are identical, some distinct. For example: $$\langle 2,5,7,2,3\rangle$$ Now, under what conditions can each permutation of a sequence be ...
3
votes
0answers
49 views

Find k such that, $\displaystyle\frac{n^{\underline k}}{n^k}<a$

How to find k here $\displaystyle\frac{n^{\underline k}}{n^k}<a$ ? With, $n^{\underline k}=n\cdot(n-1)\cdot...(n-k+1)$ and $(n>k,\ a>0)$ Of course if $k\approx n/2$ the inequality ...
3
votes
0answers
51 views

Naming elements of a group

Assume one comes across some set and constructs a finite groups out of these elements. One knows what group it is, names the elements from 1 to order of the group and constructs the multiplication ...
3
votes
0answers
36 views

(Counting problem) more challenging Modular N algebraic eqs - for combinatorics-permutation experts

Experts in algebra please help - Part II after Part I: we would like to know the number of solutions for this set of six of modular N algebraic equations: $$ x_1 y_2 = x_2 y_1 \pmod N \qquad (1) \\ ...
3
votes
0answers
51 views

What is the value of $1 + {{}^nP_2}/2 +{{}^nP_3}/3 + ~… ~ {}^nP_n/n $

What is the value of $1 + {{}^nP_2}/2 +{{}^nP_3}/3 + ~........... ~ {}^nP_n/n $ ${}^nP_r = \frac {n!} {(n-r)!}$ Attempt: $1 + {{}^nP_2}/2 +{{}^nP_3}/3 + ~........... ~ {}^nP_n/n $ $= 1 + \frac ...
3
votes
0answers
203 views

Classification of triply transitive finite groups

A permutation group $G$ on a set $X$ is said to be $k$-transitive if it is both transitive on $X$ and either $k=1$ or the point stabilizer $G_x$ is $(k-1)$-transitive on $X\setminus\{x\}$. Is ...
3
votes
0answers
142 views

Decomposition of disjoint cycles

Work out the decomposition in disjoint cycles for the following. a) (14)(12345) = (15)(234) b) (12)(2345) = (12345) c) (12)(23)(34) = (14)(24) d) (13)(1234)(13) = (143)(2) Can anyone tell me ...
3
votes
0answers
70 views

Probability/selection problem

Assume that we have $N$ items of $M$ distinct types in a closed bag. We also have $K$ bowls $(K \leq M)$ that can hold only items of same type. In the beginning bowls are empty. And bowls can hold a ...
3
votes
0answers
184 views

Count the number of restricted multigraphs

Suppose I have a multigraph with the following set of restrictions: every vertex can have up to $c$ edges two vertices can be connected by a maximum of $c-1$ edges loops may or may not be allowed ...
3
votes
0answers
189 views

Exceptional isomorphisms of classical algebraic groups

Let $k$ be an algebraically closed field of characteristic $p\geq 0$. An affine algebraic group $G$ is an affine variety over $k$ with a group structure such that multiplication and inversion are ...
3
votes
0answers
93 views

Dinner group rotation. Sixteen couples. Four couples per house. Each couple to meet all the others, no repetition.

I want to set up a rotation of sixteen couples with four couples per house so that all couples eventually have dinner together, no repetition. Each couple is to host one dinner. Meetings are monthly ...
3
votes
0answers
142 views

Is there a simple way to show that wreath product is associative?

Is there a simple way to show that wreath product is associative? If your proof is short, please write it explicitly. Thank you.
3
votes
0answers
232 views

Combinatorics Issue without repetitive combinations

We have 26 Boxes Labeled: Box 1, Box 2, Box 3 and so on. The boxes are in a specific order. We also have 15 rocks. Rocks are all identical. meaning Rock 1 is no different then Rock 2, or does not have ...
3
votes
0answers
137 views

Defining a signed involution

We define the displacement of $\pi$ as $\mathrm{disp}(\pi)=\sum_{i=1}^n|\pi(i)-i|$. I know that it's even. Could you help me to find a good signed involution of the set of permutation with ...
2
votes
0answers
49 views

I have a finite permutation group and access to a computer algebra system, how can I recognize the structure of the group?

I have a fixed permutation group $G$, and cannot tell which finite group it really is in a "human readable" way. I also have GAP. Is there a step by step computation to give me the structure of this ...
2
votes
0answers
55 views

A fashion victim puzzle

Consider $n \in \mathbb{N}$ fashion-sensitive kids, each wearing a T-shirt; for simplicity, kid $i \in \{1, \ldots, n\}$ initially wears shirt $i$. Tastes over the shirts are summarized in an $n ...
2
votes
0answers
55 views

How many anagrams of a given word exists with constraints

I saw many questions about anagrams here, but neither one fits my needs. Let's say we have the word MISSISSIPPI. I need to find the count for those anagrams that meet the criterias as follows: ...
2
votes
0answers
48 views

Use of permutation/combination in Geometric problems

There are $p$ points in space, no four of which are in the same plane with exception of $q$, which are all in the same plane. Find out how many planes there are each containing three of the points? ...
2
votes
0answers
55 views

Why does $\operatorname{SL}_2(3)$ only yield even permutations?

$\newcommand{\pa}[1]{\left(#1\right)} \newcommand{\pamat}[1]{\left(\begin{array}{cc} #1 \end{array}\right)}$ In an exercise lesson for Algebra 3, we were proven that the special linear groups over ...
2
votes
0answers
20 views

If $g=(n-j,\dots,n)$ and $\sigma\in S_{n-1}$, why are the inversions of $g\sigma$ the union of the inversions of $\sigma$ and $g$?

I can't see why a claim I'm reading is true. If $\sigma\in S_n$, let $R(\sigma)=\{(i,j):i<j,\ \sigma(i)>\sigma(j)\}$, i.e., $R(\sigma)$ is the set of inversions of $\sigma$. The set ...
2
votes
0answers
41 views

Cycle detection in a pseudo-Latin square

Given a matrix of size $m \times n$ with no repetition of values in rows or columns, is there an efficient method of detecting cycles? For example, here is a sample matrix: 3 5 2 9 7 4 ...
2
votes
0answers
24 views

On permutation notation

I am trying to write up a proof that the parity of permutations on finitely many letters is well-defined. I think I have a proof that involves the number of disjoint cycles that a permutation may be ...
2
votes
0answers
78 views

How many possible six-word sentences

A word is defined as a nonempty (possibly meaningless) sequence of letters. How many $6$-word sentences can be made using each of the $26$ letters of the alphabet exactly once? Generalise the result ...