Questions tagged [permutations]

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

Filter by
Sorted by
Tagged with
26
votes
1answer
9k 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 ...
20
votes
3answers
6k 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 ...
45
votes
4answers
23k 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?
42
votes
3answers
58k views

Multiplication in Permutation Groups Written in Cyclic Notation

I didn't find any good explanation how to perform multiplication on permutation group written in cyclic notation. For example, if $$ a=(1\,3\,5\,2),\quad b=(2\,5\,6),\quad c=(1\,6\,3\,4), $$ then ...
31
votes
5answers
17k views

$A_4$ 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| = [A_4:H]=2$. ...
18
votes
2answers
9k views

Find the center of the symmetry group $S_n$.

Find the center of the symmetry group $S_n$. Attempt: By definition, the center is $Z(S_n) = \{ a \in S_n : ag = ga \forall\ g \in S_n\}$. Then we know the identity $e$ is in $S_n$ since there is ...
9
votes
2answers
6k views

Counting number of moves on a grid

Imagine a two-dimensional grid consisting of 20 points along the x-axis and 10 points along the y-axis. Suppose the origin (0,0) is in the bottom-left corner and the point (20,10) is the top-right ...
24
votes
1answer
58k 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 ...
9
votes
3answers
921 views

An epimorphism from $S_{4}$ to $S_{3}$ having the kernel isomorphic to Klein four-group

Exercise $7$, page 51 from Hungerford's book Algebra. Show that $N=\{(1),(12)(34), (13)(24),(14)(23)\}$ is a normal subgroup of $S_{4}$ contained in $A_{4}$ such that $S_{4}/N\cong S_{3}$ and $...
15
votes
3answers
3k views

Show group of order $4n + 2$ has a subgroup of index 2.

Let $n$ be a positive integer. Show that any group of order $4n + 2$ has a subgroup of index 2. (Hint: Use left regular representation and Cauchy's Theorem to get an odd permutation.) I can easily ...
32
votes
1answer
952 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 ...
10
votes
2answers
4k views

How many elements of order $k$ are in $S_n$?

I need to find how many elements of order $k$ are in $S_n$ (where $k \leq n$). So if $k$ is prime, it's easy: $k$ can't be the $\mathrm{lcm}$ of any integers besides itself and one's (which we're ...
29
votes
4answers
7k 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 :)
21
votes
2answers
5k 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 \\ ...
6
votes
3answers
2k views

Social Golfer Problem - Quintets

I wrote an article on the Social Golfer Problem, which has questions like: Each day, 16 people play Munchkin in foursomes simultaneously. How many days can they play with no two people playing with ...
15
votes
4answers
886 views

Showing that $Q_n=D_n+D_{n-1}$

