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
49 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
31 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
485 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
30 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
29 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
34 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
95 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
45 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
85 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
28 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
68 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
48 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
271 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
271 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
23 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 ...
0
votes
1answer
40 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
37 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
61 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
39 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
94 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
62 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
16 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
70 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
25 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
26 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
20 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
46 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
70 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
28 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
31 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 ...
4
votes
1answer
38 views

Permutation question of arranging people in a row

There are $6$ boys and $4$ girls in a class. How many ways are there to arrange them in a row if no girl stands next to each other? I would know how to solve this if there are only $2$ girls. But ...
0
votes
1answer
21 views

Probability distribution of number of ordered items in a permutation

I have a simple algorithm to check if a series of numbers is sorted: if the first two numbers are sorted, move to the next two. Else, stop and return false. I want to figure out the average case ...
3
votes
1answer
71 views

To determine number of arrangements of 4 letters in a word so that the transitions remains conserved

A 10 letter word is composed of $A,\ B,\ C,\ D$. The problem is to find the number of arrangements of these alphabets which could lead to fixed number of transitions between each pair of alphabets. ...
-2
votes
1answer
25 views

How do you do this permutation? [closed]

How would you do this math problem? and how do you know to use the equation you use? Mendy’s offers three types of bread: White, Whole-Wheat and Rye. The choices of meat are corned beef, pastrami, ...
1
vote
3answers
44 views

Subgroups of a permutation group

The permutation group $S_{4}$ is defined as the group of all possible permutations of [1234]. i) Find the number of subgroups of $S_{4}$ that have order 2. ii) A: { [1234], [2143], [3412], [4321] } ...
2
votes
3answers
110 views

prove that $\binom{n}{0}^2+\binom{n}{1}^2+\binom{n}{2}^2+\cdots+\binom{n}{n}^2=\binom{2n}{n}$ [duplicate]

How can i prove that : $$\binom{n}{0}^2+\binom{n}{1}^2+\binom{n}{2}^2+\cdots+\binom{n}{n}^2=\binom{2n}{n}$$ i tried to prove it : by $$\binom{2n}{n} = \frac{(2n)!}{n!n!} = \frac{2^n ...
3
votes
2answers
57 views

How to prove this equality for Stirling numbers?

How can I prove that the following formula is true for Stirling numbers of first kind. $$\sum_{k=1}^n(-1)^k\left[\begin{matrix} n\\k\end{matrix}\right] =0$$ Actually I want to prove that number of ...
0
votes
0answers
16 views

Counting with permutations and counting ignoring permutations

I am given this problem: This problem was given to me in my computer science class but it has to do with permutation and I want to understand it mathematically first. let $c(n)$ be the number of ...
0
votes
1answer
67 views

Four Letter-envelop problem

A secretary writes four letters and the corresponding addresses on envelopes. If he inserts the letters in the envelopes at random irrespective of the addresses, (i) find the probability that only one ...