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

learn more… | top users | synonyms

4
votes
1answer
69 views

Calculating the sign of the generalised permutation

What is the sign of the following permutation. Prove your answer: $$\pmatrix{1 & 2 & \cdots&p&p+1&\cdots & \cdots &p+q \\ q+1 & \cdots & \cdots & q + ...
1
vote
1answer
145 views

Bit permutations and collisions of compression function

I'm having trouble finding a good method for solving the following problem: If $n$ is a positive integer, let $S_n$ denote the group of permutations of the set $\{1,2,\dots, n\}$. For a permutation ...
0
votes
1answer
41 views

Listing the elements of $A(3)$

List the elements of $A(3)$ and give the order of each of them. This is about permutations in number theory ... to clarify that $A(n)$ Thanks!
1
vote
2answers
108 views

Finding the sign of each permutations

How to find the sign of each of the following permutations? 1, (1 2 3 4 5)(8 7 6)(10 11) 2, (1 3 5 7 9 11)(2 4 6 8 10) 3, (1 2)(3 4)(5 6 7 8)(9 10) 4, (1 2 3 4 5 6 7 8)(1 8 7 6 5 4 3 2) Help ...
0
votes
1answer
114 views

Explanation on step $\rho$ of the SHA-3 algorithm

I'm working on implementing SHA-3 in a PIC microcontroller. In the block permutation, I don't quite understand step $\rho$: Bitwise rotate each of the 25 words by a different triangular number 0, ...
2
votes
1answer
60 views

Any comprehensive material to revise the mathematics

I left school long back and so my mathematics knowledge also fades out. I am trying hard to re-collect the basics about log / permutaion / combination / probability / polynomial equations. I tried ...
1
vote
3answers
30 views

this can be solved bypermutation and combination based problem

How many three are there whose hundred digit is greater than tens digit which in turn is greater than the unit digit? Ans:I tried it But couldn't solve..
7
votes
1answer
235 views

How do combinations (not permutations) relate to group theory?

First question. I'm just generally curious about combinations in group theory. How do they relate? If I take the set of permutations of $\langle 1,2,3,4 \rangle$, I get the symmetry group S4. How ...
0
votes
1answer
169 views

Permuation with repeated letters and consecutive letters not same

I have been trying to solve a question on permutation and haven't really been successful. I want to generate all the permutations of a specified length that start with a letter and end with the ...
3
votes
4answers
107 views

Is my textbook wrong?

My textbook says (without explaining how it is done): $$\begin{pmatrix} 1\ 2\ 3\ 4\\ 2\ 1\ 4\ 3 \end{pmatrix}\begin{pmatrix} 1\ 2\ 3\ 4\\ 2\ 3\ 4\ 1 \end{pmatrix}=\begin{pmatrix} 1\ ...
2
votes
2answers
279 views

Dihedral group and cyclic group theorem.

Let $D_n$ be the dihedral group defined by $D_n=$ {$I,R,R^2,...,R^{(n−1)},r,rR,rR^2,...rR^{(n−1)}$} Theorem. A nontrivial proper subgroup $N$ of $D_n$ is normal in $D_n$ if and only if $N$ is a ...
0
votes
1answer
71 views

number of ways of placing balls on plate

There are n plates places in a line and unlimited number of red balls with values from 1 to ...
1
vote
1answer
425 views

Doubt on married couple seating arrangement problem

I am going through a solution of the following problem. "How many ways there are there to seat $n$ couples around a circular table with $2n$ chairs such that no couple sits next to each other, i.e., ...
1
vote
1answer
65 views

Number of arrangements around a table

My doubt is based on two observations : 1) On top of a round table (which is rotatable) there are $n$ places to sit and we need to place $n$ people. How many ways is it possible to permute them ? ...
4
votes
0answers
44 views

Classification of $n \times n$ matrix in which each two components differ in each row and column up to automorphism

Suppose, we define a class $A$ of $n \times n$ matrix as follows: $$\text{In each Row }i, \text{for any} j,k\ (1 \leq j,k \leq n )\ a_{ij} \neq a_{ik} $$ $$\text{In each Column }l, \text{for any } ...
4
votes
1answer
179 views

Subgroups of $A_5$ have order at most $12$?

How does one prove that any proper subgroup of $A_5$ has order at most $12$? I have seen that there are $24$ $5$-cycles and $20$ $3$-cycles. What do the other members of $A_5$ look like?
1
vote
0answers
47 views

Cycle of length

