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

learn more… | top users | synonyms (1)

3
votes
2answers
139 views

permutations confusion!

Hello this is my first post , I am reading a book called (probability for dummies) the answer in the book for the question below has confused me ... Suppose you have four friends named Jim , Arun , ...
2
votes
3answers
77 views

permutation & combinations

How many odd three digit numbers are there when tens digit is greater than units digit and hundreds digit is greater than tens digit? $225$ $ 45$ $ 50$ $230$ My attempt: The units digit can be ...
7
votes
1answer
54 views

Applications of the following theorem in the real world

We know that every permutation can be expressed as a product of transpositions ( cycles with length 2). As a class project I'm looking for the applications of this fact in the real world; especially ...
2
votes
3answers
46 views

Stochastic variable exercise: People between me and my friend.

This is the exercise: $n$ people are arraged randomly in a line (not a circle), among which are yourself and a friend. Call $Y$ the number of people that are between you and your friend. Show: $E[Y] ...
0
votes
1answer
24 views

Abstract Algebra Symmetric Groups

$$ \begin{align} \beta &= \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 3 & 8 & 7 & 6 & 5 & 2 & 4 \end{bmatrix} \\ &= ...
0
votes
0answers
33 views

Permutations with fixed points

I am trying to write a java program that counts permutations of a string, I would like to check my results by hand, but I can remember (or find) the formula to count the number of permutations, and ...
1
vote
0answers
60 views

List all possible subgroups of $A_4.$ Determine which subgroups of $A_4$ are normal.

I have a question which is List all possible subgroups of $A_4$. Determine which subgroups of $A_4$ are normal. Since $|A_4| = 12,$ the order of any proper subgroup of $A_4$ must be an element of ...
4
votes
1answer
42 views

Determine the number of ways for n couples to stand in a line so that no one stands beside his or partner (explanation for the answer)

I'm not quite sure if I'm understanding solution to following problem: "Determine the number of ways for n couples to stand in a line so that no one stands beside his or her partner." The general ...
1
vote
0answers
60 views

Find eight elements in S6 that commute with (12)(34)(56). Do they form a subgroup of S6?

I know the question has been asked and answered many times, but I am trying to shore up my understanding of this concept. Given the questions here and here, does this mean that I could rearrange the ...
1
vote
2answers
32 views

Interpretation of a Problem involving permutations

[USAMO 1999 submission, Titu Andreescu] Let $n$ be an odd integer greater than $1$. Find the number of permutations $p$ of the set $\{ 1, 2, …, n\}$ for which $$\def\x#1{\lvert p(#1)-#1\rvert} ...
4
votes
2answers
498 views

How many teams can be made from 11 people?

The question asks this: Five places exist on a team. $11$ total people. $6$ come from district A, $4$ from district B and $1$ from district C. How many different groups of five are there? How many ...
1
vote
2answers
31 views

Group theoretic construction for permutation algorithm

