Questions tagged [permutation-cycles]

For elementary questions concerning permutation cycles and permutation groups. This includes all representations of permutations (two-line arrays, cycles, bipartite graphs); transpositions and the sign/parity of a permutation; the Symmetric group and the Alternating group. To be used with the (permutations) tag to make the distinction between abstract algebra permutation questions and combinatoric permutation questions.

Filter by
Sorted by
Tagged with
-2 votes
0 answers
18 views

Decreasing probability of finding a number in a randomized array from 1/n to 2/n using permutation graph

This is a question that my professor asked to the class. There are 52 cards with numbers ranging from 1 to 52 on them. There will be 2 players, and their aim is to find a card on the card list in at ...
wwyyaa's user avatar
  • 1
-1 votes
0 answers
25 views

Let $I$ be the collection of all involutions (for all $n \geq 0$). Find the EGF for $I$. [closed]

A permutation $\pi$ of $[n]$ is said to be an involution if its cycle decomposition consists of only $1$- or $2$-cycles. Let $I$ be the collection of all involutions (for all $n \geq 0$). Find the EGF ...
Beehunter7's user avatar
2 votes
0 answers
47 views

Finding a simple graph such that its automorphism group equals the subgroup of $S_3$ generated by a 3-cycle

I have found that the subgroup of $S_3$ generated by a 3-cycle is $\{e,(123),(132)\}$ where $e$ is the identity but I can't find any graphs that have this group as their automorphism group. I am a ...
mantaray's user avatar
1 vote
0 answers
20 views

Multiplicative orders modulo divisors of the modulus

Is there a known description of the set of multiplicative orders of a fixed unit $a$ modulo all divisors of some modulus $n$, i.e. of $\text{ord}_d(a)$ with $d\mid n$? It is easy to see that it is a ...
Conifold's user avatar
  • 11.7k
1 vote
0 answers
40 views

Brainfreeze! reduce a number by a percentage so that the number after X iterations is below 1 [closed]

I am having a sort of brainfreeze or cannot express the mathematical formula for the following: I have a Natural Number X and I want to reduce it by a Percentage e.g 4% Y times that after Y iterations ...
kg_root's user avatar
  • 11
1 vote
0 answers
17 views

Algorithm to create a polynomial invariant only under specific permutations of the variables

