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

learn more… | top users | synonyms (1)

8
votes
3answers
228 views

Random Sequence of Alternating Increase/Decrease Numbers

The problem statement: Repeatedly pick a random number (uniformly-distributed) between $0$ and $1$. Keeping going while the second number is smaller than the first, the third number is larger than the ...
2
votes
2answers
61 views

Counting nearly-sorted permutations

Let $[n]$ denote the set $\{1,2,\ldots,n\}$. We call a permutation $\sigma:[n]\to[n]$, $(n,k$)-nearly sorted if $$\forall i\in [n]: |\sigma(i) - i|\le k,$$ i.e., every element is shifted at most $k$...
1
vote
0answers
78 views

I need to prove that there is one homomorphism $\varphi : Dn \to Sn$ such that

I need to prove that there is one homomorphism $\varphi : Dn \to Sn$ such that $\varphi$($\tau$) = $$ \begin{pmatrix} 1 & 2 & . & .& . & n \\ 2 & 3 &...
3
votes
2answers
67 views

How many strings of $8$ English letters are there (repetition allowed)?

a) at least one vowel b) start with $x$ and at least one vowel c) start and end with $x$ and at least one vowel I can solve them easily by considering $total-no$ $vowel$. So, a) $26^8 -21^8$ b) $...
0
votes
1answer
75 views

How many strings of $3$ decimal digits have exactly two digits as $4$?

I approached the problem in this way : Fix two $4's$ and then third place can have $10$ ways to choose from {0,1,..,9} and then arrangement= ${10*3!}/2!$ = 30But , Since we have {$4,4,4$} and {$4,4,0$}...
0
votes
2answers
141 views

5 people into 8 seat train compartment

question for you all. In how many ways 5 people can be seated into an 8 seat train compartment, knowing that 2 people always sit by the window? would it be 6 choose 3 + 5 choose 2 ? that would give ...
0
votes
1answer
18 views

Question about Chapman's *An involution on derangements*

The (one-page-long) paper is available here: http://www.sciencedirect.com/science/article/pii/S0012365X00003101 To recap: For a permutation $\sigma$, we write $a_\sigma := \min \{ a \; | \; \sigma(...
0
votes
1answer
68 views

Hopefully simple permutations question

Say I have a permutation $B_{1}=(2,4,1,3).$ Now I'm thinking about a permutation $\sigma_{2}$ that gives me the permutation $(4,2,1,3)=\sigma_{1}$ from $B_{1}$, $\sigma_{2}B_{1}=\sigma_{1}.$ To ...
0
votes
3answers
62 views

Multiplying array elements

We are given a sorted array containing elements at indices $x_1,x_2,x_3,x_4,....x_n$. We have to find the product $\displaystyle\sum_{i,j,k}x_ix_jx_k$ where $j\geqslant i$ and $k\geqslant j$. For ...
2
votes
1answer
54 views

Professor has collection of $40$ issues of journal in $4$ boxes with $10$ issues per box.

Professor has collection of $40$ issues of journal in $4$ boxes with $10$ issues per box. How to distribute the journals if: $(a)$ each box is numbered $(b)$ boxes are identical I thought ...
0
votes
1answer
58 views

An expression to represent all possible arrangments of a set of length n into 3 (infintely sized) bins?

I have a set, A = {1,2} And I generate a set, B, of all possible arrangements of the above set across 3 "bins" (note where 1 and 2 are together, they are summed): ...
0
votes
1answer
28 views

Need help understanding the precise meaning of “unique factorisation of disjoint cycles”

Below is taken from my linear algebra course lecture notes: Some facts about permutations of $\{1,2,\dots,n\}$: Every permutation is a product of disjoint cycles which commute. For example ...
1
vote
1answer
613 views

How many four-digit numbers can be arranged from the numbers {0, 1, 2, 3, 4}, when each number can be repeated a maximum of 3 times?

