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

learn more… | top users | synonyms (1)

2
votes
1answer
108 views

Determining the size of an automorphism group for a given design

I'm trying to wrap my head around the idea of automorphisms, and I'm having a lot of issues. One of the questions I've been given as an exercise is thus; Let $\mathbb{V} = \{1, 2, 3, 4, 5, 6\}$ ...
1
vote
3answers
47 views

$S_4 \ne \langle (1,2,3,4), \, (1,3)\rangle$

So I'm trying to prove $S_4≠⟨(1,2,3,4),(1,3)⟩$, and I get the basic idea that $(1,2)$ swaps two things next to each other, which neither of the other operations do, and necessarily neither do their ...
1
vote
1answer
65 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 ...
4
votes
1answer
174 views

How does the Enigma machine ensure that no letter is substituted for itself?

In Alan Turing: The Enigma Andrew Hodges describes how the letter encodings performed by a German Enigma machine "would always be swappings" (original emphasis). And goes on to say that There was ...
1
vote
2answers
47 views

What are the transitive groups of degree $4$?

How can I find all of the transitive groups of degree $4$ (i.e. the subgroups $H$ of $S_4$, such that for every $1 \leq i, j \leq 4$ there is $\sigma \in H$, such that $\sigma(i) = j$)? I know that ...
0
votes
0answers
17 views

can someone explain what is a permutation pattern class?

I understand that involvement is having a subset of a set \alpha order-isomorphic to set \beta. A pattern class is a set of permutations closed under taking subpermutations. what does that ...
1
vote
2answers
250 views

Ways to arrange 4 different colour balls with no two of the same colour next to each other

I have n green balls, n blue balls, m red balls, m yellow balls. How many ways are there to arrange this such that we don't have an sequence with 2 of the same colour next to each other? I don't ...
7
votes
1answer
85 views

Solution to $x(128)x=(12365)(479)$ in $A_9$, the alternating group

This isn't homework. I'm wondering if anyone knows techniques besides trial and error to find $x$ or show there is no solution, to problems like this, or worse, say $xpx^2rx^{-4}=s$, where $p$, $q$, ...
3
votes
2answers
74 views

Number of ways to re-arrange INTERNATIONAL with L to the right of E.

How many ways can you re-arrange I N T E R N A T I O N A L such that L is always to the right of E, it does not need to be a specific number of places, so both E L I N T R N A T I O N A ...
1
vote
2answers
51 views

Why is the permutation $(a,c,d,e)(a,b)=(a,d)(b,c,e)$

I'm working through a proof in my notes. We already know that the transposition $(a,b)\in G$ and $(a,b,c,d,e)\in G$, where $G$ is a group of permutations of the elements $a,b,c,d,e$, so it's a ...
1
vote
2answers
84 views

Family of four and eight people ordered around a table

So the question is how many ways can a family of four which includes the mother, father and two children, be ordered around a table with eight other people if the mother must sit beside the father and ...
0
votes
1answer
51 views

Automorphisms of B_n

Consider the Coxeter group of type $B_n$. This group, of order $2^n n!$, can be identified with the group of odd permutations of the set $\{\pm 1,\dots,\pm n\}$ and is thus isomorphic to the ...
1
vote
2answers
40 views

Permutations with repeating digits

My question is this : how many distinct two digit numbers can be produced from numbers $4, 3, 3, 1$? When applying the formula $$\frac{4!}{(4-2)!2!}$$ you come up with $6$, yet when doing the problem ...
2
votes
2answers
68 views

Outer automorphism of $S_6$ and conjugate stabilizers

Let $f:S_6 \mapsto S_6$ be an outer automorphism of $S_6$ and consider the subgroups $$G = \{\pi \in S_6 \mid \pi(1) = 1\}$$ and $$H = \{\pi \in S_6 \mid f(\pi)(1) = 1\}.$$ I would like to show that ...
3
votes
2answers
352 views

Elements of order 10 in S6

I conjecture that there are no elements of order 10 in $S_{6}$. My reasoning is that in order for there to exist an element of order 10, then it must be a cycle of order 10 or it's a composition of ...
1
vote
2answers
55 views

Number of order permutations

Can someone explain how a set {1,2,3,.....,n} has n!/6 many permutations where 1 is to the left of 2 and 3, and 2 is to the left of 3. This works for all the n I tested but I can't make sense of why. ...
3
votes
2answers
167 views