I was solving the following problem (1.2.10 from Dixon and Mortimer's Permutation Groups): Given the group $G =\langle(x_1,x_2, x_3, x_4),(x_1,x_3) \rangle$, give an example of a polynomial that's ...
Robert Lee's user avatar
  • 7,133
2 votes
2 answers
105 views

Find a $6$-cycle $C$ such that $C^3=(2 \; 9) (5 \; 13) (11 \; 12)$

My initial problem was: Given $\sigma$ = $(1 \; 7 \; 3 \; 15) (2 \; 9) (4 \; 10 \; 6 \; 8 \; 14) (5 \; 13) (11 \; 12)$. Find $\tau$ such that $\tau^3 = \sigma$. I know that there are $2$ cases. First ...
Mr. Sir's user avatar
  • 79
2 votes
1 answer
90 views

Cardinality of a certain subset of group $S_k$ defined in connection with cycle decompositions

I am interested in a subset of the permutation group of $k$ elements, $\Sigma_k$. Any element in $\Sigma_k$ can be decomposed into disjoint cycles in a unique way. Conversely, if we take a partition ...
MathBug's user avatar
  • 374
2 votes
0 answers
47 views

Invariants of the Hyperoctahedral group

Apologies in advance for what I am asking might be too trivial, I am not a mathematician. I have a function $V(x_1,\dots,x_n)$ that could have, at most, a hyperoctahedral (signed permutations) ...
João Viana's user avatar
1 vote
1 answer
61 views

Show that a permutation equation has 5 solutions

How can I show that this permutation equation has 5 solutions: $\pi^{2013}$ = (1 9) (2 8) (3 7) (4 6) (5) Since the cycle structure is [2, 2, 2, 2, 1] then the only possible cyclic structure for the ...
Aljaz Brodar's user avatar
0 votes
1 answer
135 views

A permutation $\sigma$ of $\{1,2,\dots,14\}$ has $2$ cycles of length $4$ and $2$ cycles of length $3$. How many $\pi$ are there s.t. $\pi^2=\sigma$?

A permutation $\sigma$ of $\{1,2,\dots,14\}$ has $2$ cycles of length $4$ and $2$ cycles of length $3$. How many permutations $\pi$ are there st $\pi^2=\sigma$? So $\pi$ could be made of $1$ cycle of ...
fonso's user avatar
  • 1
12 votes
0 answers
99 views

If $\binom{n}{2}$ is even, then can you always express the identity permutation as a product of all distinct transpositions in $S_{n}$?

For which $n\geq 2$, is it possible to express the identity permutation as the product of all $\binom{n}{2}$ distinct transpositions in $S_n$? Clearly, we require $\binom{n}{2}$ to be even, which ...
Randall's user avatar
  • 387
5 votes
6 answers
382 views

Number of permutations in the symmetric group $S_n$ composed of $k$ disjoint $m$-cycles

Find the total number of permutations in the symmetric group $S_n$ that are composed of $k$ disjoint $m$-cycles, for valid $m$ and k. I encountered a simpler version of this question in class for $m=...
123's user avatar
  • 53
0 votes
0 answers
8 views

How to optimally distribute relative position using an $n$-cycle

Consider $n$ objects arranged in order: $A=\{1,2,\ldots,n\}$ and an $n$-cycle $\varphi$ from $S_n$. To motivate what I will ask, consider when $\varphi=(12\ldots n)$, and how the powers of $\varphi$ ...
2'5 9'2's user avatar
  • 54.6k
0 votes
2 answers
117 views

How can I tell if a permutation can be expressed as the commutator of another 2 permutations?

Given a permutation, how could I tell if it can be decomposed into the commutator of 2 permuations? I have known the formula of commutators and the following fact $$[(a,c),(b,c)]=(a,b,c)$$ But for ...
Nekomiya Kasane's user avatar
2 votes
0 answers
37 views

What Family of Groups is Similar to Semidihedral?

I was excited to find that the semidihedral group of order 16 matches what I'm looking for as a model. The larger order semidihedral groups unfortunately do not generalize the relations I'm looking ...
Barri's user avatar
  • 511
1 vote
1 answer
127 views

Combinatorial proof for Stirling number of 1st kind

This question is duplicate. But I have some questions about the already posted answers. And temporarily I don't have enough reputation to comment, so I post one new question. Sorry for that. This one ...
An5Drama's user avatar
  • 166
2 votes
2 answers
81 views

Do all finite-cycle-free permutations of $\mathbb{N}$ have square roots?

This answer nicely categorises which permutations of a finite set have square roots. This prompts the following question: Does every permutation $\sigma:\mathbb{N}\to\mathbb{N}$ that contains no ...
Adam Rubinson's user avatar
0 votes
0 answers
183 views

The number of cycle subgraphs in this graph

I have the following graph that is similar to Petersen's graph I was wondering if the number of cycle subgraphs is 792. Here are my arguments: Since the graph has 10 vertices, the only possible cycle ...
Gregory Wijono's user avatar
2 votes
0 answers
111 views

$n\ge 5$, prove $A_n$ is the only non-trivial proper normal subgroup of $S_n$.

Given than $A_n$ is simple for $n\ge 5$, prove $A_n$ is the only non-trivial proper normal subgroup of $S_n$. My work: Assume it is false, then there exists some non-trivial proper normal subgroup $K$ ...
GGplay's user avatar
  • 159
0 votes
0 answers
38 views

Notation for referring to specific graph colourings

Consider the following four graphs where $k$ represents the number of colours used to colour the vertices of each graph. Here cycle graphs are used to represent regular polygons, in this specific case ...
Astrid's user avatar
  • 722
0 votes
1 answer
143 views

The group $S_7$ has no subgroups of order $840$.

good afternoon everyone. I was studying group theory and came across the following exercise: Let $x=(3,4,8,6)(5,7)$, $y=(2,1)(8,6)(5,7)(3,4)$, and $G=\langle x,y\rangle$. Denote by $A,B,C$ and $D$ ...
Fqfqfqfqfqfq's user avatar
1 vote
1 answer
46 views

Conjecture: For transitive imprimitive permutation groups, the intersection of the stabilisers of any pair of blocks is not trivial

Let $G < S_\Omega$ be a group of permutations of a finite set $\Omega$ such that it is transitive, and has at least one, non trivial, system of imprimitivity $\mathcal{P} = \{B_1, \dots, B_m\}$. I ...
David Casas's user avatar
1 vote
1 answer
57 views

Permutation orders in specific symmetric groups

I've recently delved into symmetric groups and stumbled upon a notation that's left me somewhat puzzled. When analyzing a particular symmetric group, let's call it $S_n$, I've come across the set ...
ZenithZero's user avatar
-1 votes
1 answer
94 views

What is the symmetry group $S_3$ asked in this question my professor gave us? [closed]

We are following the book Abstract Algebra: An Introduction by W. Hungerford in my Group Theory class and my professor asked this exact question on the quiz: $S_3 = \langle a, b \mid a^3 = b^2 = 1, ...
Zek's user avatar
  • 309
3 votes
1 answer
72 views

Number of Cycles from a Permutation

Let $P(n)$ be the number of cycles in a $2^n$-length permutation where the odd numbers come first and then the even numbers. For example, the permutation from $P(3)$ would be $\{1, 3, 5, 7, 2, 4, 6, 8\...
FaranAiki's user avatar
  • 297
0 votes
0 answers
21 views

Is it true that for every initial distribution of the chips you can get any possible distribution?

Several boxes are arranged in a circle. Each box may be empty or may contain one or several chips. A move consists of taking all the chips from some box and distributing them one by one into ...
O_2djdkdkdkfo's user avatar
1 vote
0 answers
78 views

How can I prove the transitivity part of the following lemma?

I'm reading this article: https://www.ams.org/journals/tran/1984-282-02/S0002-9947-1984-0732119-5/S0002-9947-1984-0732119-5.pdf , and I'm having trouble with lemma 4.3. More specifically I can't find ...
MySelf's user avatar
  • 31
1 vote
0 answers
53 views

Writing the product of cycles as disjoint cycles, but yielding to different result when applying it.

I'm studying the symmetric group $S_n$ of permutations from $\{1,2,\ldots,n\}$ to itself. I'm doing a problem where I have to show that $$S_4\cong \langle a,b~|~a^4=b^2=(ba)^3=1\rangle.$$ I thought ...
Fabrizio Gambelín's user avatar
1 vote
0 answers
42 views

How many inversions in a permutation contain a fixed point?

An inversion occurs in permutation $X$ when $i < j$ and $X_i > X_j$, or when $i > j$ and $X_i < X_j$. A fixed point occurs when $X_i = i$, i.e., it is a cycle of length 1. If the pair $(...
virtuolie's user avatar
  • 161
1 vote
0 answers
18 views

Orders of products of $(n-1)$-cycles in the symmetric group $S_n$

I am interested in the orders of products of $(n-1)$-cycles in the symmetric group $S_n$. In particular what orders of elements can occur as products of $m$ $(n-1)$-cycles for $m=2, 3, 4,\ldots $? It ...
D.N. Yetter's user avatar
0 votes
1 answer
55 views

What's the inductive hypothesis here?

This question pertains to the proof mentioned in this question. What is the inductive hypothesis here? As I can decipher it, it seems like: If $i$ is the number of terms in 2-cycle identity ...
Shyam Tripathi's user avatar
0 votes
0 answers
29 views

Hamilton paths skipping some vertex relations

I have been developing a Python code to compute all the Hamilton cycles for a system but excluding those that have a maximum distance d between vertices. Hence, for d=1 i would only have a single ...
Joan Grebol's user avatar
-1 votes
2 answers
119 views

Why are there elements of order $6$ in the permutation group $S_5$? [closed]

I understand that an element in $S_5$ can have an order $6$ if it is product of two disjoint cycles of one of length $2$ and another of length $3$, but I do not understand why these elements have an ...
Ava Kate Lich's user avatar
-1 votes
1 answer
80 views

Finding a permutation $a$ such that $a^{-1}(12)(34)a=(56)(13)$

The question is to find the permutation $a $ such that $a^{-1}xa=y$ where $x=(12)(34) $ and $y=(56)(13)$ I found some answers to this question in this site but those don't clarify my doubt. This is my ...
Lakshmi Priya's user avatar
0 votes
2 answers
35 views

Decomposition of permutation from disjoint cycle

I am a beginner, so my notations could be wrong. Consider in disjoint cycle notation: $ X = (1)(2, 3, 16, 8, 10, 5, 14, 4, 12, 13)(6, 9)(7)(11, 15) $, $Y = (1, 10, 6, 12, 8, 9, 3)(2, 14, 16, 11, 13, ...
hola's user avatar
  • 1,329
0 votes
0 answers
28 views

Let $\sigma = (1 ... n)$. Prove $C_{S_n}(\sigma) = \langle\sigma\rangle $. [duplicate]

Let $\sigma \in S_n$ s.t $\sigma = (1 ... n)$. Prove $C_{S_n}(\sigma) = \langle\sigma\rangle$. So we this is what I have and I'll also explain where I'm stuck: We know $C_{S_n}(\sigma) = \{\tau \in ...
MathStudent101's user avatar
0 votes
1 answer
34 views

Rewriting simple permutation

I am learning about the symmetric and permutations and I have gotten a bit confused about the cyclic notation. From what I read in my lecture book, I would assume that we can rewrite $(12)(13)$ as $(...
Lenov's user avatar
  • 131
0 votes
0 answers
33 views

How is this product equal to this permutation?

This is like the third time the author has brought up something without explanation in this section... Anyway, in one example right after showing how every permutation can be written as the product of ...
iwjueph94rgytbhr's user avatar
1 vote
1 answer
49 views

Product of a transposition with any $k$-cycle

Given a transposition - say $(12)$ - is there a simple way to work out the product (from the left or from the right) of this transposition with any other $k$-cycle, such as $(124)$, $(134)$ or $(234)$,...
ZeroTheHero's user avatar
3 votes
1 answer
109 views

Type that maximize the number of permutations

Given a permutation $\sigma \in S_n$, the type of $\sigma$ is the $n$-uple $(c_1,...,c_n)$ where $c_k$ is the number of cycles of $\sigma$ of lenght $k$. It's easy to prove that the number of ...
Kandinskij's user avatar
  • 3,699
0 votes
0 answers
27 views

Multiplying Cycles and permutation

So I did this task "Let A4 be the alternating group on 4 letters, that is the subgroup of S4 consisting of even permutations. Find elements σ1, σ2, σ3 ∈ A4 such that σ1 has order 1, σ2 has order ...
user1162295's user avatar
1 vote
1 answer
39 views

Permutation series

I need your help about a series : $$ \forall n \in \mathbb{N}^* \backslash\left\{ 1 \right\} \mbox{, } \sum_{\sigma \in S_n} \sigma(1) $$ My goal is to give an explicit formula for this series. I ...
Tohiea's user avatar
  • 405
2 votes
1 answer
122 views

A circle permutation problem.

Four white beads, two red beads, and two blue beads are strung together to form a necklace. How many ways are there to string the beads? By the way, the beads are indistinguishable. Respond to @Arthur:...
WenheWang's user avatar
1 vote
0 answers
40 views

Permutation of combinations with a certain property

Let $1 \le k \le n$ be integers and let $S_k$ be the set of all $k$-size subsets of $\{1, \ldots, n\}$. I am interested in conditions on $n$ and $k$, such that there exists a permutation $\pi$ of $S_k$...
taninamdar's user avatar
  • 2,598
1 vote
2 answers
116 views

Prove exists embedding $\phi: \mathbb {Z}_3 \times \mathbb {Z}_3 \times \mathbb {Z}_3 \to S_{27}$ s.t. ${\rm Im}\phi$ intersects 2 conjugacy classes.

Question: Prove exists an embedding $\phi: \mathbb {Z}_3 \times \mathbb {Z}_3 \times \mathbb {Z}_3 \to S_{27}$ such that ${\rm Im}\phi$ intersects exactly 2 conjugacy classes of $S_{27}$. I'm pretty ...
MathStudent101's user avatar
0 votes
0 answers
36 views

Pairs with relations

Let $\mathrm{p}$ be a prime number at least three and let $\mathrm{k}$ be a positive integer smaller than $\mathrm{p}$. Given $\mathrm{a}_1, \ldots, \mathrm{a}_{\mathrm{k}} \in \mathbb{F}_{\mathrm{p}}$...
Snowball's user avatar
  • 1,064
2 votes
1 answer
100 views

Number of fixed points of elements of a dihedral group

Suppose that $D_{2n}=\langle r,s\vert r^n=s^2=1,\, srs=r^{-1} \rangle=\lbrace1,r,\cdots, r^{n-1}, s,rs,\cdots, r^{n-1}s\rbrace$ denotes the dihedral group of order $2n$. We know that the conjugacy ...
M. R.'s user avatar
  • 491
0 votes
0 answers
56 views

For $1 \le i \lt j \le n$ and $d=j-1$, prove $S_n = \langle\{i\;\; \overline {i+d} : 1 \le i \le n\}\rangle$ $\iff$ $gcd(d,n) = 1$

So in the first part of the question I had to prove that $gcd(d,n)=1 \implies S_n = \langle\{(i\;\; \overline {i+d}) : 1 \le i \le n\}\rangle$ whilst $\forall a \in \mathbb {Z}$, we mark $\overline {a}...
MathStudent101's user avatar
0 votes
0 answers
57 views

Finding all permutations which follow reflection symmetry

I am unsure how to write down these questions formally, so here is some python code and the problem in words. I am looking to find all permutations which subscribe to reflective symmetry. For example, ...
Astrid's user avatar
  • 722

1
2 3 4 5
14