I just can't wrap my head around this. Maybe I'm overthinking it. I tried to use permutations with indistinguishable objects but I failed. Please help :(
1
vote
0answers
76 views

Cycle Structure of a Permutation Based on the Binary Representation

Define a permutation $\sigma$ on the set $X=\{1,2,...,n\}$, $n$ is a natural number as follows. Given a non-negative integer $k$, let $s(k)=\frac{b+1}{2}$, where $b=\max\limits_c\big(c2^k\le n, c\text{...
0
votes
1answer
48 views

Probability for unknown events

Let A arrive in a party in the time interval [0,a] and B arrive at the same party in the time interval [0,b]. What will be the probability that both of them arrive at the same time ? Note : Arrival ...
0
votes
4answers
173 views

How many different words can be formed from the word FACETIOUS (taking all letters), leaving the vowels in order A,E,I,O,U?

I thought of fixing _A_E_I_O_U_ first, and then remaining $6$ places can be occupied by F,C,T,S in several orders:Case $1$: {F,C,T,S} as a group of $4$ can occupy in $C(6,1)$ and then permute them = $...
0
votes
0answers
125 views

How many ways we can arrange numbers such that sum of arrangement will be a given number

we have a value $p$ and we have to arrange numbers at $p$ places such that no number is greater that $p$ and no number is less than $0$ and also sum of arrangement should be a given number (suppose $k$...
0
votes
1answer
46 views

Total Number of strings

I came across the following question on SPOJ. Find the number of strings of length “N” made up of only 3 characters – a, b, c such that “a” occurs at least “min_a” times and at most “max_a” times, “b”...
2
votes
1answer
78 views

how to solve this permutation

In how many ways a Table with $N$ rows and $M$ columns can be created so that sum of elements in $i$th row is greater or equal to the sum of elements in $(i-1)$th row for $ 2 \le i\le N$ and sum of ...
2
votes
1answer
48 views

Permutation problem!

I was recently trying to do an exercise that I am either misinterpreting or is wrong: Show that each transposition $(k,k+1)$ is a product of $(1,2)$ and powers of the $n$-cycle $(1,2,...,n)$. I ...
4
votes
3answers
114 views

$(12) \notin \langle (132), (123456) \rangle$

How can I prove/disprove that as an element of $S_6, $ $(12) \notin \langle (132), (123456) \rangle$. We can use GAP to check this, but by hand it looks not so obvious. Let $r=(123456)$ is odd and $...
10
votes
4answers
195 views

Can we count odd and even derangements nicely without taking a determinant?

It's not hard to see that $$\det \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$$ is equal to #(even derangements on 3 elements) - #(odd derangements on 3 ...
0
votes
1answer
35 views

Order of $\epsilon$ Permutation?

From Prof. Pinter's "A Book of Abstract Algebra", here's a table for a group of permutations: The "Order of Group Elements" chapter explains the concept of order. It explains that, per the above ...
2
votes
0answers
53 views

Cycle detection in a pseudo-Latin square

Given a matrix of size $m \times n$ with no repetition of values in rows or columns, is there an efficient method of detecting cycles? For example, here is a sample matrix: 3 5 2 9 7 4 ...
0
votes
1answer
186 views

12 students in a class, how many ways these can take 4 different tests if 3 students are to take each test?

Can I approach the problem as 12-digit number with each digit having $4$ possible values and then $3$ digits must take $4$ values , so C($12$,$3$)*$4^3$ and how to do the rest part for remaining $12-3=...
2
votes
1answer
28 views

Group action permutations

I have this triangle $\hskip2,5in$ In my notes I have that the permutation $(1 2)$ leaves $x$ unchanged and interchanges $y$ and $z$. With the permutation $(1 2 3)$, $x$ maps to $y$, $y$ maps to $z$...
0
votes
1answer
150 views

Output all permutations using 0-9 of of n-size up to 25. [Python]

Solving a problem in which I need to generate all possible permutations using the elements [0-9] of a number of n-size up o 25; where repetition is allowed. I've been using Python with different ...
0
votes
1answer
15 views

When to close brackets in product of disjoint cycle

when expressing 2 composition of function as a product of disjoint cycles, when do we 'close' the bracket? None of the sources explain this clearly. Some do not even make an attempt to.
0
votes
0answers
23 views

90 degrees CCW permutation of a square ($D_4$)

Given a square and a permutation of 90 degrees counter-clockwise, what is the order of this finite symmetry group? Here's an attempt: $$\rho =\begin{bmatrix} 1 &2 &3 &4 \\ \rho (1) &...
1
vote
1answer
38 views

large permutation question

What are the permutations of the following: 7 marbles each of 4 colors, for a total of 28 marbles. A 5x5 board, so 25 places for 1 marble to be placed. What are the permutations of placing the 25 ...
-1
votes
1answer
48 views

A problem relating to combinatorics/ Permutation|Combination [closed]

The question is: (I actually may have messed up!) Suppose we have $4$ numbers namely : $a,b,c$ and $d$ Now we need to compare two of these numbers four at a time. For example : $a>b$ |...
3
votes
1answer
39 views

The number of adjacent transpositions

If $\alpha\in S_{k+l}$, $\alpha=\left(\begin{array}{cccccc}1&\cdots&k&k+1&\cdots&k+l\\l+1&\cdots&l+k&1&\cdots&l\end{array}\right)$, for $k,l\in\mathbb{Z}^+$ ...
-2
votes
1answer
39 views

Compute Square of Permutation

Dr. Pinter's "A Book of Abstract Algebra" presents the preface to a few exercises: In $S_{5}$, express each of the following as the square of a cycle (that is, express $\alpha^{2}$ where $\alpha$ is ...
5
votes
1answer
306 views

Oberwolfach Problem - 30 people at dinner on 3 tables of 10 seats each

There are $30$ people at an alumni dinner, seated at $3$ round tables of $10$ seats each. After every time interval $\Delta t$, a position change event is required where everyone changes position ...
-1
votes
2answers
64 views

Representing a 5-cycle as a product of transpositions

Dr. Pinter's "A Book of Abstract Algebra" shows that: $$(12345)$$ can be written as the following product of transpositions: $$(54)(53)(52)(51)$$ How can the first representation, $(12345)$, be ...
2
votes
0answers
26 views

On permutation notation

I am trying to write up a proof that the parity of permutations on finitely many letters is well-defined. I think I have a proof that involves the number of disjoint cycles that a permutation may be ...
3
votes
0answers
45 views

Identity element of a group as a factorization of group elements.

For any group $G$ we readily verify that if $a,b,c\in G$ and $a*b*c=e$ , where $e$ denotes the identity element,then also: $b*c*a=e$ Indeed,let $b*c=x$.Then our problem amounts to: $a*x=e⇒x*a=e$ This ...
4
votes
2answers
155 views

Split a number into parts

In how many ways can a natural number $n$ be split into $m$ natural numbers (parts) where each part is less than $n$, the parts don't necessarily have to be equal, and all of them add up to $n$?
5
votes
2answers
300 views

seating arrangements of four men and three women around a circular table

In how many ways can $4$ men and $3$ women be arranged at a round tale if i)the women always sit together? ii)the women never sit together? I attempted both the questions but the answers I got don't ...
2
votes
1answer
40 views

A combinatorial question about outer automorphisms of $S_6$

Quite possibly I'll solve this and post my answer below, but maybe others will post better answers before I get to that. Or after.$^\dagger$ The group of permuations of $\{a,b,c,d,e,f\}$ is ...
3
votes
0answers
59 views

Conjugation of permutations

In the group $S_n$ I usually use the fact that if $(a_1 a_2 \dots a_r) \in S_n$ is an r-cycle and $\sigma \in S_n$ then $\sigma (a_1 a_2 \dots a_r)\sigma^{-1} = (\sigma(a_1)\sigma(a_2) \dots \sigma(...
0
votes
1answer
124 views

Transitive action of the group implies isomorphism with the quotient by stabilizer

Let $\Omega$ be a set and $G$ a subgroup of the group $Sym(\Omega)$ of permutations of $\Omega$. Let $\omega \in \Omega$ and let $G_{\omega}$ denote the stabilizer of $\omega$ in $G$. If $G$ acts ...
-1
votes
1answer
86 views

Combinations without Repetition [closed]

For calculating follow Combinations RRDD RDRD RDDR DRRD DRDR DDRR answer is $\frac{4!}{(2!\times2!)}$. First divide into $2!$ is because does not matter order ...
5
votes
1answer
116 views

Permutations of cards with no adjacent pairs

We have a standard 52-card deck, and are looking at the possible shuffles/permutations of this deck. However, we have rubbed off the suits from the cards, so for every rank (aces, tens, etc.) all 4 ...
2
votes
1answer
124 views

What is the use and motivation for this particular concept in permutations?

Say you have the permutation $(54231)$ element of $S_5$ Now you drop say the "4" and then re-rank the remnant permutation on the other elements. Then you are left with, $(4231)$ element of $S_4$ ...
1
vote
0answers
25 views

Mixing time of three particle systems

Is there anything known about mixing time of Markov chains for three particle systems? It is proved here that the mixing time of an exclusion process is $\operatorname{O}(n)$. We can think if a ...
4
votes
1answer
50 views

Anagram with condition on last letter

How many ways can "computer" be arranged with a vowel as last alphabet? Isn't it $7! \times 3 $? since there are 3 vowels. $3$ (e,o,u) $ \times 7!$(number of arrangement without one of vowel). Shouldn'...
0
votes
2answers
35 views

Permutation and Combinations Problem.

There are m copies of each n books on different subjects in the college library. The number of ways in which one or more books can be selected is ...?? I have no idea to deal with this problem , ...
1
vote
1answer
51 views

Natural action of $S_n$ on $\{ 1,2,\dots,n \}$

From reading online the "natural" action of $S_n$ on $\{ 1,2,\dots,n \}$ is $(g,x) \mapsto gx$. How is this action transitive? As far as I can see if we take $g$ to fix some element we will not get a ...
0
votes
2answers
2k views

How many 2 digit even numbers can be formed from these numbers?

How many even 2 digit numbers can be formed from the numbers 3,4,5,6,7? The digits cannot repeat (you can't have 44 or 66 for example). I know the answer to this is 8, because I just wrote them all ...