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

learn more… | top users | synonyms (1)

35
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 ...
30
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
2answers
786 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 ...
27
votes
1answer
2k views

Six Frogs - Puzzle (order reversal using special transpositions)

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 ...
24
votes
6answers
35k 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 ...
23
votes
4answers
8k 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?
23
votes
1answer
625 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 ...
22
votes
5answers
7k 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) ...
22
votes
2answers
739 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 ...
21
votes
2answers
406 views

The smallest nontrivial conjugacy class in $S_n$

Find the smallest nontrivial conjugacy class in $S_n$. For small $n$, the answer can be found by counting the permutations of each possible cycle type. The result is: $$\begin{array}{ccc} n & ...
20
votes
3answers
713 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
323 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 ...
18
votes
1answer
375 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 ...
16
votes
2answers
823 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
8answers
13k 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 ...
15
votes
1answer
4k 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$. ...
15
votes
3answers
244 views

Count permutations of $\{1,2,…,7\}$ without 4 consecutive numbers - is there a smart, elegant way to do this?

Here's a problem I've solved: Count permutations of $\{1,2,...,7\}$ without 4 consecutive numbers (e.g. 1,2,3,4). So I did it kinda brute-force way - let $A_i$ be the set of permutations of $[7]$, ...
15
votes
2answers
261 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
372 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
2answers
586 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 ...
14
votes
2answers
2k 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 \\ ...
14
votes
1answer
5k 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 ...
14
votes
3answers
190 views

Rearrangements that never change the value of a sum

Which bijections $f:\{1,2,3,\ldots\}\to\{1,2,3,\ldots\}$ have the property that for every sequence $\{a_n\}_{n=1}^\infty$, $$ \lim_{n\to\infty} \sum_{k=1}^n a_k = \lim_{n\to\infty} \sum_{k=1}^n ...
14
votes
0answers
500 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 ...
13
votes
4answers
30k 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
2answers
1k views

$A_n$ is the only subgroup of $S_n$ of index $2$.

How to prove that the only subgroup of the symmetric group $S_n$ of order $n!/2$ is $A_n$? Why isn't there other possibility? Thanks :)
13
votes
3answers
338 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
4answers
17k 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 ...
12
votes
4answers
221 views

Prove that $(mn)!$ is divisible by $(n!)\cdot(m!)^n$

Prove that $$(n!)\cdot(m!)^n|(mn)!$$ I can prove it using Legendre's Formula, but I have to use the lemma that $$ ...
12
votes
3answers
810 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 ...
12
votes
2answers
739 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 ...
12
votes
1answer
53k views

How many possible combinations in 8 character password?

I need to calculate the possible combinations for 8 characters password. The password must contain at least one of the following: (lower case letters, upper case letters, digits, punctuations, special ...
11
votes
5answers
814 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
3answers
431 views

Group of $r$ people at least three people have the same birthday?

What is the probability that in a randomly chosen group of $r$ people at least three people have the same birthday? $\displaystyle 1- \frac{365\cdot364 \cdots(365-r+1)}{365^r}$ $\displaystyle ...
11
votes
4answers
4k views

A4 has no subgroup of order 6

Can a kind algebraist offer an improvement to this sketch of a proof? Show that $A_4$ has no subgroup of order 6. Note, $|A_4|= 4!/2 =12$. Suppose $A_4>H, |H|=6$. Then $|A_4/H| = ...
11
votes
1answer
20k views

How to write permutations as product of disjoint cycles and transpositions

$$\sigma=\begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 4&2&9&10&6&5&11&7&8&1&3 \end{pmatrix}$$ (1) I am ...
11
votes
2answers
291 views

Show that there is always a way to achieve det(A) > 0

a) Assume that $(a_1, ..., a_9)$ are different positive numbers. Let us make a $3 \times 3$ matrix $A_s$ by placing them arbitrarily into $9$ positions available. Show that there is always a way to ...
11
votes
1answer
220 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
4answers
419 views

confusion about permutation

$7$ white identical balls and $3$ black identical balls are randomly placed in a row. The probability that no two black balls are together is ? I am getting it as $ \frac{1}{3}$ while the answer in ...
10
votes
4answers
793 views

How to solve this confusing permutation problem related to arrangement of books?

Ms. Jones has 10 books that she is going to put on her bookshelf. Of these, 4 are mathematics books, 3 are chemistry books, 2 are history books, and 1 is a language book. Ms. Jones wants to ...
10
votes
2answers
234 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
4answers
170 views

Can we count odd and even derangements nicely without taking a determinant?

It's not hard to see that $$\det \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$$ is equal to #(even derangements on 3 elements) - #(odd derangements on 3 ...
10
votes
1answer
453 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 ...
10
votes
2answers
369 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 ...
10
votes
3answers
200 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
4answers
3k views

Exponential Generating Functions For Derangements

I have been introduced to the concept of exponential generating functions a few days ago. However, my understanding of them are still quite limited, and I would like to see some examples. Earlier this ...
9
votes
3answers
1k 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 ...
9
votes
4answers
481 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 ...