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

learn more… | top users | synonyms (1)

1
vote
0answers
26 views

How many permutations cover alternating/reverse alternating permutations?

Given integers $1$ through $2n$, let $S$ be set of ordering of integers that respect even alternating or reverse alternating permutations (https://en.wikipedia.org/wiki/Alternating_permutation) up to ...
2
votes
1answer
31 views

Where do I use that $G$ is a permuation group?

This is about question $4.1.7$ from Dummit and Foote, and also related to my previous question. The question is (summarised a bit): Let $G$ be a transitive permutation group on a finite set $A$. ...
0
votes
1answer
45 views

Compose $(1243)$ and $(5)$

Checking my work. In either direction: $(1243)[1] = 2$ and $(5)[2] = 2$, so far we have $(1, 2,\ldots$ $(1243)[2] = 4$ and $(5)[4] = 4$, so far we have $(1, 2, 4,\ldots$ $(1243)[4] = 3$ and ...
0
votes
0answers
56 views

Finding permutation matrix

Let $P_{\pi}$ denote a permutation matrix associated to the permutation $\pi:\{1,...,n\}\rightarrow \{1,...,n\}$ and $\sigma$ denote the cyclic permutation $(1 2 ...n)$. If T is the $n\times n$ lower ...
0
votes
1answer
37 views

How many permutations $(a_i)_{i=1}^{30}$ of $\{1,\dots,30\}$ satisfy $m$ divides $a_{n+m}-a_n$ when $m \in \{2,3,5\}$ and $1 \le n<n+m \le 30$?

Define a permutation $(a_1,a_2,\dots,a_{30})$ of $\{1,2,\ldots,30\}$ as good if for all $m \in \{2,3,5\}$, we have that $m$ divides $a_{n+m}-a_n$ for all integers $n$ satisfying $1 \leq n < n+m ...
4
votes
3answers
100 views

Why Composition and Dihedral Group have reverse order of operation?

NOTE - I didn't receive any answer in here and I think because my first post is not clear, so I entirely made another example: $K={\{id,r^2,r^4,s,r^2s,r^4s}\}$ is a proper subgroup of the dihedral ...
1
vote
1answer
78 views

Intuitively and Mathematically Understanding the Order of Actions in Permutation GP vs in Dihereal GP

I define $r$ to be one rotation clockwise, and s to be reflection on the 'horizontal' line (see the figure). So I can make these bijections: (in clockwise order) $$\begin{align*} 1,2,3,4,5,6 ...
0
votes
0answers
102 views

Permutation equivalence classes with kendall-tau distance

Consider a set $A=\{a_1,...,a_m\}\subset \{1,...,n\}$ for which $a_i<a_{i+1}$ for all $i = 1,\ldots,m-1$. Take any two distinct permutations $\sigma, \tau$ of $\{1,...,n\}$ such that $ ...
0
votes
1answer
33 views

Permutation and signature matrices “almost commute”

Let $\mathcal{P}$ be the set of all permutation matrices of order $n$ and $\mathcal{S}$ the set of all signature matrices of order $n$. Furthermore, let $$\mathcal{P}\mathcal{S} = \{PS \mid ...
3
votes
1answer
54 views

Characterisation of the squares of the symmetric group

I found out that for $n\le 4$ we have $S_n^2=A_n$ with $G^2$ defined by $$G^2:=\{g^2 \mid g\in G\}$$ for any group $G$. Surely we have $S_n^2\subseteq A_n$ for all $n\in\mathbb N$. Is there a ...
11
votes
2answers
271 views

Show that there is always a way to achieve det(A) > 0

a) Assume that $(a_1, ..., a_9)$ are different positive numbers. Let us make a $3 \times 3$ matrix $A_s$ by placing them arbitrarily into $9$ positions available. Show that there is always a way to ...
2
votes
1answer
85 views

Proving a certain lemma about subgroups of $A_n$

In proving $A_n$ is simple for $n\neq4$, my teacher established the cases 1, 2, 3 as obvious, then proved the case 5, and proceded by induction on the rest. In the midst of that induction, he stated ...
3
votes
2answers
123 views

How to arrange 15 women and 15 men so no two females are seated next to each other?

To a certain conference, each firm can send two employee representatives, on the condition that one of them is a male and the other a female. If 15 firms were represented in this conference, what is ...
2
votes
4answers
101 views

When will Andrea arrive before Bert?

The question was as follows- on any given day, Andrea is equally likely to clock in at work any time from 8:50am to 9:06am. Similarly, Bert is equally likely to to clock in at work at any time ...
1
vote
4answers
50 views

Prove that the 4-group V is normal subgroup of $S_4$ by using isomorphism theorem

Prove that the 4-group V is normal subgroup of $S_4$ First, by using the multiplication table, I am able to prove that 4-group V is subgroup of $S_4$. But I face problem in proving that $\forall ...
1
vote
0answers
39 views

Simple string permutations question

How many sequences of 5 letters are there in which exactly two are vowels? My approach There are $5^2$ different permutations for 2 vowels and $\binom{5}{2}$ ways allocate them. There are $21^3$ ...
1
vote
2answers
40 views

Basic Password permutation question

I'm reading the problem from this stanford material (http://infolab.stanford.edu/~ullman/focs/ch04.pdf). Can you please help me understand this? Question: At Real Security, Inc., computer passwords ...
1
vote
4answers
149 views

How many words can be formed using all the letters of “DAUGHTER” so that vowels always come together?

How many words can be formed using all the letters of "DAUGHTER" so that vowels always come together? I understood that there are 6 letters if we consider "AUE" as a single letter and answer would be ...
0
votes
1answer
38 views

$S_n$ notation in permutations

What does notation $S_n$ stands for? For example if I have the following set $\{1,2,3,4\}$ so we say that $S_4$=24? Moreover in many examples I saw the use of following numbers like $\{1,2,...,n\}$ ...
1
vote
4answers
37 views

Question on Permutations Please advise

Among all seven digit decimal numbers,how many of then contain exactly three 9's? My Approach: 3 places contains only 9's---> 1*1*1 (No. of Ways to Choose out of 0 to 9) other 4 places: since first ...
3
votes
1answer
31 views

Which permutation am I? Or: what is a bijection $f:S_n \rightarrow \{1,2,\ldots,n!\}$ such that we can compute $f(\beta)$ easily?

Let $S_n$ be the symmetric group on $\{1,2,\ldots,n\}$ and assume that $S_n$ is ordered in some way, i.e., $$S_n=\{\alpha_1,\alpha_2,\ldots,\alpha_{n!}\}.$$ We are able to choose this ordering on ...
0
votes
2answers
21 views

Commutativity of cycles

Disjoint cycles commute: $(ab)(cd) = (cd)(ab)$, but do non-disjoint cycles commute? Does $(ac)(ab) = (ab)(ac)?$ Consider the composition of two permutations: $\begin{pmatrix} a & c\\ ...
-6
votes
2answers
38 views

The number of times the digit 8 will be written when listing the integers from 1 to 1000 [closed]

When i calculated the answer as 360 but in book it is mentioned 300. Please Help .
1
vote
5answers
120 views

Help needed to solve combinatorics problem.

I have been revisiting my old probability courses and I found a problem, which I can't figure out how to solve or at least what I get differs from the answer in the book. The problem reads as ...
0
votes
1answer
56 views

Number of permutations in a word ignoring the consecutive repeated characters

Given a word "aab", permutations are: aab, aab, aba, aba, baa, baa I need to get the number of permutations where characters don't repeat. So from the above permutations, I need to ignore those ...
0
votes
0answers
33 views

Trying to learn how to compose permutations

I am trying to prove myself that $(1)(2)(3)(4) = (12)(12)(3)(4).$ So, $\begin{pmatrix} 1 & 2 \\ 2 & 1 \\ \end{pmatrix}$ $\begin{pmatrix} ...
1
vote
1answer
60 views

Defeating enemy crab by cutting off legs and claws [closed]

The following is from the MIT-Harvard Tournament: You are trapped in ancient Japan, and a giant enemy crab is approaching! You must defeat it by cutting off its two claws and six legs and ...
0
votes
0answers
27 views

Problem with random permutation and conditional probability

Let $\pi_1,...,\pi_n$ be a random permutation of numbers $1,...,n$. If you are told that $\pi_k > \pi_1,...,\pi_k > \pi_{k-1}$, what is the probability that $\pi_k = n$? What I've tried: Let ...
2
votes
2answers
31 views

Permutations with Condition

I have looked at this old problem in my textbook: How many permutations $\pi \in S_n (n \geq 3)$ meet the requirement: $\pi (1) < \pi (2) $ or $\pi (1) < \pi (3)$? I am not sure how to ...
0
votes
0answers
65 views

Examples of injective maps such as MTF (Book Stack). Set of such mappings.

Let $S \in \mathbb N$. Let $\mathfrak S_S$ be the set of permutations of size $S$. Consider map $f : \mathfrak S_S \times \{1,2,\ldots,S\} \to \mathfrak S_S$, such as $f(\alpha, \cdot) : ...
0
votes
0answers
37 views

For which integers $r$ is $\sigma ^r$ also a $k$-cycle? [duplicate]

Let $\sigma$ be a $k$-cycle in $S_n$. For which integers $r$, is $\sigma ^r$ also a $k$-cycle? I think I managed to prove that this is true iff $(k,r)=1$, but my proof was too long and not elegant ...
2
votes
1answer
103 views

Rank 3 permutation groups

Let $G \leq Sym(\Omega)$ be a finite permutation group of rank 3, $\alpha \in \Omega$ and $g,h \in G$ such that $x_1 := g(\alpha)$ and $x_2 := h(\alpha)$ are not equal. Now my question is: Is there ...
0
votes
1answer
18 views

Hashing: Quadratic Probing

I have the following to prove, unfortunately I am not able to do so. Let h, h' be hash functions: $h(k,i) = (h'(k) + c_{1}i + c_{2}i^2)$ mod $m$. Show the following: if m is prime and $c_{2} \neq 0$ ...
1
vote
1answer
32 views

What is the distribution of cycle lengths in derangements? In particular, expected longest cycle.

There is a lot of information about expected cycle lengths in random permutations, but I'm having trouble adapting the arguments and calculations to the specific case of derangements - permutations in ...
1
vote
2answers
33 views

To prove an identity in permutation and combination.

I am trying to prove the following identity: ${n \choose 0}$ + ${n \choose 1}$ + $\ldots$ + $\frac{1}{2}{n \choose n/2}$ = $2^{n-1}$ where $n$ is even I know that I have to use few relations like ...
2
votes
1answer
36 views

Disjoint Cycles in a Cyclic Subgroup of $S_n$

If a permutation $\sigma$ $\in$ $S_n$, the permutation group of n elements, and $\sigma$ can be expressed as a product of disjoint cycles, is it necessary that the disjoint cycles be elements in ...
1
vote
3answers
71 views

In how many ways can a natural number be written as a sum of $2$ natural numbers?

For example, $7=1+6,2+5,3+4$. Hence $7$ can be written as a sum of $2$ natural numbers in $3$ ways.
0
votes
1answer
54 views

Random permutation and isolated points on the line

Let $[n]=\{1,\dots,n\}$ be the (ordered) set of the $n$ first integers, and $\mathcal{S}_n$ denote the set of permutations of $[n]$. Let $1\leq k \leq \frac{n}{4}$ be an integer. If I draw uniformly ...
0
votes
1answer
21 views

Success rate of a player trying to guess a bitstring with given constriants

For work at my university I try to solve a problem. I have a bit string with given length $len$ and count of active bit $active$ An example could be: 1001 0110 ...
-1
votes
2answers
37 views

Prove a cycle of length l is odd if l is even? [closed]

This is my first course on Group Theory. How do I go about proving this?
0
votes
1answer
54 views

Number of ways arranging entries of a tuple - combinations or permutations

Let $x=(x_1,x_2,\ldots,x_n)$ be an $n$-tuple where $n$ is even In how many ways we can arrange such that exactly half of the entries are even ? My attempt is : As we are talking about possible ...
2
votes
3answers
55 views

find all odd permutations $\sigma \in S_4$ such that $\sigma (123) \sigma^{-1} = (234) $

need help with this question... find all odd permutations $\sigma \in S_4$ such that $\sigma (123) \sigma^{-1} = (234) $ really have no idea how to approach this. thanks.
1
vote
1answer
35 views

Finding the number of combinations

A teacher distributes 7 books to 7 children (each student a books), on the next day she collects the books back and redistributes in such a way that each students get a new book. In how many ways can ...
2
votes
1answer
77 views

Find the probability of at least two vowels together when letters in word “AEINCB” are rearranged for all random permutations.

Find the probability of at least two vowels together when letters in word "AEINCB" are rearranged for all random permutations. What will be new probabilities when word is changed to either "AEINCBB" ...
0
votes
0answers
48 views

Can anyone explain these conclusions? Permutations, Symetric group…

The conclusions start off like this:I will highlight what is unclear in yellow. $sgn G$-sign of G permutation, $Ker$-kernel of a function Lets define the function: $\ \Phi$ like: $(\forall G \in ...
3
votes
2answers
46 views

Finding the number of ways of picking three cards

Problem: An urn has 10 red cards numbered 1 through 10 and 8 blue cards numbered 1 through 8. Three cards are randomly drawn, one at a time, without replacement. Find the number of ways to ...
3
votes
2answers
64 views

Finding how many bits of length n there are

So we are starting on the section of combinatorics in my discrete math class and our instructor gave us a simple problem to see if we understood what we learned that day. The problem consists of three ...
0
votes
2answers
49 views

question based on probability/permutation/combination

In a box containing $15$ apples, $6$ apples are rotten. Each day one apple is taken out from the box. What is the probability that after four days there are exactly $8$ apples in the box that are not ...
3
votes
1answer
50 views

Sum of Permutations of n objects taken r at a time ( r=1 to n ) where objects may be groups of same entities

Given n objects where n1 objects are the same ,along with another group of n2 objects of same element etc.. such that Σni = n (i=1 to k). Assuming there are k groups of similar objects eg: in ...
-2
votes
1answer
52 views

Sum of all the numbers with the given numbers repeated

How to find the sum of all the numbers that can be formed using the digits 4,5,5,6,6,6 (This includes 4,5,6,45,46,54,55,....,666554). I knew that the answer is 39345806. I just need to know the method ...