Questions tagged [permutations]
For questions related to permutations, which can be viewed as re-ordering a collection of objects.
8,374 questions
0
votes
1answer
16 views
Number of permutations differing in at least $d$ spots in pairwise comparisons
A friend and I were thinking about this problem today but we were unable to come up with a solution.
Problem:
Consider the the numbers $S=\{1,\ldots,n\}$. Given
$2\le d \le n$ what is the ...
0
votes
0answers
6 views
Generating combinations using a butterfly network
I'm using a butterfly network to generate a random combination of a bitstring of length $n$ and weight $w$. Let me clarify it with an example. Suppose I want a random bitstring of length 8 and Hamming ...
0
votes
0answers
9 views
Definition of the rank of $x_t$ among $(x_1,…,x_T)$
I recently came across the following statement, but I don't understand how to implement it:
Let ${x_1,...,x_T}$ be $T$ i.i.d observations of first differences of
a variable $x_t$, and let $r(x)$ ...
2
votes
0answers
45 views
5 digits numbers such that when the sum of digits divided by 4 leaves remainder 2.
How many 5 digits numbers such that when the sum of digit divided by 4 leaves remainder 2.
Example:-
Consider a 5 digit number-
(x1,x2,x3,x4,x5)
Then (x1+x2+x3+x4+x5)= must be of form(4n+2)
I tried ...
3
votes
0answers
29 views
Odds of two runners ending up with the same average rank across multiple races?
Imagine a race with $n$ runners, all equally skilled so that the outcome is just based on luck. If the race is run $m$ times, what are the chances that two runners end up with the same exact average ...
1
vote
1answer
13 views
Permutation and Combination in probability question - Choose team members
I would like to have your help and explanation on following question.
For an 8-a-side football match, a coach has to choose the team from a squad of 12 boys. Only three of them can play as a ...
1
vote
1answer
29 views
Number of determinant formed by using non zero a,b
Two non zero distinct numbers a and b are as used elements to make determinants of the third order. The number of determinant whose value is zero for all a,b is:-
my attmept:
Determinant of a 3x3 ...
0
votes
0answers
26 views
Necessary and sufficient conditions that $\langle \zeta, (ij), \lvert\lvert k\, \ell \rvert\rvert, \xi_M\rangle$ generates $\mathscr{P}_n.$
Throughout I use cycle notation and write maps $m:X\to Y$ on the right of their arguments (e.g. $xm=y$ for $m(x)=y$).
Let $\zeta=(12\dots n)$.
This question is inspired by the following questions:
...
0
votes
0answers
23 views
the number of ways to change an element in the permutation cycles from outside those cycles
I've been thinking about this issue for a while! For the set of $n$ elements, consider that there is a permutation over the whole set $\{1,\dots, n\}$ where $n-k$ elements are fixed. A way of ...
1
vote
1answer
19 views
Composition of permutations in cycle notation
For $p=(1\ 4\ 3\ 2)$, find $p^2$. The textbook states that the solution is $p^2=(1\ 3)(2\ 4)$.
Now I understand that $1 \mapsto 4 \mapsto 3$, and $2 \mapsto 1 \mapsto 4$, however, why must the result ...
0
votes
0answers
31 views
Ways in which a knight can reach the diagonally opposite corner
A knight is placed in a corner of an $8\times8$ chessboard. In how many different ways can this knight reach the diagonally opposite corner if it can not move on the same cell more than once?
0
votes
0answers
17 views
What are the patterns for these decompositions of permutations into transpositions?
By looking at answers on this site, in order to decompose a permutation into transpositions, so far I have seen 3 patterns as follows:
(12345)=(15)(14)(13)(12)
(12345)=(12)(23)(34)(45)
(12)=(21) ...
1
vote
1answer
36 views
counting number of strings with at least one consonant
The English alphabet contains $21$ consonants and $5$ vowels. How many strings of $7$ lowercase letters of the English alphabet
(repeats allowed) contain:
(a) exactly one consonant
(b) exactly two ...
1
vote
0answers
43 views
How to combine shuffles to prove associativity of Eilenberg-Zilber map
I've got a problem related to $(p,q)$-shuffles that comes from the Eilenberg-Zilber map $\nabla$ when I tried to show that this map is associative in the sense that $\nabla(\nabla\otimes 1)=\nabla(1\...
0
votes
0answers
13 views
Permutation and combination when certain objects are alike.
What will be the number of permutations and combinations when m objects are to be taken from a group of n objects, having 'a' and 'b' number similar objects?
Example: Find number of ways of ...
2
votes
1answer
29 views
Using wreath products to find stabilisers of a partition of a set
I have the following example, that uses the wreath product to find the stabilisers of a partition. I don't understand how the wreath product does this though. I can recite the definition of a wreath ...
1
vote
1answer
36 views
How many way can you encode a five letter word
I have a solution for this problem, but the way iv carried it out seem a bit long and am wondering if and only if my ans is correct if there is a shorter method or maybe and alternate way of looking ...
2
votes
1answer
26 views
Normal subgroup with index that divides n!
Is this argument valid?
If $G$ is a finite group with $n$ Sylow $p$-subgroups (in particular $n = 1$ mod $p$ and $n$ divides $|G|$), then $G$ permutes them acting by conjugation. Therefore there is a ...
2
votes
3answers
42 views
Getting a wrong answer on evaluating permutations separately
Good Day!
I was doing some combinatorics problems when I got stuck.
The problem was:
Suppose that a teacher selects 4 students from 5 boys and 4 girls. If at least one boy and one girl must be ...
0
votes
2answers
24 views
Arranging $3$ books on $3$ shelves so that there are $2$ books on one shelf and $1$ book on another shelf
We have $3$ books and $3$ shelves. We are to put $2$ books on $1$ shelf and $1$ book on the other two.
Answer given in the book is $6$ but I feel that——
We can select $2$ books from $3$ in $C_{(3,2)}=...
2
votes
2answers
50 views
Conditions when a permutation matrix is symmetric
I am now playing with permutation matrices, http://mathworld.wolfram.com/PermutationMatrix.html.
Also, there is a similar discussion: Symmetric Permutation Matrix.
I want to ask more details than ...
0
votes
1answer
17 views
How can I choose the highest resulting combination out of arbitrary sized chunks, worth an arbitrary amount each
I am given a set of companies that each want to buy my product in different sized chunks. I have a maximum of 28 Million units to sell and each company pays a different amount of money for their order....
2
votes
1answer
35 views
how to check if there is an automorphism mapping between two conjugacy class
Let $G\le S_n$ be a permutation group and suppose that $C_1,C_2$ are two distinct conjugacy classes that have the same cardinality and is represented by a permutation of the same cycle-type. My ...
-2
votes
1answer
32 views
Calculating number of non-duplicated permutation
I want to calculate the number of permutation from duplicated list.
Example) There is a list combined of 76 icons.
Here is icon list
A: 1
B: 3
C: 5
D: 6
E: 6
F: 5
G: 10
H: 9
I: 8
J: 7
K: 6
L: 10
...
1
vote
1answer
23 views
Decompose permutation $σ=(123)(345)(4567).$
i'm getting confused at how to decompose this permutation
I've seen this post about how to decompose How to decompose permutations?
I understood and managed to apply to other kind of permutation but ...
0
votes
0answers
26 views
There is a group of 4 married couples. What is the number of the groups of 4 people in which there is at least 1 married couple? [closed]
There is a group of 4 married couples.
What is the number of the groups that consist of 4 people in which there is at least 1 married couple?
0
votes
1answer
24 views
In how many different ways can 7 people sit around 2 round tables , one of which has 3 and the other has 4 seats?
In how many different ways can 7 people sit around 2 round tables , one of which has 3 and the other has 4 seats?
The answer to the question is 460
-4
votes
1answer
48 views
I am stuck in this question please help. [closed]
The number of ways in which an examiner can assign 30 marks to 8 questions, giving not less than 2 marks to any question is
A) $ 21 \choose 7$
B) $ 21 \choose 8$
C) $ 21 \choose 9$
...
0
votes
0answers
11 views
Perturbation Bound for Left Singular Matrix
Let $A$ and $\hat{A}$ be two $N\times N$ matrix with rank r, let $A=\hat{A}+H$ where $H$ is some perturbation. Suppose $A$ and $\hat{A}$ have following SVD:
\begin{align}
A&=U\Sigma V^T\\
\hat{A}&...
1
vote
2answers
54 views
How do I solve this combinatorics problem with conditions?
I have $N$ lattice points which are arranged linearly and equally spaced. I want to make connections(say with some wire or thread) with each lattice site with another. The first one has $N-1$ ...
1
vote
2answers
14 views
Subset of combinations in larger set
I am a biologist and not a real mathematician. Hence some of the answers featured here are sometimes too complicated.
My question is:
I have set of 8 genes named PBX1,ESX1,PIM1,HBB,HBG,BCL11A,KLF4,...
0
votes
0answers
20 views
Conjugacy classes of some involutions
$\newcommand\Cl{\mathrm{Cl}}$Assume that $G$ is a finite permutation group with degree 2n (i.e. acting on {1,...,2n}). Suppose now that I have two fixpoint free involution $g_1,g_2\in G$. So if I ...
0
votes
1answer
29 views
Lucky draw Permutation or Combination
I need help with a question, I have no idea where to start. If someone can help me solve it, and explain it at the same time that would be great. Here it is:
In a lucky draw, there are 20 names in a ...
0
votes
1answer
31 views
How many bytes contain exactly two 1s?
I know the answer is $C(8,2)$, but I was confused as to why the answer wouldn't be $P(8,2)$? Doesn't the order of the 0s and 1s matter? For example: 10010000 is different than 10100000, so don't we ...
0
votes
2answers
13 views
Combination or Permutation math question help
I need help with a question. I have absolutely no idea how to do this, can someone please explain how to solve this problem:
A committee of 8 workers is formed selecting from a group of 6 men and 5 ...
0
votes
2answers
28 views
Determining the power of permutation matrix of order $N\times N$ to get identity matrix.
This particular 6x6 permutation matrix is P
$$ P = \begin{pmatrix}
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 0 \\
...
1
vote
1answer
23 views
Order of permutation $a \in S_n$ if $a^k$ is a cycle of length n
Let $a$ be an element of $S_n$ ,the permutation group of order n. $a^k$ is a cycle of length n. Then what is the order of $a$?
If $n$ is prime then a should be a cycle of length $n$.But if $n$ is not ...
0
votes
1answer
23 views
Arranging Letters and Plus Signs
We have 4 spaces which should be filled with $1$ letter and $3$ plus signs, $2$ letters and $2$ plus signs, or with $3$ letters and $1$ plus sign. In any of these cases, letters can not be repeated ...
0
votes
3answers
55 views
Permutation or Combination help [closed]
Am I wrong in using 6! -1 For this problem:
An iPhone password is a 6-digit number. How many different possible passwords are there if each number can only be used once, and 0 cannot be in the first ...
-1
votes
0answers
18 views
How many unique ways to put H rings of k colors of n numbers (of each color) from a pile of r rings on m fingers? [closed]
Is there a formula?
e.g.
Let’s say you have 100 rings:
green: 10
blue: 30
yellow: 42
red: 11
black: 7
how many ways can you put 35 of them on 5 fingers? (order matters)
6
votes
1answer
75 views
+50
Why is the permutohedron simple?
I am working with the permutohedron in $\mathbb{R}^n$ which is defined as the convex hull of $n!$ vectors as follows:
$$\Pi_n := conv\{(\sigma(1), \ldots, \sigma(n))\ |\ \sigma \text{ permutation of }...
1
vote
1answer
26 views
number of ways to order 5 english and 4 french hits
the question is as follows: suppose a dj has 5 english hits and 4 french hits.
in how many ways can these songs be played if no two english hits should follow each other?
in how many ways can these ...
0
votes
1answer
23 views
Possible ways to sort elements of set so that all elements of type x are next to each other.
We have a set $A=\{a_1, a_2, ..., a_{2n}\}$ such that $|A|=2n$. We have subsets of $A$, $G = \{a_1, a_2, ..., a_n\}$, $B=\{a_{n+1}, a_{n+2}, ..., a_{2n}\}$. For the sake of this example, lets say $A$ ...
1
vote
1answer
50 views
Number of $7$-digit telephone numbers with non-decreasing digits? strictly increasing digits? [duplicate]
I'm really confused with the question below.
A phone number is a 7-digit sequence that does not start with 0.
(a) Call a phone number lucky if its digits are in non-decreasing order. For example, ...
1
vote
0answers
29 views
Permutation graph and the number of inversion statistics
Let $K_m$ be the number of m-cliques, $m \in N$, in a random permutation graph $G_n$ with $n$ vertices and $\pi_n$ is the corresponding permutation representation in $S_n$.
I am looking for a basic ...
2
votes
2answers
43 views
Number of different necklaces with $2$ black and $6$ white beads
This is not a home work question, I'm preparing for an entrance test.
The number of different necklaces you can form with $2$ black and $6$ white beads is?
My approach: We can place the white ...
0
votes
0answers
18 views
A concrete example to show that every permutation representation is reducible.
I was reading this definition of permutation representation:
but I do not understand what is this nontrivial subrepresentation that every permutation representation has is it $e_{x_{1}}+e_{x_{2}}+ ......
0
votes
1answer
36 views
If $f^{-1}(j)\leq f(j)$ for all $j$ then $f=f^{-1}$
Let $f$ denote the bijective map from $I=\{1,2,3,4,5\}$ to $I$. If $f^{-1}(j)\leq f(j)$ for all $j$, then $f=f^{-1}$.
I have solved the problem using induction. I was wondering if there are some ...
0
votes
2answers
19 views
How many different words can be formed in which neither two consonants nor two vowels can come next to each other? [closed]
There are 6 letters of which 3 are consonant and 3 are vowels. How many different words can be formed in which neither two consonants nor two vowels can come next to each other?
-2
votes
2answers
41 views
In how many ways can $8$ lions be fed with $3$ goats, $3$ rabbits and $2$ lambs? [closed]
The options are $70$, $210$, $560$ and $580$.
