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

learn more… | top users | synonyms (1)

13
votes
0answers
428 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
176 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
132 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
87 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
116 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 ...
6
votes
0answers
63 views

functions representable as a sum of two permutations

I am trying to prove that for every function $f:\mathbb{Z}/n\mathbb{Z}\to \mathbb{Z}/n\mathbb{Z}$ satisfying $\sum_if(i)=0$, there exist permutations $\pi_1, \pi_2:\mathbb{Z}/n\mathbb{Z}\to ...
5
votes
0answers
41 views

Number of representatives from states to from a comittee?

Among the three representatives to a conference from each of the fifty states, either none, one, or two of the representatives will be chosen for a large special committee. How many ways can this ...
5
votes
0answers
210 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
50 views

How to “see at a glance” the solution to the exercise “Show that $\langle (1,2,3… n),(1,2,3… m)\rangle$ contains a 3 cycle, if $1 < n < m$”?

I tried the commutator of the generators and it worked, but I had no real justification for making that computation. Is there a perspective from which trying the commutator is the "obvious" thing to ...
5
votes
0answers
71 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
209 views

Special Products of Transpositions

[Edit. Significantly expanded to add examples and (I hope) clarification. Feel free to skim by reading the gray boxes.] A colleague asked me for insights on a collection of special permutations, ...
5
votes
0answers
135 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 ...
4
votes
0answers
40 views

How many $4$ digit numbers with distinct digits can be formed using $0,1,2,3,4,5$?

So left most digit can be filled with $5$ (can't use $0$ there) then next one got $5$ option then $4$ and $3$. So the answer is $5\cdot 5\cdot 4\cdot 3 =300$. Is it correct ?
4
votes
0answers
63 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
97 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
58 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
105 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
132 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
91 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
120 views

Permutation: How many ways to put 7 people in 10 rooms?

How many ways can 7 people be placed into 10 rooms, if (only) 2 of them can’t share a room with anyone? I'm not sure how to go about this, mostly because of the "share a room" bit. I'm thinking I ...
4
votes
0answers
76 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
124 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
46 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
73 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
80 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
40 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
35 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
62 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
45 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
39 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
30 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
50 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
167 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
118 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
67 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
172 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
183 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
68 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
89 views

Counting number of distinct systems

This is an enumeration problem in conjonction with some lottery problems. Given an integer $N \ge 5$. Let a ticket be a set of 5 distinct integers between $1$ and $N$. Given an integer $T$ between ...
3
votes
0answers
138 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
223 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
134 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
46 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 ...
2
votes
0answers
53 views

Characterization of conjugacy classes of $A_n$: intuition

Note the following theorem (quoted after handouts by Keith Conrad (UoCT) found online): Let $\pi \in A_n$. Its conjugacy class (cc) in $S_n$ remains the same in $A_n$, or it breaks into two cc's of ...
2
votes
0answers
34 views

Idemptent of Young Tableaux

I've been studying representation theory of symmetric group on Tung's Group Theory in Physics. I understood that different Young Diagrams corresponds to inequivalent irreducible representations of ...
2
votes
0answers
64 views

Permutation problem with ordering persons in a line

We have the following problem: There are $p$ persons from each city. Consider $p \cdot n$ persons from $n$ different cities. The $p \cdot n$ persons stand in a line such that every person stands next ...
2
votes
0answers
27 views

Is the sequence generated by two permutations periodic?

It's quite easy to prove that given an application: $\sigma:[1,n]\to [1,n]$ we know that the sequence: $$Id_n,\sigma,\sigma^2,\sigma^3,\cdots,\sigma^m,\cdots $$ Is periodic after some index $k\leq ...
2
votes
0answers
56 views

Am I over counting?

Two chess players, A and B are going to play 7 games. Each game has three possible outcomes: a win for A (which is a loss for B), a draw (tie), and a loss for A (which is a win for B). A win is ...
2
votes
0answers
32 views

Please check my solution of a problem in combinatorics regarding partitions

A lift automatically operated has a further computer facility of recording how many people leave the lift at each floor. It starts at floor $1$ and goes up to floor $6$. If $8$ people consisting of ...