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

learn more… | top users | synonyms

33
votes
3answers
2k 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
1k 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
3k 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 ...
26
votes
1answer
1k 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 ...
23
votes
2answers
618 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
486 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 ...
21
votes
3answers
562 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
6answers
18k 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 ...
17
votes
4answers
3k 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) ...
16
votes
1answer
191 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
239 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 ...
14
votes
4answers
4k 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?
14
votes
2answers
660 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 = ...
13
votes
3answers
306 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 ...
12
votes
8answers
4k 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 ...
12
votes
4answers
13k 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 ...
12
votes
2answers
511 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
672 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
2answers
451 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 ...
11
votes
1answer
2k 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 ...
11
votes
1answer
198 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 ...
11
votes
0answers
364 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 ...
10
votes
2answers
178 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
4answers
212 views

Group Action - Permutation on the Polynomial

I'm trying to check the permutation on the polynomial is a Group Action, but I'm not getting the second axiom. I'm following my lecturer's work --- Examples 2.1 and 2.6 on page 5 on ...
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
3answers
531 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
2answers
528 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
152 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
3answers
134 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} ...
8
votes
3answers
689 views

Number of permutations where n ≠ position n

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 not ...
8
votes
4answers
353 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 ...
8
votes
1answer
802 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$. ...
8
votes
2answers
124 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 ...
8
votes
1answer
184 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
440 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
172 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
793 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, ...
8
votes
2answers
371 views

Probability of opening all piggy banks

Interesting problem I found, and can't solve it since the morning: We have $n$ keys and $n$ piggy banks. Each key fits only one piggy bank. We randomly put exactly one key in each piggy bank. Then ...
8
votes
2answers
716 views

All possible permutations on a Rubik cube ($3\times3\times 3$) can be reached from the initial state?

If I were to represent a state in the Rubik cube as a permutation of the colors on the 9 tiles per side on all sides of the cube, could I reach all possible states (i.e. colorings) by the permutations ...
8
votes
1answer
1k views

Centralizer of a given element in $S_n$?

It is known that any two disjoint cycles in $S_n$ commutes. Therefore, any $\pi\in S_n$ which is disjoint with $\sigma$ is in the centralizer of $\sigma$: $C_{S_n}(\sigma)$. Also $$ \sigma^i\pi\in ...
8
votes
3answers
3k 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 ...
8
votes
1answer
362 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 ...
7
votes
2answers
571 views

Number of permutations which fixes a certain number of point

Given the set $N:=\{1,\cdots,n\}$, let $\pi$ be a permutation on $N$. We say $i \in \{1,\cdots,n\}$ is fixed by $g$ iff $\pi(i)=i.$ Denote the set of all permuations on $N$ by $S_n$. Define $f :~N ...
7
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 ...
7
votes
3answers
153 views

Problem involving permutation matrices from Michael Artin's book.

Let $p$ be the permutation $(3 4 2 1)$ of the four indices. The permutation matrix associated with it is $$ P = \begin{bmatrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 ...
7
votes
2answers
121 views

On doubly graceful permutations

A permutation $\sigma\in\mathfrak S_n$ is graceful if $$\{|\sigma(i+1)-\sigma(i)| \text{ with } 1\leq i\leq n\}=\{1,2,\ldots,n-1\}$$ (terminology coming from a more general definition in graph ...
7
votes
2answers
131 views

Integer solution $x,y$ and $z$ to $x \cdot y \cdot z=24$

The total no. of Integer solution of the equation $xyz=24$ I have tried $xyz = 2^3 \cdot 3$ This is my process: Let $x = 2^{x_{1}} \cdot 3^{y_{1}}$ and $y = 2^{x_{2}} \cdot 3^{y_{2}}$ and $z = ...
7
votes
1answer
656 views

number of combination in which no two red balls are adjacent.

given x spaces(you can fit 1 ball in 1 space) and unlimited number of identical red and white balls, find the total number of combinations in which no two red balls are adjacent to each other. i ...
7
votes
5answers
684 views

How many arrangements of $\{a,2b,3c,4d, 5e\}$ have no identical consecutive letters?

How many arrangements of $\{a,2b,3c,4d, 5e\}$ have no identical consecutive letters? I find it very tough... Could anyone have some good ways?