permutations confusion!

Hello this is my first post , I am reading a book called (probability for dummies) the answer in the book for the question below has confused me ... Suppose you have four friends named Jim , Arun , ...
2
votes
3answers
132 views

permutation & combinations

How many odd three digit numbers are there when tens digit is greater than units digit and hundreds digit is greater than tens digit? $225$ $ 45$ $ 50$ $230$ My attempt: The units digit can be ...
7
votes
1answer
55 views

Applications of the following theorem in the real world

We know that every permutation can be expressed as a product of transpositions ( cycles with length 2). As a class project I'm looking for the applications of this fact in the real world; especially ...
2
votes
3answers
53 views

Stochastic variable exercise: People between me and my friend.

This is the exercise: $n$ people are arraged randomly in a line (not a circle), among which are yourself and a friend. Call $Y$ the number of people that are between you and your friend. Show: $E[Y] ...
0
votes
1answer
34 views

Abstract Algebra Symmetric Groups

$$ \begin{align} \beta &= \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 3 & 8 & 7 & 6 & 5 & 2 & 4 \end{bmatrix} \\ &= ...
0
votes
0answers
42 views

Permutations with fixed points

I am trying to write a java program that counts permutations of a string, I would like to check my results by hand, but I can remember (or find) the formula to count the number of permutations, and ...
2
votes
0answers
119 views

List all possible subgroups of $A_4.$ Determine which subgroups of $A_4$ are normal.

I have a question which is List all possible subgroups of $A_4$. Determine which subgroups of $A_4$ are normal. Since $|A_4| = 12,$ the order of any proper subgroup of $A_4$ must be an element of ...
4
votes
1answer
73 views

Determine the number of ways for n couples to stand in a line so that no one stands beside his or partner (explanation for the answer)

I'm not quite sure if I'm understanding solution to following problem: "Determine the number of ways for n couples to stand in a line so that no one stands beside his or her partner." The general ...
1
vote
0answers
138 views

Find eight elements in S6 that commute with (12)(34)(56). Do they form a subgroup of S6?

I know the question has been asked and answered many times, but I am trying to shore up my understanding of this concept. Given the questions here and here, does this mean that I could rearrange the ...
1
vote
2answers
39 views

Interpretation of a Problem involving permutations

[USAMO 1999 submission, Titu Andreescu] Let $n$ be an odd integer greater than $1$. Find the number of permutations $p$ of the set $\{ 1, 2, …, n\}$ for which $$\def\x#1{\lvert p(#1)-#1\rvert} ...
4
votes
2answers
574 views

How many teams can be made from 11 people?

The question asks this: Five places exist on a team. $11$ total people. $6$ come from district A, $4$ from district B and $1$ from district C. How many different groups of five are there? How many ...
1
vote
2answers
36 views

Group theoretic construction for permutation algorithm

