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
970 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
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 ...
6
votes
2answers
280 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 ...
4
votes
2answers
2k 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
1k 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 ...
23
votes
6answers
29k 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 ...
8
votes
5answers
761 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?
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 ...
3
votes
3answers
297 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 ...
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 ...
23
votes
1answer
580 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 ...
21
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?
7
votes
1answer
915 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 ...
0
votes
3answers
536 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$ ...
14
votes
1answer
3k 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$. ...
13
votes
4answers
22k 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
1answer
2k 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 ...
5
votes
1answer
952 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 ...
0
votes
2answers
248 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 ...
6
votes
4answers
3k 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...
2
votes
1answer
461 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
162 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
162 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
302 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
759 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 ...
1
vote
1answer
51 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
676 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
212 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
381 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
154 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 ...
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 \\ ...
6
votes
1answer
824 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$)?
4
votes
1answer
735 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 ...
4
votes
2answers
429 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 ...
3
votes
2answers
510 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
875 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 ...
0
votes
2answers
2k 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 ...
9
votes
1answer
826 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 ...
2
votes
2answers
74 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$ ...
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 ...
26
votes
2answers
730 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 ...
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) ...
15
votes
2answers
762 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 = ...
8
votes
2answers
996 views

Span of Permutation Matrices

The set $P$ of $n \times n$ permutation matrices spans a subspace of dimension $(n-1)^2+1$ within, say, the $n \times n$ complex matrices. Is there another description of this space? In particular, ...
5
votes
2answers
270 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 ...
9
votes
4answers
430 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 ...
8
votes
2answers
410 views

Probability of opening all piggy banks

Interesting problem I found, and can't solve it since the morning: We have $n$ keys and $n$ piggy banks. Each key fits only one piggy bank. We randomly put exactly one key in each piggy bank. Then ...
4
votes
3answers
2k views

Combination problem with constraints

You have four containers and one pitcher of water that holds 100L. Each container has different capacities with maximums of, say...70L, 45L, 33L and 11L levels respectively. What is the formula that ...
3
votes
0answers
203 views

Classification of triply transitive finite groups

A permutation group $G$ on a set $X$ is said to be $k$-transitive if it is both transitive on $X$ and either $k=1$ or the point stabilizer $G_x$ is $(k-1)$-transitive on $X\setminus\{x\}$. Is ...