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
26 views

How to represent the sum of matrix elements given all permutations of a set of indices?

I would like to represent the sum all matrix elements of all permutations of indices given a set. For example, given the set $S=\{1,2,3\}$ I would like to compactly express ...
3
votes
3answers
269 views

How many four-digit odd numbers, all of digits different, can be formed from the digits 0 to 9, if there must be a 5 in the number?

How many four-digit odd numbers, all of digits different, can be formed from the digits 0 to 9, if there must be a 5 in the number? I know that there are 4 different cases where 5 is in the ...
2
votes
3answers
40 views

Cardinality of the set of automorphisms of $(\mathbb{N},+)$

I wonder if the set of bijections $\sigma\,:\mathbb{N}\to\mathbb{N}$ that satisfy $$ \sigma(a+b) = \sigma(a)+\sigma(b)\qquad \forall a,b\in\mathbb{N} $$ is countable or uncountable. What if we also ...
0
votes
2answers
28 views

Even permutations

I am given the symmetric group $S_{9}.$ Let $$\sigma = \begin{bmatrix} 1 & 2& 3& 4& 5& 6& 7&8 &9 \\ 4& 8& 7& 9& 3& 1& 2& 5 ...
1
vote
1answer
43 views

Composition of groups

Let's say we have a system of interacting particles that can divided into two populations. The symmetry group of each population is $G$, and the two populations are identical, so that I can exchange ...
1
vote
2answers
43 views

What is the best algorithm for finding a $g \in S_n$ which $a^g=b$ for given $a, b \in S_n$

What is the best algorithm for finding a $g \in S_n$ which $a^g=b$ for given $a, b \in S_n$, where $S_n$ is a symmetric group and $a$ and $b$ have same cycle type? Question 2: Is there any command in ...
0
votes
2answers
20 views

Showing the permutation of 2 elements in a symmetry group is an even permutation

Show that for every 2 elements $\alpha$ and $\beta$ in $S_{8}$, the permutation $\alpha ^{-1}\beta ^{2}\alpha $ is an even permutation. How do I show that the above is an even permutation? I know ...
2
votes
1answer
50 views

Help with proof of the fact that $\det(A) = -\det(B)$, permutations

I got a couple questions regarding a proof of a well known property of the determinant. I'm not sure if the proof is correct (found it online): Proposition: If $B$ is a matrix gotten from $A$ by ...
0
votes
1answer
25 views

Help with understanding a proof on permutations

I've come across a theorem in Serge Lang's Linear Algebra, which I'm having trouble understanding. First I'll write the proof then indicate which part I do not understand: Proposition: Every ...
2
votes
1answer
29 views

square of a permutation cycle

$$\sigma = \begin{bmatrix} 1 &2 &3 &4 &5 &6 &7 &8 &9 \\ 1&5 &7 &4 &6 &9 &3 &2 &8 \end{bmatrix}$$ $$\sigma^{2} = ...
7
votes
3answers
124 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
35 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 ...
1
vote
0answers
33 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
57 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
34 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 ...
0
votes
2answers
49 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
16 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 \; | \; ...
0
votes
1answer
62 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
57 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
46 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 ...
0
votes
0answers
29 views

n positions to be filled by only x and y, such that no 2 x occur together [duplicate]

i'm not very good with permutations and combination, i need help with this problem. i need to use it in a programming question. Can someone derive a formula for "n positions to be filled by only x and ...
0
votes
1answer
48 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
17 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
54 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
19 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, ...
0
votes
1answer
28 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
56 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
65 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 ...
0
votes
1answer
33 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, ...
2
votes
1answer
68 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
44 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
109 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
129 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
25 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
37 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
29 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 ...
2
votes
1answer
27 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 ...
0
votes
1answer
36 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
14 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
17 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
27 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 ...
0
votes
1answer
41 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$ ...
0
votes
0answers
25 views

Counting number of ways in which switches can be pressed IF order doesn't matter

If there are given "K" number of distinct switches and "N" is any large number representing the total number of times those "K" switches will be pressed. We can easily say that the total number of ...
3
votes
1answer
18 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
23 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
136 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
48 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
23 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
37 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
80 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$?