Consider a permutation $\sigma = [s_1, \ldots, s_n]$. The `contracting endpoints' construction for the subsequence $[s_i,\ldots, s_k]$ is given by iteratively taking the product of cycles given by the ...
1
vote
0answers
33 views

Equivalence relation among matrices

Consider the set of $p\times q$ matrices with entries from the set $S=\{1,\dots,s\}$. Say that two such matrices are equivalent if one can be transformed into the other by a series of operations of ...
0
votes
0answers
23 views

Finding Number Of Permutation Reverses

What is the easiest way to count the number of opposite order in permutation. meaning the total of elements in the permutation where $i<j$ and $\sigma_i>\sigma_j$ For example, $3142$, we have ...
0
votes
0answers
32 views

Permutation puzzler

Given a permutation on n letters, how many clues do you need to solve it? For example if the permutation is 31524, the clues come in the form of 5<4, meaning that 5 comes before 4. So, given a ...
0
votes
0answers
9 views

Reordering indexed expressions (combinatorics)

To me, it appears always as a little 'magic' when people reorder expressions, indexed by highly complex combinations of permutations and I would like to know in deep and formally what really is going ...
1
vote
0answers
48 views

Normalizer of a transitive subgroup in the symmetric group

Let $G$ be a finie group, and $H$ be a core-free subgroup of $G$ (that is to say, there is no nontrivial normal subgroup of $G$ contained in $H$). Denote by $\Omega$ the set of right cosets of $H$ in ...
2
votes
3answers
165 views

Expected value of number of sorted elements in a permutation

Consider the obvious algorithm for checking whether a list of integers is sorted: start at the beginning of the list, and scan along until we first find a successive pair of elements that is out of ...
2
votes
2answers
119 views

Permutations: A cycle is conjugate to its own inverse

I need help with d) here. Let $2 \le r \le n$ be two natural numbers. Assume that $\rho \in S_n$ is a permutation of the set $I_n=\{1,2,...,n\}$. Let $x_i \in I_n$ for $1 \le r$ be r different ...
0
votes
2answers
116 views

Are these two events independent?

Let n ≥ 3 be an integer, consider a uniformly random permutation of the set {1, 2, . . . , n}, and define the events ...
1
vote
1answer
27 views

How do you apply an element on the left of a permutation?

I am looking at the set $G=\{1,2,3\}$. I take the subgroup: $$H=\{(), (1,2)\} < S_G$$ I want to find $G/H$. I take the definition of $G/H$: $$\{1H, 2H, 3H\}$$ $$\{1\{(), (1,2)\}, 2\{(), ...
1
vote
1answer
117 views

How to calculate a pair of cards contains at least one ace?

A pair of cards are simultaneously drawn from a deck of 52 cards three times in a row. The drawn cards are returned to the deck. What is the probability that two of three pairs contain an ace? For ...
1
vote
1answer
124 views

How many ways there are to arrange 40 people to play exactly one match each? [duplicate]

A tennis club has 40 members. They host a tournament playing single (one verses one) matches. Every member of the club plays one match with another member of he club, so twenty matches are ...
3
votes
4answers
614 views

Are there any Symmetric Groups that are cyclic?

Are there any Symmetric Groups that are cyclic? Because I have been doing some problems and I tend to notice that the problems I do that involve the symmetric group are not cyclic meaning they do not ...
1
vote
1answer
107 views

Nearest latin square

given a n x n matrix A with integer entries is there any way to find the nearest n x n latin square to it, say, e.g., in the Frobenius norm? I am looking for some type of convex optimization... ...
6
votes
2answers
378 views

Permutations to satisfy a challenging restriction

In a stack of n distinct cards in order {1,2,3,4,...,n} from top, define distance between 2 cards as the number of cards between them. 2 cards are neighbours if they're adjacent in original ...
4
votes
1answer
40 views

Find a subgroup of $S_{4}$ which is isomorphic to $\mathrm{Aut}(U_{8})$

The notation I am using is: $S_{4}$: the permutation group of order 4 $\mathrm{Aut}(U_{8})$: the set of all automorphisms on the set $U_{8}$ $U_{8}$: the group of numbers relatively prime to 8 I ...
10
votes
2answers
369 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 ...
1
vote
2answers
35 views

Arranging pictures possible combinations

I'm working on a problem which states there are 26 portraits of men and 4 of women. It wants to know how many ways can the photos be organized so no women are next to each other. I assume that the ...
1
vote
1answer
75 views

Dividing gems by random permutation

A group of people have found a treasure of gems: $G=90$ green and $B=990000$ blue. They decided to divide it among them. Since there are more people then gems, they decide to order themselves in a ...
1
vote
1answer
20 views

Group Theory - Permutations

If $B \in S_7$ and $|B^3| = 7$, prove that $|B|=7$. Solution: As $o(B^k) = o(B) / (o(B),k) $ Thus $|B| / (|B|,3) = 7$ Let $|B| = 7a$. Then $7a/(7a,3)$ should be $7a/a = 7$ or $(7a,3) = a$. As $3$ is ...
1
vote
1answer
66 views

Proof of 2^n deck of card, it will be reverse order performing n perfect in-shuffle.

I am now trying to prove performing n perfect in-shuffle with 2^n deck of card, and then it will be resulting reverse order. For example, Initial : [1, 2, 3, 4] 1st round : [3, 1, 4, 2] 2nd round : ...
0
votes
1answer
190 views

how many strings you can write with the letters abcd (permutation & combination or what?)

You have 4 letters abcd. How many 4-letter strings can you write with them? Assumptions: - the order is not important (aaab, abaa, baaa are same, counts 1) - you can use same letter more than once ...
2
votes
2answers
49 views

Permutations on a set with certain conditions.

Suppose we have a set $S=\{1,2,3,x,y\}$. There are $5!$ ways to rearrange the elements in the set, but I am confused about how to find the number of ways to rearrange the set given that $3$ comes ...