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
420 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 ...
9
votes
0answers
232 views

How is $\mathrm{PGL}(V)$ a subgroup of $\mathrm{P\Gamma L}(V)$?

I've stumbled upon a strange exercise while reading "Notes on Infinite Permutation Groups" by Bhattacharjee, Möller, Macpherson and Neumann. If you have the book, the exercise is 7(ix) on page 66. ...
8
votes
0answers
175 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
131 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
112 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
40 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
208 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
67 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
208 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
38 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
92 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
55 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
99 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
126 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
90 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
112 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
79 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
60 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 ...
3
votes
0answers
39 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
60 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
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
149 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
110 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
66 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
168 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
179 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
66 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
87 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
133 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
215 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
133 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
52 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
30 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 ...
2
votes
0answers
20 views

How to calculate total results of combinations of letters

I am programmer and have developed an algorithm to run a processor intensive function on all the permutations of 2 letters (X and O) when we define how many X's and O's there will be. For example, I ...
2
votes
0answers
41 views

The $8$-Puzzle and $2$-Cycles

I have been studying the $8$-puzzle and have thus far managed to wrap my head around the following information: The following illustrates the solved position of the $8$-puzzle, where $9$ is the empty ...
2
votes
0answers
46 views

Permutation and Combination- Rowing a Boat

The crew of an 8 member rowing team is to be chosen from 12 men, of which 3 must row on one side only and 2 must row on the other side only. Find the number of ways of arranging the crew with 4 ...
2
votes
0answers
43 views

Ways of Assigning Grades to Students

I was reading somewhere that the number of ways 10 students could be assigned the grades A,B,C,F would be $4^{10}$. However, that seems to be counting sequences such as AABCFBFAFC and switching the ...
2
votes
0answers
35 views

Multinomial problem

Suppose one has a nested table of disitnct primes then the permutations of their products produce dupluicates at certain values. For example, letting the primes $\{a,b\}=\{2, 3\}$, the products of ...
2
votes
0answers
38 views

give a group that is isomorphic to the figure.

I think if I get help with one of these I should be good on the rest. 23) is concerned with figure a) It has one symmetry and 4 possible points. seems like it would have two elements that map to ...
2
votes
0answers
39 views

How to combine possible permutations of two sets to find number of combined permutations

I hope the title accurately describes the question. I have a question that asks: There are 7 male swimmers and 5 female swimmers. If there is a gold, silver, and bronze medalist male swimmer, and a ...