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

learn more… | top users | synonyms (1)

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 ...
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 ...
6
votes
2answers
346 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 ...
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?
5
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 ...
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 ...
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 ...
24
votes
6answers
38k 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 ...
7
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 ...
23
votes
1answer
637 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
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 ...
1
vote
1answer
95 views

Number of binary numbers given constraints on consecutive elements

I've been trying to solve this question for quite a while, given to us by our discrete maths professor. I've been having a hard time in general with it, so I thought I tried looking it up online but ...
1
vote
1answer
376 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 ...
8
votes
5answers
876 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?
3
votes
3answers
322 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
votes
1answer
259 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 ...
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 ...
3
votes
1answer
840 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
195 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$ ...
0
votes
3answers
630 views

Counting arrays with gcd 1

I want to calculate the number of arrays of size $N$, such that for each of it's element $A_i, 1 \leq A_i \leq M$ holds, and gcd of elements of array is 1. Constraints: $1 \leq A_i \leq M$ and $A_i$ ...
16
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
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 :)
14
votes
4answers
34k 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 ...
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 ...
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 \\ ...
7
votes
4answers
4k views

every permutation is either even or odd,but not both

How we can show every permutation is either even or odd,but not both......I can't arrive at a proof for this ..... Can anybody give me the proof... Thanks in advance...
0
votes
2answers
298 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 ...
5
votes
1answer
960 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 ...
3
votes
2answers
1k views

To find the total no. of six digit numbers that can be formed having property that every succeeding digit is greater than preceding digit. [closed]

I have a question and got strucked on this.. To find the total no. of six digit numbers that can be formed having property that every succeeding digit is greater than preceding digit. Please guide me ...
3
votes
1answer
704 views

Normal subgroups of $S_n$ for $n\geq 5$.

Question is to : Find all normal subgroups of $S_n$ for $n\geq 5$. What I have done so far is : We know that $A_n$ is one normal subgroup of $S_n$. Suppose $H\neq (1)$ is another normal subgroup ...
0
votes
1answer
255 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 ...
9
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 ...
7
votes
2answers
2k views

Find the center of the symmetry group Sn.

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 ...
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
1answer
817 views

Baseball Combinations Problem

Two part question (My work below). For both questions will use the orioles current roster: -Current orioles roster: 12 pitchers, 2 catchers, 5 in-fielders, and 6 out-fielders: Similar to the list ...
2
votes
2answers
222 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$ ...
1
vote
1answer
68 views

Finite groups acting on strings.

Let $s = abcdandsoon.. \ \in \Sigma^*$. Let $|s| = n$ be the length of $s$. Consider all permutations of the positioned symbols that make up $s$, such that $s$ is fixed under the permutation. So if ...
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}$ ...
5
votes
2answers
223 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
447 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 ...
3
votes
1answer
131 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 ...
3
votes
1answer
172 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
379 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 ...
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 ...
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$)?
6
votes
3answers
123 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
4answers
10k views

How many different words can be formed using all the letters of the word GOOGOLPLEX?

How many different words can be formed using all the letters of the word GOOGOLPLEX? I tried answering this problem and came up with the formula $n!/a!b!c!$ where ...
8
votes
3answers
16k views

Distinct permutations of the word “toffee”

What does distinct permutations mean and how many distinct permutations can be formed from all the letters of word TOFFEE?
8
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 ...