I'm learning permutations and came upon this question which made me freeze. So to say it in my own words, it asks that how many permutations in $S_n$ do not have a cycle of length one in their ...
3
votes
1answer
175 views

Orders of centralizers $C_G(g)$ in a group of order 60?

Given a group $G$ of order 60 with 24 elements of order 5, 20 of order 3, and 15 of order 2, how do we find the sizes of centralisers of elements of $G$ without proving $G\simeq A_5$? By considering ...
1
vote
2answers
186 views

mixed permutations and combinations

I have a problem that I am not too sure of. In a team of 16, there are 5 couples and 6 single people. In how many ways can at most 1 couple be chosen if 6 people are required to represent the team at ...
0
votes
3answers
2k views

How many bit strings of length 17 contain at least 5 ones?

I'm a really confused as to how to start this question, would really appreciate any help you guys could give me!
0
votes
1answer
125 views

Determining Permutation/Combinations with Bit Strings

I've got a discrete math problem on my hands...I'm trying to understand the steps behind working with bit strings; specifically, how a bit string of x length has "at least" or "exactly" a certain ...
1
vote
1answer
266 views

Solving conjugacy equations in dihedral groups.

For all integers $m$ such that $0≤m<n$ find $a,b,c\in D_n$ such that $a(rR^m ) a^{-1}=R^2$ $b(rR^m ) b^{-1}=r$ $c(rR^m ) c^{-1}=rR$ $D_n$ is dihedral group of an $n$-gon represented by ...
5
votes
1answer
644 views

Why is $S_5$ generated by any combination of a transposition and a 5-cycle?

Why is $S_5$ generated by any combination of a transposition and a 5-cycle? Is this true for any prime $p$ (in this case $p=5$)?
4
votes
2answers
172 views

The Mathematics of Shuffling Poker Chips?

First, I must say that I do not have an advanced understanding of mathematics and I don't know what category this question belongs in. This is just a question that I have been thinking about recently. ...
1
vote
1answer
54 views

Permutation and combinations prob

there are $k$ different things and the task is to arrange them at $n$ places such that no adjacent things are of the same type and first and last things are of the same type. An example for: $k=3,n=4$ ...
2
votes
1answer
113 views

Permutation & Combination

There is a game in which there is a point P and k other points on a plane. To win, we must draw directed lines starting from point P and ending at point P with exactly n number of lines to be drawn. P ...
2
votes
2answers
342 views

Exponential generating function for permutations with descent set whose least element is even

Let $E(n)$ be the number of permutations $w\in S_n$ such that the least element of the set $Des(w)\cup \{n\}$ is even, where $Des(w)$ is the descent set of $w$. I need to find the exponential ...
2
votes
3answers
52 views

Computing $\langle (13746) \rangle$ in $S_7$.

How to list the elements of subgroup $\langle a \rangle$ in $S^7$ where $$a=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 2 & 7 & 6 & 5 & 1 &4 ...
1
vote
3answers
90 views

Restricted Permutations

I have a problem in which 4 music books, 5 education books and 2 medicine books need to be arranged on a shelf. In how many ways can this be done if only the music books must be kept together and all ...
6
votes
5answers
813 views

Simplify $\sum_{i=0}^n (i+1)\binom ni$

Simplifying this expression$$1\cdot\binom{n}{0}+ 2\cdot\binom{n}{1}+3\cdot\binom{n}{2}+ \cdots+(n+1)\cdot\binom{n}{n}= ?$$ $$\text{Hint: } \binom{n}{k}= \frac{n}{k}\cdot\binom{n-1}{k-1} $$
2
votes
2answers
595 views

Probability of having $k$ empty urns after putting $n$ balls into $n$ urns

Assume that there are $n$ balls (numbered from $1$ to $n$) and $n$ urns (numbered from $1$ to $n$). At the beginning no ball is placed in any urn. Balls are randomly thrown into urns: Each ball is ...
3
votes
1answer
92 views

Conjugation on subgroups of $A_4$ faithful?

Let $X$ be the set of all subgroups of $G=A_4$. We define the group action $$G\times X\ni(g,H)\mapsto gHg^{-1}\in X$$ I am trying to determine whether this action is faithful, i.e. $\bigcap_{H\in X} ...
0
votes
1answer
370 views

On Circular Permutations

In how many ways can 3 ladies and 3 gents be seated together at a round table so that any two and only two of the ladies sit together?
0
votes
1answer
88 views

Explanation of the 'division of $52$ cards' in four groups of $13$ problem?

