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

learn more… | top users | synonyms (1)

15
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 ...
10
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 ...
6
votes
3answers
371 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 $...
6
votes
2answers
3k 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 ...
23
votes
4answers
9k 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?
26
votes
1answer
666 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 ...
13
votes
1answer
3k 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_{...
8
votes
3answers
1k 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 ...
15
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 :)
8
votes
5answers
890 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?
25
votes
6answers
39k 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 ...
11
votes
4answers
4k 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 ...
5
votes
2answers
2k 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 ...
3
votes
3answers
327 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 ...
1
vote
2answers
201 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$ ...
37
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 ...
7
votes
1answer
1k 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 ...
1
vote
1answer
397 views

Permutation of n objects with restriction of adjacent pairs

Given $n$ objects with values $\{x_1,x_2,x_3,\dots,x_n\},$ and $m$ pairs $a_k = \{x_i,x_j\}$. Let $\{p_1,p_2,p_3,\dots,p_n\}$ be a permutation of objects. The question is to find number of ...
19
votes
1answer
5k 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$. ...
14
votes
4answers
35k 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 ...
9
votes
1answer
1k 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$)?
15
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 \\ ...
8
votes
2answers
2k 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 ...
5
votes
1answer
996 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 ...
0
votes
1answer
260 views

Finding the “square root” of a permutation

Suppose $r$ is odd, and ${\rm ord}(\alpha)=r$. ($\alpha,\beta$ are cycles.) Now, $\alpha=(a_1\cdots a_n)$. I need to find $\beta$ that will make $$\alpha = \beta^2$$ How can I show it? What I ...
4
votes
2answers
181 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 ...
2
votes
2answers
273 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
2answers
224 views

Number of bitstrings with $000$ as substring

I have $F_n$ number of bitstrings that have $000$, How would I prove that for $n \ge 4$ , $a_n = a_{n-1} +a_{n-2}+a_{n-3}+ 2^{n-3}$? Now there are many ways to go about this but if I choose starting ...
5
votes
3answers
463 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
1answer
134 views

Recurrence for the number of $\sigma \in S_n$ with cycle length at most $r$

I have just learned that the formula is right, but the definition of $c_n^{(r)}$ was wrong. The correct problem is: Prove $$c_{n+1}^{(r)} = \sum_{k=n-r+1}^n n^{\underline{n-k}} c_k^{(r)}$$ where $c_n^{...
3
votes
1answer
181 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 ...
2
votes
4answers
384 views

Factorial of 0 - a convenience?

If I am correct in stating that a factorial of a number ( of entities ) is the number of ways in which those entities can be arranged, then my question is as simple as asking - how do you conceive the ...
1
vote
0answers
99 views

Finding total number of multi-sets

I am provided with a multi-set, let's say S with elements as [num1, num2, num3] and these elements are integers (both negative as well as non negative). As this is a multi-set, elements in the multi-...
-1
votes
1answer
270 views

Number of pairs of strings satisfying the given condition

We are provided with a string A (may contain repeated characters as well ). One needs to make all possible permutations of A , and find out how many pairs of strings chosen from these permutations are ...
31
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 ...
12
votes
1answer
24k 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 ...
7
votes
3answers
151 views

How do Gap generate the elements in permutation groups?

I understand that permutationgroups in Gap are represented by generators, which seems to be far more efficient than groups represented by all it's elements, but how could then for example ...
5
votes
1answer
2k 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$....
0
votes
2answers
316 views

When a 0-1-matrix with exactly two 1’s on each column and on each row is non-degenerated? [1]

Let $A$ be an $n\times n$ matrix with entries in the set $\{0,1\}$ which has exactly two ones in each column and two ones in each row. Give necessary and sufficient conditions for the rank of $A$ to ...
10
votes
3answers
3k 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 $\left|C_{S_{...
6
votes
1answer
388 views

Arrangement of integers in a row such that the sum of every two adjacent numbers is a perfect square.

Inspired by this interesting question and in order to solve an old problem, I have the following question: Can we construct a strictly increasing sequence $(N_i)_{i\in \mathbb{N}}$, such that for ...
10
votes
1answer
1k 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 ...
4
votes
2answers
626 views

Derangement of n elements

What are the total number of ways to arrange $N$ objects such that first $K$ are deranged? I know the general formula of Derangement of $N$ objects. Is there any way the above problem be reduced to ...
4
votes
2answers
859 views

What is the parity of permutation in the 15 puzzle?

You might know the 15 puzzle: $\hskip1.4in$ Concerning the solvability, Wiki says: The invariant is the parity of the permutation of all 16 squares plus the parity of the taxicab distance (...
3
votes
2answers
1k views

What will be total number of solutions of $a+b+c = n$?

Please tell me how to find the total number of intergral solutions of $$ a+b+c=n $$ I already know that total number of solutions will be $(n+3-1)c(3-1)$. But what will be the case when a varies from ...
3
votes
1answer
921 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 ...
1
vote
2answers
1k 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 ...
0
votes
2answers
3k views

some questions about combinations

1) In how many ways can 10 pencils (identical) be distributed among 5 children if a) there are no restrictions? b) each child gets at least 1 pencil? c) the oldest child gets at least 2 ...
7
votes
2answers
1k views

Bubble sorting question

Consider that we use the bubble-sorting algorithm to sort a string of size $n$. We know then that the maximum number of swaps results when the string is in reverse order- this gives $\frac{n(n-1)}{2}$ ...
3
votes
2answers
231 views

Find the number of permutations in $S_n$ containing fixed elements in one cycle

Find the number of permutations in $S_n$ such as 1 and 2 belong to one cycle.