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 ...
29
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 (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 ...
26
votes
2answers
723 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
575 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
27k 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
657 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
612 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
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?
18
votes
5answers
305 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
309 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
751 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
250 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
327 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
4k 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
193 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]$, ...
14
votes
0answers
444 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
8answers
7k 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
21k 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
514 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 ...
13
votes
3answers
324 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
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$. ...
12
votes
2answers
638 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
735 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
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 \\ ...
11
votes
1answer
211 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
218 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
3answers
666 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 ...
10
votes
4answers
125 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
2answers
245 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 3x3 matrix $A_s$ by placing them arbitrarily into 9 positions available. Show that there is always a way to assemble ...
10
votes
3answers
185 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
3answers
926 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
418 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
711 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
196 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
1answer
33k 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 ...
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
88 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
390 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
298 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
1answer
812 views

Conjugacy classes in $A_n$.

Suppose $n$ is a non negative integer $\geq 4$ and $\sigma\in S_n$ a permutation. Conjugacy classes in $S_n$ are completley determined by the cycle structure of $\sigma$. If we let the alternating ...
9
votes
1answer
266 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. ...
9
votes
1answer
184 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 ...
8
votes
3answers
3k 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
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 ...