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

learn more… | top users | synonyms (1)

18
votes
0answers
544 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 ...
12
votes
0answers
112 views

Covering pairs with permutations

Consider an $n \times n$ matrix $M_n$ with the following properties: Each row is a permutation of $A_n \equiv \{1, 2, ..., n\}$. Every ordered pair $(i,j)$, $i,j \in A_n$, $i \neq j$, appears as a ...
9
votes
0answers
190 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 ...
8
votes
0answers
94 views

How many ways can I arrange the numbers $1$ to $N$ with this divisibility condition?

For the numbers $1, \ldots, N$, how many ways can I arrange them such that either: The number at $i$ is evenly divisible by $i$, or $i$ is evenly divisible by the number at $i$. Example: for N = 2$...
7
votes
0answers
87 views

What is the criterion for a matrix containing vectors and their permutations being invertible?

Consider the matrix $A\in\mathbb{R}^{m\times 2m}$. Let any arbitrary choice of $m$ columns of $A$ be linearly independent. Together with a permutation $P\in\mathcal{P_{2m}}$, one can build the matrix $...
7
votes
0answers
150 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 ...
7
votes
0answers
154 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
197 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
60 views

At what rate does the entropy of shuffled cards converge?

Consider a somewhat primitive method of shuffling a stack of $n$ cards: In every step, take the top card and insert it at a uniformly randomly selected one of the $n$ possible positions above, between ...
6
votes
0answers
120 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 ...
5
votes
0answers
241 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
85 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
142 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 (http://en.wikipedia.org/...
5
votes
0answers
225 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 ...
5
votes
0answers
50 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
104 views

Number of ways to arrange $n$ numbers based on their relative values to each other

EDIT I've found a formula to solve this question, but I don't understand the reasoning behind it. Can someone explain this formula? $s(n - 1, x + y - 2) \times C(x + y - 2, x - 1)$ $s$ being ...
4
votes
0answers
51 views

Abstract algebra: for a polynomial $p$, prove $\sigma(\tau(p))=(\sigma\tau)(p)$ for all $\sigma, \tau \in S_n$

I'm trying to solve to following problem: Part 1: Let $\{x_1,...x_n\}$ be variables. For any polynomial $p$ in $n$ variables and for $\sigma$ $\in S_n$ define $\sigma (p)(x_1,...,x_n)=p(x_{\...
4
votes
0answers
39 views

Sharply $2$-transitive subgroup of a group

My question is about the problem 2.8.14 of the book "Permutation Groups" by Dixon and Mortimer. Let $F=F_q$ be the finite field with $q$ elements and $d\ge 1$. For each linear transformation $a \in ...
4
votes
0answers
48 views

Need a book recommendation for the Symmetric Group (Permutations)

I am looking for a textbook to read about permutations. Looking for something to cover such topics as: Representation of permutations (2-line arrays, cycles, bipartite graphs), inverses, involutions, ...
4
votes
0answers
139 views

Parity of a Permutation and Shifting

Given a permutation $P$ of $[1,2,...,n]$ and a positive integer $t\le n$. An operation is defined as shifting any $t$ consecutive elements of $P$ cyclically to the right by one index. For example: ...
4
votes
0answers
82 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
137 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
84 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 $$3!\int\...
4
votes
0answers
492 views

Count swap permutations

Given an array A = [1, 2, 3, ..., n]: ...
4
votes
0answers
145 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
375 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 ...
4
votes
0answers
81 views

Projectivizing a group: how to go from AGL(n,K) to PGL(n+1,K)

$ \newcommand{\GL}{\operatorname{GL}} \newcommand{\AGL}{\operatorname{AGL}} \newcommand{\PGL}{\operatorname{PGL}} $Given an irreducible matrix group $G_{\infty,0} \leq \GL(n,K)$, I form the group $G_\...
4
votes
0answers
111 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
89 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
80 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
81 views

Optimal cyclic permutations (Formulate as standard problem)

How can we find cyclic permutations $\prod_i$ to be applied to each of corresponding $i$'th rows of a square matrix $X$ of size $n \times n$ such that a given sum of pairwise costs $\sum_{ij}C\left[\...
3
votes
0answers
40 views

Isomorphism of Non-Symmetric Matrix when Permutation-Set is given: A simple observation

Context: Consider, two $m \times n$ matrices $A, B$ such that there is a permutation $\kappa$ that such that such that $A^{\kappa}=B$ (Wielandt's notation), i.e. $A, B$ are isomorphic but not ...
3
votes
0answers
21 views

Determinant of $\delta$ function

Let $$\delta_i^j=\left\{ \begin{aligned} 1 ~~~~~~i=j \\ 0 ~~~~~~i\ne j \end{aligned} \right. $$ $1\le i,j\le n$. How to prove $$ \begin{vmatrix} \delta_{j_1}^{i_1} ~...~ \delta_{j_n}^{i_1} \\ \\ \...
3
votes
0answers
41 views

oligomorphic subgroups of $S_\infty$

Is it true that every oligomorphic subgroup of $S_\infty$ is not abelian? A subgroup of $S_\infty$ is said oligomorphic if its action on $\mathbb N^n$ has only finitely many orbits for each $n\in\...
3
votes
0answers
31 views

Discussion of $Z(A_4) = \{e\}$

I tried to answer the following question: Why does the fact that the orders of the elements of $A_4$ are $1,2$ and $3$ imply that $|Z(A_4)|=1$? My answer: Two cycles commute if and only if ...
3
votes
0answers
62 views

Is there a name for this generalization of the determinant?

In the context of averaging over network paths, I arrived at a certain generalization of the determinant for an $n\times n$ square matrix $A$, that is $$D_k(A) := \sum_{(j_1,j_2,...,j_n):\,\, |\{j_1,....
3
votes
0answers
36 views

Given a positive integer $m$, what is the smallest number $n$ such that $S_n$ contains an element of order $m$?

This was a question on a midterm I recently took, but I didn't do well on it (the question I mean), so I'd like to figure out the idea. I thought that since the order of a composition of disjoint ...
3
votes
0answers
32 views

Decomposition of sorting permutation in fewest amount of transpositions

I found that any permutation cycle of length n can be written as a product of n-1 two-level permutations or transpositions. However, there are many other ways to do this decomposition(but it has to ...
3
votes
0answers
38 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 $\operatorname{End}_{\mathbb{Q}G}(\...
3
votes
0answers
34 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
45 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
59 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 \sigma(...
3
votes
0answers
93 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
55 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
103 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
139 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 like,...
3
votes
0answers
84 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
56 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
55 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 ...