Consider a permutation $\sigma = [s_1, \ldots, s_n]$. The `contracting endpoints' construction for the subsequence $[s_i,\ldots, s_k]$ is given by iteratively taking the product of cycles given by the ...
1
vote
0answers
30 views

Equivalence relation among matrices

Consider the set of $p\times q$ matrices with entries from the set $S=\{1,\dots,s\}$. Say that two such matrices are equivalent if one can be transformed into the other by a series of operations of ...
0
votes
0answers
21 views

Finding Number Of Permutation Reverses

What is the easiest way to count the number of opposite order in permutation. meaning the total of elements in the permutation where $i<j$ and $\sigma_i>\sigma_j$ For example, $3142$, we have ...
0
votes
0answers
23 views

Permutation puzzler

Given a permutation on n letters, how many clues do you need to solve it? For example if the permutation is 31524, the clues come in the form of 5<4, meaning that 5 comes before 4. So, given a ...
0
votes
0answers
9 views

Reordering indexed expressions (combinatorics)

To me, it appears always as a little 'magic' when people reorder expressions, indexed by highly complex combinations of permutations and I would like to know in deep and formally what really is going ...
1
vote
0answers
36 views

Normalizer of a transitive subgroup in the symmetric group

Let $G$ be a finie group, and $H$ be a core-free subgroup of $G$ (that is to say, there is no nontrivial normal subgroup of $G$ contained in $H$). Denote by $\Omega$ the set of right cosets of $H$ in ...
2
votes
3answers
98 views

Expected value of number of sorted elements in a permutation

Consider the obvious algorithm for checking whether a list of integers is sorted: start at the beginning of the list, and scan along until we first find a successive pair of elements that is out of ...
2
votes
2answers
50 views

Permutations: A cycle is conjugate to its own inverse

I need help with d) here. Let $2 \le r \le n$ be two natural numbers. Assume that $\rho \in S_n$ is a permutation of the set $I_n=\{1,2,...,n\}$. Let $x_i \in I_n$ for $1 \le r$ be r different ...
0
votes
2answers
87 views

Are these two events independent?

Let n ≥ 3 be an integer, consider a uniformly random permutation of the set {1, 2, . . . , n}, and define the events ...
1
vote
1answer
24 views

How do you apply an element on the left of a permutation?

I am looking at the set $G=\{1,2,3\}$. I take the subgroup: $$H=\{(), (1,2)\} < S_G$$ I want to find $G/H$. I take the definition of $G/H$: $$\{1H, 2H, 3H\}$$ $$\{1\{(), (1,2)\}, 2\{(), ...
1
vote
1answer
31 views

How to calculate a pair of cards contains at least one ace?

A pair of cards are simultaneously drawn from a deck of 52 cards three times in a row. The drawn cards are returned to the deck. What is the probability that two of three pairs contain an ace? For ...
1
vote
1answer
69 views

How many ways there are to arrange 40 people to play exactly one match each? [duplicate]

A tennis club has 40 members. They host a tournament playing single (one verses one) matches. Every member of the club plays one match with another member of he club, so twenty matches are ...
1
vote
1answer
51 views

Nearest latin square

given a n x n matrix A with integer entries is there any way to find the nearest n x n latin square to it, say, e.g., in the Frobenius norm? I am looking for some type of convex optimization... ...
6
votes
2answers
281 views

Permutations to satisfy a challenging restriction

In a stack of n distinct cards in order {1,2,3,4,...,n} from top, define distance between 2 cards as the number of cards between them. 2 cards are neighbours if they're adjacent in original ...
4
votes
1answer
32 views

Find a subgroup of $S_{4}$ which is isomorphic to $\mathrm{Aut}(U_{8})$

The notation I am using is: $S_{4}$: the permutation group of order 4 $\mathrm{Aut}(U_{8})$: the set of all automorphisms on the set $U_{8}$ $U_{8}$: the group of numbers relatively prime to 8 I ...
9
votes
2answers
285 views

How many permutations of a multiset have a run of length k?

Background $\newcommand\ms[1]{\mathsf #1}\def\msP{\ms P}\def\msS{\ms S}\def\mfS{\mathfrak S}$Suppose I have $n$ marbles of $c$ colors, where $c≤n$. Let $n_i$ denote the number of marbles of color ...
1
vote
2answers
28 views

Arranging pictures possible combinations

I'm working on a problem which states there are 26 portraits of men and 4 of women. It wants to know how many ways can the photos be organized so no women are next to each other. I assume that the ...
1
vote
1answer
72 views

Dividing gems by random permutation

A group of people have found a treasure of gems: $G=90$ green and $B=990000$ blue. They decided to divide it among them. Since there are more people then gems, they decide to order themselves in a ...
1
vote
1answer
19 views

Group Theory - Permutations

If $B \in S_7$ and $|B^3| = 7$, prove that $|B|=7$. Solution: As $o(B^k) = o(B) / (o(B),k) $ Thus $|B| / (|B|,3) = 7$ Let $|B| = 7a$. Then $7a/(7a,3)$ should be $7a/a = 7$ or $(7a,3) = a$. As $3$ is ...
1
vote
1answer
51 views

Proof of 2^n deck of card, it will be reverse order performing n perfect in-shuffle.

I am now trying to prove performing n perfect in-shuffle with 2^n deck of card, and then it will be resulting reverse order. For example, Initial : [1, 2, 3, 4] 1st round : [3, 1, 4, 2] 2nd round : ...
0
votes
1answer
57 views

how many strings you can write with the letters abcd (permutation & combination or what?)

You have 4 letters abcd. How many 4-letter strings can you write with them? Assumptions: - the order is not important (aaab, abaa, baaa are same, counts 1) - you can use same letter more than once ...
2
votes
2answers
22 views

Permutations on a set with certain conditions.

Suppose we have a set $S=\{1,2,3,x,y\}$. There are $5!$ ways to rearrange the elements in the set, but I am confused about how to find the number of ways to rearrange the set given that $3$ comes ...
0
votes
3answers
40 views

How do I calculate the number of permutations of the list $(6, 6 ,5, 4)$?

I have the list $l = (6, 6, 5, 4)$ and want to how to calculate the possible number of permutations. By using brute force I know that there are 12 possible permutations: $$\{(6, 5, 6, 4), (6, 6, 5, ...
3
votes
1answer
67 views

$x^3=y^3=1, xyx=yxy$

The statement of the following problem from Artin's book is: Use the Todd-Coxeter algorithm to identify the number of elements in the group $G$ with the following defining relations: $x^3=y^3=1, ...
0
votes
3answers
40 views

Basic Permutation and Combinations practice quesiton

I am a novice at discrete mathematics and I have been working on trying to get my combinatorical skills up and i was working on some practice questions for permutation practice and i came across this ...
2
votes
1answer
131 views

Logic Pizza Toppings Ordering Question

So here's the question: The menu at a pizza place offers 14 possible toppings from 3 categories. Customers circle the toppings that they want on the order pad. (The order of circles or order of ...
4
votes
2answers
73 views

number of pairs formed from $2n$ people sitting in a circle

I am trying to understand the solution to the following problem: Suppose that $2n$ persons are sitting in a circle. In how many ways can they form $n$ pairs if no two adjacent persons can form a ...
0
votes
1answer
21 views

Probability : Container arrangement

There are a total of 15 containers out of which two containers have same color and the remaining are of different colors. The question is to find the probability that i) Two containers with same ...
1
vote
1answer
40 views

How should I continue my proof of this cycle property? (And did I make a mistake?)

I am trying to show: For a given single cycle, such as $(1, 4, 5, 7)$, the order of such a cycle is the length of the cycle. (i.e $(1, 4, 5, 7)^4 = ()$). I am trying to do this by induction. ...
1
vote
3answers
74 views

How to count permutations with cycles of length at least 51 in $S_{100}$?

Let consider permutation $ \in S_{100} $ How to count the number of permutations of those which contains a cycle of length 51 at least. ( so I would like a cycle of length 52,53,54,....,100)
0
votes
1answer
48 views

A simple question about permutations [closed]

So I could not find an answer anywhere, so here it is: If a string could be consisted of x y x y x y x y and x could only be used once, while y could be repeated, would it be correct to say that ...
0
votes
2answers
32 views

Combination and Permutation Math Problem

I am having some difficulty dissecting this problem and solving it: The track team has 7 girls and 6 boys. For the meet next week, they must choose a runner, a pole-vaulter, a captain and a ...
0
votes
1answer
34 views

Square labeled with same number.

Recently I met this combinatorics problem: "Let all points with integer coordinates in a plane be labeled with one of the numbers $1,2,3,...,n$. Prove that there is a rectangle whose vertices are ...
0
votes
2answers
32 views

How to maximize sum of pairwise multiplication of array elements taken one from each array?

Suppose you are given two arrays: $$a = [a_1,a_2,a_3,\dots,a_n],\hspace{5mm} b = [b_1,b_2,b_3,\dots,b_n]$$ Now you need to take one element from $a$ and one from $b$ multiply it, and add to sum and ...
0
votes
0answers
23 views

Form of an element of a normal subgroup of $A_n$

I want to show that $A_n$ is simple for $n\geq 5$. For $n=5$ I have used the following criterion Let $H$ be a normal subgroup of $A_5$ then $H$ can contain any one of the following $a.$ a $5$ ...
0
votes
0answers
57 views

Possible combinations of N different balls in M identical bins with the same capacity L

For a distribution center I am interested in the number of possible combinations to put N different boxes (all the same size but different content) into M equal bins (containers) with capacity L, with ...
0
votes
1answer
73 views

How many different permutations?

Suppose I've n boxes and m different colored balls of different quantities.How many unique permutations can be obtained ? Example : n=2,m=2, with quantities ( A - 1 ball, B - 2 balls) Thus the ...
0
votes
0answers
31 views

What is sgn(321)?

I've tried to compute the length of (321) and I got 2. Then the sgn should be (-1)^2=1. But I suppose sgn(321)=-1 by the definition in the graph?
2
votes
0answers
32 views

Please check my solution of a problem in combinatorics regarding partitions

A lift automatically operated has a further computer facility of recording how many people leave the lift at each floor. It starts at floor $1$ and goes up to floor $6$. If $8$ people consisting of ...