Let $T_n$ be the set of permutations of $\{1,2,\ldots,n\}$ which do not have $i$ immediately followed by $i+1$ for $1\le i\le n-1$; in other words, let \begin{align} T_n=\{\sigma \in S_n: \sigma(i)+1\...
1
vote
2answers
798 views

Counting all possibilities that contain a substring

How many strings are there of seven lowercase letters that have the substring tr in them? So I am having a little problem with this question, I know that the total number of combinations is $26^6$ ...
5
votes
2answers
3k views

Derivation of the Partial Derangement (Rencontres numbers) formula

I'm looking for the method by which the partial derangement formula $D_{n,k}$ was derived. I can determine the values for small values of N empirically, but how the general case formula arose still ...
6
votes
3answers
275 views

Polynomials and partitions

There is a question I have based on the fact: If you take a quadratic polynomial with integer coefficients, take the set $\{1,2,3,4,5,6,7,8\}$, make a partition $A=\{1,4,6,7\}$, $B=\{2,3,5,8\}$, and ...
42
votes
3answers
7k 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 ...
20
votes
1answer
7k 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 C_{...
14
votes
1answer
4k views

Why is $S_5$ generated by any combination of a transposition and a 5-cycle?

Why is $S_5$ generated by any combination of a transposition and a 5-cycle? Is this true for any prime $p$ (in this case $p=5$)?
38
votes
6answers
63k 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 four ...
14
votes
4answers
7k views

Exponential Generating Function 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 ...
8
votes
3answers
306k views

how many ways can the letters in ARRANGEMENT can be arranged [closed]

Using all the letters of the word ARRANGEMENT how many different words using all letters at a time can be made such that both A, both E, both R both N occur together .
6
votes
2answers
5k views

Number of zeroes at end of factorial

Question: How many zeroes will there be at the end of $(127)!$ Approach: Considering the fact that when two numbers ending in $x$ and $y$ zeroes are multiplied, the resulting number contains $x+y$ ...
5
votes
3answers
908 views

How does $(12\cdots n)$ and $(ab)$ generate $S_n$?

I know that $S_n$ is generated by a number of things, like all transpositions, all transpositions of form $(1a)$, the transpositions $(12),(23),(34),\cdots(n-1n)$, and just the two elements $(123\...
3
votes
2answers
2k views

On Conjugacy Classes of Alternating Group $A_n$

In Dummit & Foote, page 131 Let $K$ be a conjugacy class and suppose that $K$ is subset of $A_n$ . Show that if $\sigma$ belongs to $S_n$ then , $\sigma$ does not commute with any odd ...
4
votes
2answers
1k views

Number of possible permutations of n1 1's, n2 2's, n3 3's, n4 4's such that no two adjacent elements are same?

Given $n_1 $ number of $1 $'s, $n_2 $ number of $2 $'s, $n_3 $ number of $3 $'s, $n_4 $ number of $4 $'s. form a sequence using all these numbers such that two adjacent numbers should not be ...
4
votes
1answer
551 views

Rearrangement of groups such that no two members meet again

Suppose that we are given $n$ groups of $m$ people. We want to rearrange these $nm$ people into the same format of $n$ groups of $m$ with that the catch that any two people who were originally in a ...
37
votes
2answers
17k 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$. ...
25
votes
4answers
72k 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 ...
8
votes
5answers
1k 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?
7
votes
3answers
4k views

“In a party people shake hands with one another”

In a party people shake hands with one another (not necessarily everyone with everyone else). (a) Show that 2 people shake hands the same no. of times. (b) Show that the number of people who shake ...
3
votes
1answer
269 views

Does a homomorphic image of even permutations consist of even permutations?

If $f:S_n \to S_n$ is a homomorphism, prove $f(A_n) \subseteq A_n$. If every image of a transposition is even, then there is nothing to prove, but it is not sure.. How can I prove the problem?
8
votes
1answer
3k 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 ...
3
votes
1answer
6k views

Fixed points in random permutation [closed]

Suppose two random permutations of the numbers 1 to n placed side by side. a) Calculate the expectation number of fixed points for $n = 5$. b) Find the value of expectation in the amount of fixed ...
3
votes
3answers
478 views

Existence of subgroup of order six in $A_4$

Show that the alternating group $A_4$ of all even permutations of $S_4$ does not contain a subgroup of order $6$. For me am thinking to write all elements of $A_4$ and trying to find every ...
10
votes
2answers
4k views

Proving that any permutation in $S_n$ can be written as a product of disjoint cycles

I have attempted a proof of this, but upon looking at my notes, I feel it might be incorrect: it is noticeably simpler than the one in my notes. Proposition: any permutation in $S_n$ can be written ...
8
votes
2answers
8k views

Arrangements of a,a,a,b,b,b,c,c,c in which no three consecutive letters are the same

Q: How many arrangements of a,a,a,b,b,b,c,c,c are there such that $\hspace{5mm}$ (i). no three consecutive letters are the same? $\hspace{5mm}$ (ii). no two consecutive letters are the same? A:(i). ...
3
votes
3answers
2k views

The center of $A_n$ is trivial for $n \geq 4$

I need to prove that the center of $A_n$ is trivial for $n \geq 4$. $Z(A_3) = A_3$, since $A_3 = \mathbb{Z}/3\mathbb{Z}$ is commutative. One idea is two use "counting" technique. First of, all we ...
7
votes
3answers
198 views

How many permutations of $\{1, \ldots, n\}$ exist such that none of them contain $(i, i+1)$ (as a sequence) for $i \in {1,…,(n-1)}$?

How many permutations of $\{1, \ldots, n\}$ exist such that none of them contain $(i, i+1)$ (as a sequence) for $i \in {1,...,(n-1)}$? First thing that comes to my mind is to find all that have $(i, ...
4
votes
1answer
642 views

Counting necklace with no adjacent beads are of the same color

I've read that one can use the Polya enumeration theorem or the Burnside's lemma to count the number of necklaces using $n$ beads from $k$ colors. Can we then find a way to count the number of ...
1
vote
2answers
16k views

Find the subgroups of A4

I had a question I was hoping for some help on: Find all of the subgroups of $A_4$ Here is what I know: $A_4$ is the alternating group on 4 letters. That is it is the set of all even permutations....
4
votes
4answers
3k views

Show that not all 5 cycles in $A_5$ are conjugate in $A_5$

This is a practice question (not assignment). One thing I am wondering is what this question exactly means. From my understanding, the conjugate of $a \in A_5$ is $gag^{-1} \in A_5$ where $g \in A_5$. ...
25
votes
13answers
56k 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
2answers
2k views

Solving Rubik's cube and other permutation puzzles

I've seen two questions on solving the Rubik's cube but none of the answers have given a complete solution using mainly mathematical techniques. Furthermore, I've not seen a good explanation of ...
9
votes
1answer
5k views

Proving that $A_n$ is the only proper nontrivial normal subgroup of $S_n$, $n\geq 5$

There is a famous Theorem telling that: For $n≥5$, $A_n$ is the only proper nontrivial normal subgroup of $S_n$. For the proof, we firstly start with assuming a subgroup of $S_n$ which $1≠N⊲S_n$. ...
16
votes
3answers
386 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 a_{f(k)...
4
votes
2answers
43k views

In how many ways can 20 identical balls be distributed into 4 distinct boxes subject?

I was practicing math exercises on text book and i got stuck in this question ? ...