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

learn more… | top users | synonyms (1)

34
votes
3answers
3k views

What is the shortest string that contains all permutations of an alphabet?

What is the shortest string $S$ over an alphabet of size $n$, such that every permutation of the alphabet is a substring of $S$? I thought of this problem while reading a open problem on shortest ...
32
votes
1answer
2k views

Is War necessarily finite?

War is an cardgame played by children and drunk college students which involves no strategic choices on either side. The outcome is determined by the dealing of the cards. These are the rules. A ...
28
votes
7answers
4k views

How many lists of 100 numbers (1 to 10 only) add to 700?

Each number is from one to ten inclusive only. There are $100$ numbers in the ordered list. The total must be $700$. How many such lists? Note: if, as it happens, this is one of those math problems ...
27
votes
1answer
2k views

Six Frogs - Puzzle

I had come across a puzzle: The six educated frogs in the illustration are trained to reverse their order, so that their numbers shall read 6, 5, 4, 3, 2, 1, with the blank square in its ...
26
votes
2answers
696 views

Can $G≅H$ and $G≇H$ in two different views?

Can $G≅H$ and $G≇H$ in two different views? We have two isomorphic groups $G$ and $H$, so $G≅H$ as groups and suppose that they act on a same finite set, say $\Omega$. Can we see $G≇H$ as permutation ...
23
votes
1answer
561 views

“Efficient version” of Cayley's Theorem in Group Theory

I'm considering finite groups only. Cayley's theorem says the a group $G$ is isomorphic to a subgroup of $S_{|G|}$. I think it's interesting to ask for smaller values of $n$ for which $G$ is a ...
23
votes
6answers
25k views

Combination of smartphones' pattern password

Have you ever seen this interface? Nowadays, it is used for locking smartphones. If you haven't, here is a short video on it. The rules for creating a pattern is as follows. We must use ...
22
votes
2answers
628 views

Permutations with restriction

We have $n$ types of objects, and the number of objects of type $i$ is $a_i$, $1\leq i\leq n$. What is the number of permutation of the $\sum_{i=1}^n a_i$ objects, if no two objects of the same type ...
20
votes
4answers
5k views

How does one compute the sign of a permutation?

The sign of a permutation $\sigma\in \mathfrak{S}_n$, written ${\rm sgn}(\sigma)$, is defined to be +1 if the permutation is even and -1 if it is odd, and is given by the formula $${\rm sgn}(\sigma) ...
20
votes
3answers
583 views

Math puzzle: 10 digit strings generations

There was a question in a math competition that I attended last year. At the end of competition, I realized that my answer was wrong for the question below and I have never been able to figure out how ...
18
votes
5answers
303 views

$\sum\limits_{\sigma \in S_n} (\mbox{number of fixed points of } \sigma)^2 $

I came across this result while doing some representation theory of the permutation group $S_n$ $$ \sum\limits_{\sigma \in S_n} (\mbox{number of fixed points of } \sigma)^2 = 2 n!$$ This can be ...
17
votes
4answers
6k views

Why are two permutations conjugate iff they have the same cycle structure?

I have heard that two permutations are conjugate if they have the same cyclic structure. Is there an intuitive way to understand why this is?
17
votes
1answer
277 views

Involutions, RSK and Young Tableaux

Let $S_n$ be the symmetric group on $n$ elements. The Robinson-Schensted-Knuth (RSK) correspondence sends a permutation $\pi\in S_n$ to a pair of Standard Young Tableaux $(P,Q)$ with equal shapes ...
15
votes
2answers
721 views

Shortest sequence containing all permutations

Given an integer $n$, define $s(n)$ to be the length of the shortest sequence $S = (a_1, \cdots a_{s(n)})$ such that every permutation of $\{1,\cdots,n\}$ is a subsequence of $S$. If $n=1$, then $S = ...
15
votes
2answers
246 views

Help deriving that $\mathrm{sign} : S_n\to \{\pm 1\}$ is multiplicative