I have been thinking about this problem, total possible combinations of division of $52$ cards deck in $4$ groups of $13$. I remember that the answer was ${52 \choose 13 }{39 \choose 13} {26 \choose ...
0
votes
1answer
87 views

Confusing combination-permutations question

In a shop there are five types of ice-creams available. A child buys six ice-creams. Is it true that the number of different ways the child can buy six ice creams is equal to the number of ...
1
vote
1answer
593 views

Restricted Permutations and Combinations

Tino, Colin, Candice, Derek, Esther, Mary and Ronald are famous artist. Starting next week, they will take turns to display their work and each artist's work will be on display at the London Show for ...
0
votes
2answers
127 views

Product of disjoint cycles question.

Consider the following permutations $x$ and $y$ in $S_6$: $x=(1 \, 3 \, 5)(2 \, 4)$ and $y=(2 \, 3 \, 4 \, 5)$ Express $xy$ as a product of disjoint cycles. My attempt: I first got $xy = (3 \, 5 \, ...
4
votes
2answers
333 views

How to determine the number of 5 consecutive digit blocks in a set of digits?

Let there be a set containing the following digits: {1,2,3,4,5,6,7,8,9}. If I choose 5 digit blocks, where the digits are arrange in consecutive ascending order, ...
0
votes
1answer
44 views

The letters A, E, I, P, Q, and R are arranged in a circle. Find the probability that at least 2 vowels are next to one another

This isn't homework, but could someone please give an explanation and answer to this question. Thanks! :D
0
votes
2answers
147 views

The letters A, E, I, P, Q, and R are arranged in a circle. Find the probability that at least 2 vowels are next to one another.

I've had trouble for his one for a while now. All help would be greatly appreciated. My attempt: Alright, since one letter is fixed, that leaves us with 5 letters to arrange. I'm going to fix the ...
1
vote
2answers
2k views

Cayley's Theorem - Discourse on Fraleigh's proof or Alternative Easier proof [duplicate]

I have hard time understanding Fraleigh's proof. Can someone either explain Fraleigh's or provide an alternative, perhaps easier proof? Thanks so much.
3
votes
2answers
211 views

Derangements property

It is not difficult to evaluate a formula for the number of derangements, with a simple combinatorical argument we get $D(n)=(n-1)(D(n-1)+D(n-2)), n\ge 3$ where $D(n)$ is the number of derangements. ...
9
votes
2answers
154 views

Cocktail bar problem

Recently I went out with friends and we asked ourselves the following question: Consider $n$ people sitting at a cocktail bar next to each other. How many rearrangements have to be made to ensure that ...
7
votes
0answers
191 views

Citation for subset complement result

Let $S = \{s_1, \ldots, s_n\} \subset \{1, \ldots, 2n\}$. Consider two operations on $S$, unfortunately both called complement in different setting: let $A(S) = \{1, \ldots, 2n\} \setminus S$ (set ...
1
vote
2answers
278 views

Permutations in Two Rows

I have been looking at linear and circular permutations. I have now come across a question that entails permutations in two rows. This is the question: Six natives and two foreigners are seated in a ...
0
votes
1answer
156 views

Anti-Symmetric Complex Polynomial

Let $f(x_1,...,x_n)$ be a complex polynomial. Show the following two conditions on $f$ are equivalent: i) for any transpositions $\tau$ we have $\tau.f=-f$ and ii) for any $\sigma \in S_n$ we have ...
6
votes
4answers
85 views

Permutations under Complex Numbers

The question stands: Let $S=\mathbb{C}-\{1,0\}$. Describe the subgroup of $\operatorname{Perm}(S)$ generated by the functions: $f:S\rightarrow S, z\mapsto 1-z$ and $g:S\rightarrow S, z\mapsto ...
1
vote
2answers
50 views

Why cannot the permutation $f^{-1}(1,2,3,5)f$ be even

Please help me to prove that if $f\in S_6$ be arbiotrary permutation so the permutation $f^{-1}(1,2,3,5)f$ cannot be an even permutation. I am sure there is a small thing I am missing it. Thank you.
4
votes
1answer
41 views

from product of swaps to product of disjoint cycles

I have permutation represented in this form: $X=(8,9)(14,15)(12,14)(13,15)$ Can I do the following steps? $$X=(8,9)(14,15)(12,14)(13,15)\\ =(8,9)(14,12,15)(13,15)\\ =(8,9)(15,13,14,12)$$ I think ...
3
votes
2answers
587 views

Calculating the power of permutations

I have this permutation $A$: $$ \left(\begin{array}{rrrrrrrrrr} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 10 & 8 & 5 & 2 & 3 & 1 & 6 & ...