Questions tagged [permutations]
For questions related to permutations, which can be viewed as re-ordering a collection of objects.
12,848
questions
-2
votes
0
answers
21
views
Sum of combination of items without repetition
Consider we have $A,B,C$.
What is the formula in combinatorics to get the value of 15 we have here for this special example:
$\{A,B,C,AB,AC,BC,BA,CA,CB,ABC,BCA,CBA,BAC,ACB,CAB\}$
but in the general ...
1
vote
2
answers
76
views
How many permutations are possible in a 10 digit number containing 2 and 5 such that no two 2's are together
How many ten digits whole number satisfy the following property they have 2 and 5 as digits, and there are no consecutive 2's in the number (ie. any two 2's are separated by at least one 5).
So I know ...
4
votes
1
answer
89
views
Is $S_5$ generated by (1 3) and (1 2 3 4 5)? [duplicate]
I proved that $S_4$ is not generated by $(1 \ 3)$ and $(1 \ 2 \ 3 \ 4)$, using that the partition $A = \{ \{ 1, 3 \}, \{ 2, 4 \} \}$ is invariant under the action of the elements of $\left \langle (1 \...
7
votes
1
answer
177
views
+150
In an art museum, there are $n$ paintings, $n \ge 33$, ...
In an art museum, there are $n$ paintings, $n \ge 33$, for which there are
used a total of $15$ different colors so that any two paintings have at least one common color and there are no two paintings ...
0
votes
1
answer
43
views
Standard notation for permutations
I have a question about the standard notation for representing properties of permutations. This is best illustrated with a concrete example: let's take a permutation on 6 elements with cycle ...
1
vote
1
answer
44
views
Structure of Hermitian matrices that commutes with all permutation of subsystems?
Denote the set $\mathcal S$ all Hermitian matrices act on $\mathbb{C}^d\otimes \mathbb{C}^d\otimes\mathbb{C}^d$. If for any $H\in\mathcal S$, we have $H$ is invariant under the permutation of ...
1
vote
2
answers
45
views
Handling Excess People with Indistinguishable Chairs in Circular Arrangements
I'm grappling with a problem involving seating arrangements in a room that features two circles of chairs. One circle consists of 11 chairs, and the other has 7, making a total of 18 chairs. The twist ...
-4
votes
0
answers
30
views
Seating arrangements at Round Table Meeting [closed]
I am Organizing a round table meeting of a business association with 5 tables and 6 persons to each table. How do I swap participants in each table 5 times to have different people sit each of the ...
0
votes
0
answers
36
views
Functions which commute with incomparable elements
I have a claim that I believe to be true, but am not sure how to prove it.
Suppose I have a (strict) partially ordered set $(A, <)$ and some other set $B$ and a function $f : A \times B \to B$ such ...
0
votes
0
answers
26
views
Orbits of a $GL_{n}×GL_{n}×M_{n}(F)$ action group
There's an exercise on Permutations Groups of Dixon:
Let $\Omega$ be the set of all $n × n $ matrices over a field $F$ and let $G = GL_{n}(F) × GL_{n}(F)$ where $GL_{n}(F)$ is the group of all $n × n$ ...
8
votes
1
answer
146
views
Well-mixed permutations
A permutation $\phi:\{1,2, \ldots, n\} \rightarrow\{1,2, \ldots, n\}$ is called a well-mixed if $\phi(\{1,2, \ldots, k\}) \neq\{1,2, \ldots, k\}$ for each $k<n$.
What is the number of well-mixed ...
0
votes
0
answers
28
views
Permutations of divisors in some interval of composite integers
At this answer it is provided an interval of the form $[kn,(k+1)n]$ where each integer is divisible by at least one of the integers of the interval $[2,n]$.
We define a permutation of the integers of ...
0
votes
0
answers
34
views
Permutations with Limited Repetitions in a 12-Letter Word Formation [closed]
I recently encountered an interesting combinatorial problem and wanted to share my approach to solving it, hoping to verify its correctness and understand any potential missteps in my reasoning.
The ...
-1
votes
0
answers
27
views
Proof that the number of involutions in $S_n$ is odd. [duplicate]
We know that an involution is any permutation $\pi$ such that $\pi^2=id$.
We also know that the number of involutions of $S_n$ will be the number of permutations $\pi\in S_n$ such that $\pi$ has order ...
0
votes
0
answers
14
views
Decomposing Signed Permutations
Please, how do I decompose a signed permutation into simple transpositions? I need a concrete example to do this. I represented the signed permutation 3 -4 -1 2 in its cycle form (1 3 - 1 3) (2 -4 -2 ...
0
votes
0
answers
18
views
Finding an algorithm that goes through all the possible permutations of a set only by swapping 2 elements
I recently came across a problem when trying to deal with a set of numbers with n elements.
The problem is as follows:
Starting with a set of n distinct elements, how would one generalize a unique ...
2
votes
2
answers
284
views
How to compensate for overcount?
Task: Find the number of ways to distribute 10 customers (distinguishable) to 7 salesmen (dist.) with each having at least 1 customer.
Attempt: We first pick 7 customers (unordered: $C(10,7)$) and ...
1
vote
1
answer
33
views
How many subgraphs of $K_{9,9}$ are isomorphs of $C_6$?
I approached this problem the following (apparently incorrect) way:
In $K_{9,9}$, there are 18 vertices, so 18 choices for a starting point. From there, since the graph is bipartite, whichever "...
-3
votes
0
answers
21
views
No two vowles are together in Bengali [closed]
The number of arrangements of the letters of the word E-A-M-C-E-T so that no two vowels are together is.
-2
votes
0
answers
64
views
In how many ways can 3 prizes be distributed among 5 people such that each one gets at least one prize? [closed]
In how many ways can 3 prizes be distributed among 5 persons such that each one gets at least one prize?
This is how I solved using the permutation:
We need to calculate the event when one student ...
1
vote
2
answers
86
views
Counting arrangements of seven people standing in a row of $3$ and a row of $4$, with $A$ and $B$ together, and with $A$ and $C$ separated
Seven people are standing in two rows, with three people in the front row and four in the back row. Among them, A and B must stand next to each other, while A and C must stand separately. How many ...
3
votes
1
answer
86
views
Is there a permutation $\sigma(n)$ of $\{0,1,2,\ldots,m-1\},$ such that $\{(n+\sigma(n))\pmod m:0\leq n\leq m-1\}=\{0,1,2,\ldots m-1\}?$
Given $m\in\mathbb{N},$ is there a permutation $\sigma(n)$ of
$\{0,1,2,\ldots,m-1\},$ such that $\{ (n+\sigma(n))\pmod m: 0\leq n
\leq m-1 \} = \{0,1,2,\ldots m-1\},\ ?$
Based on computation with ...
5
votes
1
answer
71
views
How many different totals can be obtained in a test with $20$ questions if one can obtain $-1$, $0$, or $4$ for a question?
In an exam there are $20$ questions, one can obtain either $-1,0$ or $4$ in each question based on marking scheme. How many different totals can he obtained in the test?
One thing I observed different ...
3
votes
2
answers
75
views
Show that a transitive subgroup of symmetric group is primitive
I am working on this exercise 1.5.7 of Dixon-Mortimer Permutation Groups: Let $G \leqslant \mathrm{Sym}(\Omega)$ be a transitive group and let $\Gamma$ and $\Delta$ be finite subsets of $\Omega$. ...
0
votes
0
answers
20
views
Minimal paths in a network [duplicate]
I have the matrix in the image for a
reference.
I can't understand why using combinations work on finding all the minimal paths.
(In the image, I go from bottom-left to top-right).
For the first ...
1
vote
2
answers
44
views
Bijection between permutations of even length cycles and pairs of factors
I was trying to solve Exercise 3.13.15 in Cameron's Combinatorics: Topics, Techniques, Algorithms. It goes like this:
(a) Let $n = 2k$ be even, and $X$ a set of $n$ elements. Define a factor to be
a ...
0
votes
0
answers
75
views
Let $A$ be a $4\times 4$ diagonal matrix whose entries are complex numbers such that $A^4=I$. If the trace of $A$ is zero then which is\are correct
Let $A$ be a $4\times 4$ diagonal matrix whose entries are complex numbers such that $A^4=I$. If the trace of $A$ is zero then which is\are correct ($I$ is unit matrix)
(A) There are $36$ distinct ...
1
vote
1
answer
36
views
Summing a binomial series that arose while counting functions
Define $f:A \to A$ where $A$ contains $n$ distinct elements. How many functions exist such that $ \forall x \in A, f^m(x)=x$, $(m<n)$ (and $m$ is prime to avoid the mistake pointed out in the ...
0
votes
0
answers
48
views
Is the number of elements of $S_n\wr S_m$ with cycle-type $\lambda$ known? [closed]
I wonder if a formula for the number of elements in $S_n\wr S_m$ with cycle type $\lambda$ is known? Cycle type of elements of $S_n\wr S_m$ is the cycle type by the natural embedding $S_n\wr S_m \to ...
1
vote
0
answers
37
views
Permutations and partial orders
Consider the set of all permutations of $n$ numbers $\mathfrak{S}(n)$. Each permutation can be seen as a total ordering relation of $n$ elements $a_1,...,a_n$, such that
\begin{equation}
a_{\pi(1)}<...
5
votes
2
answers
110
views
"Encode" all $n$-permutations with the fewest number of swaps
The goal is to find $m$ swaps $s_1, s_2, \dots, s_m$ such that any $n$-permutation can be encoded as a binary sequence of length $m$, $x_1, x_2, \dots, x_m$, where $x_i$ indicates whether to perform ...
-1
votes
1
answer
65
views
For $k$-cycle $(1, 2, ..., k)$, do the elements in it need to be taken in order? [closed]
For $k$-cycle $(1, 2, ..., k)$, do the elements in it need to be taken in order?
Is $(3,1,5,2,4)$ a $5$-cycle? Or the elements in the rotation must satisfy a law of order? i.e. $5$-cycle just are $(1,...
-2
votes
1
answer
66
views
Find the number of ways to express 3600 as a product of three factors(triplets) [closed]
Ok so I came upon this question, and I have absolutely no idea how do we proceed.
I had done a similar kind of question which was :-
Find the number of ways to express 12 as a product of 2 factors
...
0
votes
0
answers
24
views
Combinations problem about multiset. Multiple ways.
Determine the number of 6-combinations of multiset s = {3·a, 4·b, 5·c}
I can solve this problem by inclusion-exclusion principle, but is there any more clever way ...
1
vote
0
answers
40
views
How many $7$-digits number can be formed by using $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$ such that it is divisible by $3$? Repetition not allowed [duplicate]
The question is:
How many $7$-digits number can be formed by using $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$ such that it is divisible by $3$? Repetition is not allowed.
I have done a similar ...
0
votes
0
answers
33
views
Numbers of combination of groups
I have 120 people and groups of 6 people and i want to know the probability that I am in the same group as a specific person (call him x)?
I’m little confused about the usage of the binomial and how ...
5
votes
0
answers
51
views
In how many ways can numbers $ \in \{1, 2, ..., 3n \}$ be arranged in such way that the sum of every $3$ consecutive numbers is divisible by $3$?
In how many ways can the numbers from the set $ \{1, 2, ..., 3n \}$ be arranged in a sequence such that the sum of every three consecutive numbers is divisible by $3$?
Solution:
All the numbers from ...
1
vote
1
answer
40
views
Showing an element of a permutation raised to a specific power is equal to the permutation
Here's my permutation:
$\sigma = \left( \begin{array}{ccccccccccccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\
7 & 4 & 2 & 5 &...
1
vote
1
answer
82
views
A subgroup of $S_6$.
Show that the set of permutations $\{\sigma \mid \sigma(i)\le i \text{ for }1\le i\le 6 \}$ is a subgroup of $S_6$.
I am stuck at how I am supposed to reason about this question. I'd assume I'd first ...
1
vote
1
answer
64
views
How many different ways can the 19 people be split across 3 cars such that no two cars have the same number of people?
There are 19 people who are riding a rollercoaster and each time the rollercoaster runs with all 19 people they are organized differently among the 3 separate cars on the track. Each car can carry ...
0
votes
0
answers
21
views
Injective Homomorphism from $GL_2(\mathbb{F}_5)$ to $\mathcal{S}_n$: Determining the Smallest $n$ [duplicate]
Let $ \text{GL}_2(\mathbb{F}_5) $ denote the group of $2 \times 2$ invertible matrices over $ \mathbb{F}_5 $, and $ \mathcal{S}_n $ represent the group of permutations of $ n $ objects. Determine the ...
-3
votes
1
answer
66
views
In $\sigma (12)\sigma ^{-1}=\left(\sigma (1)\sigma (2)\right)=(23)$, why $\left(\sigma (1)\sigma (2)\right)=(23)$?
This is a proof of a formula in a math class. There are some parts that I don't quite understand, so I would like to ask for some clarification.
In $\sigma (12)\sigma ^{-1}=\left(\sigma (1)\sigma (2)\...
0
votes
1
answer
43
views
Unique ways to arrange people in seats. 4 people, 5 seats
Say that I have 4 people and 5 seats. How many unique ways are there of arranging these 4 people into the five seats?
In questions like this I would use this formula:
$$\frac{n!}{(n-k)!}$$
However ...
5
votes
1
answer
395
views
Is there a permutation of a given length in which every element divides sum of the elements before it?
For given positive integer $n$, is it possible to construct a permutation $p$ of [1, n], such that for each $k$ in
[2, n], $p_k$ divides $p_1 + p_2 + ... + p_{k-1}$.
Solutions for small $n$:
$n=3$, p ...
1
vote
0
answers
67
views
Mastermind guessing
I'm reading this problem and I can understand how they got the output for the first four test cases. But the last one I can't really arrive at it. Is there some mathematical concept that I can apply ...
0
votes
1
answer
71
views
Theater Seating Combinatorics Problem: 6 friends go to the movies and sit in adjoining seats in one row
The theater is configured so that in any row there is a wall, 6 seats, an aisle, 6 more seats, and then a wall. In total there are 2* 6! arrangements = 1440.
"How many ways can they sit if Jane ...
1
vote
1
answer
98
views
Which permutations commute with each other?
Two bijections from a finite set to itself commute with each other when they are both powers of one bijection. They also commute with each other when their cycles do not intersect each other.
But some ...
-3
votes
1
answer
79
views
Determine the mapping related to a machine which shuffles cards [closed]
A friend of mine told me about this problem.
Given a indexed sequence of 13 cards from Ace to King, there is a machine which shuffles them and gives a certain (indexed) output sequence. Now inserting ...
2
votes
1
answer
58
views
Prove that $\alpha(r+s+1,r)=\alpha(r+s+1,s)$
I am reading a paper
I am having difficulty understanding this part, which is why I posted it on this forum to discuss with you
Let me recall some definitions:
Let $\pi = \left(a_1,a_2,\ldots a_n\...
3
votes
1
answer
56
views
Coloring of a 4-sided figure with three colors [closed]
I attached the image below for reference. I am trying to color the figure using three colors and find the number of distinguishable colorings.
The long sides of the figure are one side and not two ...