$\def\sign{\operatorname{sign}}$ For homework, I am trying to show that $\sign:S_n \to \{\pm 1\}$ is multiplicative, i.e. that for any permutations $\sigma_1,\sigma_2$ we have $$\sign(\sigma_1 ...
15
votes
1answer
312 views

Is there a group which has precisely all finite groups as subgroups?

I would like to ask the following question: Does there exist a group $G$ such that every finite group can be embedded in $G$, and every proper subgroup of $G$ is finite? The closest ...
14
votes
1answer
3k views

6-letter permutations in MISSISSIPPI

How many 6-letter permutations can be formed using only the letters of the word, MISSISSIPPI? I understand the trivial case where there are no repeating letters in the word (for arranging smaller ...
13
votes
8answers
6k views

Calculating the number of possible paths through some squares

I'm prepping for the GRE. Would appreciate if someone could explain the right way to solve this problem. It seems simple to me but the site where I found this problem says I'm wrong but doesn't ...
13
votes
4answers
20k views

How many ways are there for 8 men and 5 women to stand in a line so that no two women stand next to each other?

I have a homework problem in my textbook that has stumped me so far. There is a similar one to it that has not been assigned and has an answer in the back of the textbook. It reads: How many ways ...
13
votes
3answers
319 views

How to see that the polynomial $4x^2 - 3x^7$ is a permutation of the elements of $\mathbb{Z}/{11}\mathbb{Z}$

This is from Rotman's Group Theory book, although I don't have the specific reference right now, as the book is with a friend. He asks to show that $\alpha (x) = 4x^2 - 3x^7$ is a permutation of the ...
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 ...
12
votes
2answers
501 views

What do all the $k$-cycles in $S_n$ generate?

Why don't $3$-cycles generate the symmetric group? was asked earlier today. The proof is essentially that $3$-cycles are even permutations, and products of even permutations are even. So: do the ...
12
votes
2answers
608 views

How many $n\times m$ binary matrices are there, up to row and column permutations?

I'm interested in the number of binary matrices of a given size that are distinct with regard to row and column permutations. If $\sim$ is the equivalence relation on $n\times m$ binary matrices such ...
11
votes
5answers
724 views

Probability that a random permutation has no fixed point among the first $k$ elements

Is it true that $\frac1{n!} \int_0^\infty x^{n-k} (x-1)^k e^{-x}\,dx \approx e^{-k/n}$ when $k$ and $n$ are large integers with $k \le n$? This quantity is the probability that a random permutation ...
11
votes
1answer
2k views

Can someone explain Cayley's Theorem step by step?

This is from Fraleigh's First Course in Abstract Algebra (page 82, Theorem 8.16) and I keep having hard time understanding its proof. I understand only until they mention the map $\lambda_x (g) = xg$. ...
11
votes
1answer
207 views

What's the name of this quantity?

For each permutation $\sigma$ of $ \left\{ 1, 2, \dots, n \right\}$ define $$\operatorname{dist}(\sigma)=\sum_{i=1}^{n}\left| \sigma (i)-i \right|$$ For each $n\in\mathbb{N}$, I'm interested in ...
10
votes
2answers
210 views

Probability of $\alpha\beta\gamma=\gamma\beta\alpha$ for random permutations of a finite set?

Following up on my previous question Probability that two random permutations of an $n$-set commute?, here's a related question for three elements. Q: If $\alpha,\beta,\gamma$ are chosen uniformly ...
10
votes
2answers
1k views

how to find the root of permutation

Observe that $$\bigl(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \end{smallmatrix}\bigr)* \bigl(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 \\ ...
10
votes
3answers
637 views

Proof that no permutation can be expressed both as the product of an even number of transpositions and as a product of an odd number of transpositions

I am aware that there are a couple of well-known proofs of this theorem, but I'm specifically grappling with the proof given in Fraleigh's A First Course in Abstract Algebra (Theorem 9.15 in the ...
9
votes
4answers
397 views

Unique Groups for Game Tournament

I am trying to put together a Munchkin game tournament where I am assuming I will have 16 people coming to my tournament. As part of that, I want to have as many games as possible where people are not ...
9
votes
2answers
3k views

Given 5 children and 8 adults, how many ways can they be seated so that there are no two children sitting next to each other. [duplicate]

Possible Duplicate: How many ways are there for 8 men and 5 women to stand in a line so that no two women stand next to each other? Given 5 children and 8 adults, how many different ways ...
9
votes
2answers
662 views

normal subgroups of infinite symmetric group

I recently took a course on group theory, which mentioned that the following proposition is equivalent to the continuum hypothesis: "The infinite symmetric group (i.e. the group of permutations on the ...
9
votes
2answers
129 views

Four generators of $S(9)$ - A smart way of showing that this generates the entire group?

I have four 4-cycles, given by: $(1452),(2563),(4785),(5896)$. I know that the group generated by these guys are $S(9)$ by asking mathematica for the order of the permutation group generated by these ...
9
votes
1answer
195 views

Largest symmetric group contained in alternating group

I know that for $n \geq 3$, the alternating group $A_n$ contains a subgroup which is isomorphic to $S_{n-2}$, namely $$\langle \{(i \;i+1)(n-1 \;n):1 \leq i \leq n-3\} \rangle.$$ I was wondering what ...
9
votes
4answers
5k views

How would I figure out how many anagrams of mississippi don't contain the word psi?

I'm really confused how I'd calculate this. I know it's the number of permutations of mississippi minus the number of permutations that contain psi, but considering there's repetitions of those ...
9
votes
2answers
76 views

Exotic maps $S_5\to S_6$

This section says: There is a subgroup (indeed, $6$ conjugate subgroups) of $S_6$ which are abstractly isomorphic to $S_5$, At this point I'm thinking: certainly: the group of all ...
9
votes
2answers
161 views

Cocktail bar problem

Recently I went out with friends and we asked ourselves the following question: Consider $n$ people sitting at a cocktail bar next to each other. How many rearrangements have to be made to ensure that ...
9
votes
1answer
386 views

Subgroups of $S_4$ isomorphic to $S_3$ and $S_2$?

It's a home work problem I got: Find $4$ different subgroups of $S_4$ isomorphic to $S_3$ and $9$ isomorphic to $S_2$. My approach is: since $S_3=\{1, (123),(132),(12),(23),(13)\}$, just take the ...
9
votes
2answers
285 views

How many permutations of a multiset have a run of length k?

Background $\newcommand\ms[1]{\mathsf #1}\def\msP{\ms P}\def\msS{\ms S}\def\mfS{\mathfrak S}$Suppose I have $n$ marbles of $c$ colors, where $c≤n$. Let $n_i$ denote the number of marbles of color ...
9
votes
3answers
172 views

Number of elements of order $2$ in $S_n$

How many elements of order $2$ are there in $S_n$? Using combinatorics I arrived at this: For $n$ even ($n=2k$) there are ${n\choose2}+{n\choose 2}{n-2\choose 2}\dfrac{1}{2!}+{n\choose 2} ...
9
votes
1answer
172 views

Product of permutations of consecutive numbers yields arithmetic sequence

Let $n\geq 3$ be an integer, and $a,b$ be positive integers. Let $c_1,\ldots,c_n$ be a permutation of $a,a+1,\ldots,a+(n-1)$, and $d_1,\ldots,d_n$ be a permutation of $b,b+1,\ldots,b+(n-1)$. Is it ...
9
votes
0answers
244 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
3answers
860 views

Number of permutations of $n$ where no number $i$ is in position $i$

I am trying to figure out how many permutations exist in a set where none of the numbers equal their own position in the set; for example, $3,1,5,2,4$ is an acceptable permutation where $3,1,2,4,5$ is ...
8
votes
3answers
2k views

The number of ways to order 26 alphabet letters, no two vowels occurring consecutively

What is the shortest solution to the following problem? What is the number of ways to order the 26 letters of alphabet so that no two of the vowels a,e,i,o,u occur consecutively? What I ...
8
votes
4answers
9k views

Odd/Even Permutations

How do you classify a permutation as odd or even (composition of an odd or even number of transpositions)? I somewhat understand the textbook definition of it but im having hard time conceptualizing ...
8
votes
3answers
2k views

Order of the centralizer of a permutation

Given a permutation $\sigma\in S_{n}$, is there a way to know the order of the centraliser $C_{S_{n}}\left(\sigma\right)=\left\{ \pi\in S_{n},\,\pi\sigma=\sigma\pi\right\}$ , i.e what is ...
8
votes
1answer
196 views

Subgroups between $S_n$ and $S_{n+1}$

Lets look at $S_n$ as subgroup of $S_{n+1}$. How many subgroups $H$, $S_{n} \subseteq H \subseteq S_{n+1}$ there are ?
8
votes
1answer
545 views

Literature on group theory of Rubik's Cube

While searching for literature on the group theory of Rubik's Cube, I mostly find introductions to group theory motivated by applications to Rubik's cube. I.e. the focus lies on elementary group ...
8
votes
1answer
176 views

Permutations: Given $P^4$, how many $P^1$s are possible?

Let $P^0$ be the identity tuple $(1,2,...,N)$ Let $P^{i+1}$ be the tuple after a permutation $P$ is applied to $P^i$. For example, if $P$ is $(2,1,3,6,4,5)$ than: $$\begin{align} P^0 &= ...
8
votes
2answers
948 views

Span of Permutation Matrices

The set $P$ of $n \times n$ permutation matrices spans a subspace of dimension $(n-1)^2+1$ within, say, the $n \times n$ complex matrices. Is there another description of this space? In particular, ...