Questions tagged [permutations]
For questions related to permutations, which can be viewed as re-ordering a collection of objects.
12,315
questions
0
votes
0
answers
9
views
Number of ways of distributing 75 identical objects into 4 boxes such that each box contains at least 15 objects.
There are 75 distinguishable objects, to be distributed into 4 distinguishable boxes.
In how many ways can they be distributed such that each box contain at least 15 objects.
Is there way to solve ...
1
vote
2
answers
21
views
Probability - Choosing two numbers from {1,2,3,4,5,6} such that one is lesser than 4
Two numbers are selected randomly from the set S = {1, 2, 3, 4, 5, 6} without
replacement one by one. The probability that minimum of the two numbers is
less than 4, is?
The correct method to solve ...
- 13
0
votes
0
answers
34
views
What is the largest order of an element in the group of permutations of $n$ objects?
I have a very little knowledge in abstract algebra and want to know what does the problem actually mean.
I encountered this question in the official test
$\text{Graduate Record Examination - Math ...
- 4,547
0
votes
1
answer
29
views
how many (5,4,3,2,1)-tables are there?
A (5,4,3,2,1)-table is an arrangement of the integers 1 through 15 with five numbers in the top row, four in the next, three in the next, two in the next, and one in the last, such that each row and ...
- 1,921
1
vote
0
answers
15
views
Permutation of repeated items in fixed capacity buckets
The following question is asked in hashing
There are 100000 buckets and each bucket has a capacity of 10. A bucket may not have the same item more than once. With random allocation and replacement, ...
- 11
-3
votes
0
answers
36
views
What mathematical formalism can be used to disprove natural selection on the basis there are too many simultaneous genetic parameters? [closed]
First of all, just to be clear: I am not promoting creationism as an explanation for the species present on Earth. These living species I accept arose through gradual evolution.
But I have doubts that ...
- 11
0
votes
0
answers
38
views
Count of permutation for empty set, why is it 1, not 0?
Count of permutation of n different items are:
A(n) = 1*2* .. *n
e.g:
[1] -> {1} // 1
...
- 215
1
vote
1
answer
36
views
Probability of no jack, queen, king before the first ace
I am reviewing some probability puzzles, and trying to solve them under a standard timed duration. But, I think could be completely wrong in formulating the below exercise problem. So, I'd like ...
- 5,082
1
vote
1
answer
48
views
If $N$ and $K$ are normal subgroups of a group $G$ such that $G=MN$ and $M\cap N=\langle e \rangle$ then $G=M\times N$.
The following is an exercise in Hungerford's abstract algebra text.
If $N$ and $K$ are normal subgroups of a group $G$ such that $G=MN$ and $M\cap N=\langle e \rangle$ then $G=M\times N$.
If $G=S_3$ ...
- 2,185
1
vote
1
answer
38
views
Eigenvalue Localization
Let $\mathbf{A} \in \mathbb{C}^{n \times n}$ be a normal matrix with eigenvalues $\lambda_1, \dots, \lambda_n$. Show there exists a permutation $\pi$ of $1, \dots n$ so that $$ \sum_{i=1}^n\left|a_{i ...
- 79
3
votes
3
answers
73
views
Permutation exercise
Let $A = \{1,2,3,4,5,6\}$.
In how many ways can we select in order without replacement, three elements from A such that the last number is even:
The dr's solution was $(5 * 4) * 3 = 5P2 * 3 = 60$. But ...
-3
votes
0
answers
25
views
how many arrangments in a circle? [closed]
we have 4 groups A, B, C, and D in A there are 3 people, in B 4 in C 7 in D 280.
how many arrangements in a circle are there when between each 2 people from groups A,B,C there are at least 10 from ...
3
votes
2
answers
86
views
Letters arrangement so that vowels are never together - can't find my mistake... is there any other way to attempt this problem?
In how many ways can the letters of the word ${\sf DIRECTOR}$ be arranged so that the three vowels are never together?
I arranged the consonants in $5!/2!$ Then the number of gaps created around these ...
- 113
-1
votes
2
answers
79
views
Let $S=\{1,2,... 1000\}$. Find the number of subsets of $S$ so that sum of the elements of subset is a multiple of $3$. [closed]
Let $S=\{1,2,... 1000\}$ be a set of first $1000$ natural numbers. Find the number of subsets of $S$ so that sum of the elements of subset is a multiple of $3$.
I can see that the sum of elements in a ...
0
votes
2
answers
38
views
Examples where we calculate combinations/permutations using probability
The probability of an event $A$ is given by:
$$P(A) = \frac{n(A)}{n}$$
Usually, $n$ is easy to find out, and the only hurdle in finding $P(A)$ is $n(A)$.
However, suppose we are interested in finding $...
- 1,727
0
votes
0
answers
29
views
Counting number of ways to choose m non-empty contigous subsequences. [closed]
Suppose there is a sequence of numbers from 1 to n. We have to choose ordered m contiguous nonempty subsequences in such a way that every number from 1 to n belongs to at least 1 subsequence.
How many ...
0
votes
0
answers
16
views
If I know the cycle lengths of two permutations can I make any statements about the cycle length of their composition? [closed]
Let's say I know the cycle lengths of two permutations $\sigma,\tau \in S_n$. Can I make any comment about $\sigma \circ \tau$?
- 134
0
votes
0
answers
22
views
Can anybody help count cycles without certain strings?
Let $n\geq3$ be an odd positive integer and $C=\{a,b,c\}$. Let $E$ be the set of all $n$-cycles $x=(x_1,x_2,\ldots, x_n)$,
where $x_i\in C$, such that $x$ contains no segments of the following two ...
- 1
0
votes
3
answers
60
views
Number of permutations such that no two elements swap places
How many permutations of $N$ elements $x_1, x_2, x_3...x_n$ exist such that if $x_i$ ends up in the $j$th index, $x_j$ does not end up in the $i$th index? I'm stumped trying to figure out a clean, ...
1
vote
0
answers
22
views
How many strings can be formed by reordering the letters ABCDEF so that each string contains the substring EA or the substring CE or both?
How many strings can be formed by reordering the letters ABCDEF so that each string contains
the substring EA or the substring CE or both?
So I thought considering EA as single character there are 5! ...
2
votes
2
answers
14
views
Each row of an n x n table form an arithmetic progression. Find n such that table can be transformed so that each column form arithmetic series
We place $ 1,\ldots,n^2$ integer numbers into an $n \times n$ table. We call this table good if each row can be permuted to form an arithmetic progression. For what value of $n$ can we transform (by ...
XMannnn
0
votes
0
answers
19
views
Special Case - How to generate a formula to calculate where next additional items in a set of items, in a particular row and at a particular index
I've tried to generate a simple formula to do this calculation but I've not successfully arrived at a working formula.
Here, I have a list of items displayed in a grid.
Let's use these symbols
...
0
votes
0
answers
36
views
About the number of disjoint cycles in a product of permutations [duplicate]
I am being troubled by a quick doubt on products of permutations. Concretely suppose we have the permutation
$$(123\dots n)^k,\quad\text{for some}\quad k=1,\dots,n$$
I wish to find the number of ...
- 1,060
2
votes
1
answer
33
views
Understanding rearrangement and simplification of products of adjacent transpositions.
Whilst working with permutations I have attempted to write several as products of disjoint cycles and adjacent transpositions. Below is an example:
$\sigma =
\begin{pmatrix}
1 & 2 & 3 & ...
- 23
0
votes
1
answer
23
views
I am trying to understand how to rearrange and simplify adjacent transpositions of permutations
Whilst working with permutations I have attempted to write several as products of disjoint cycles and adjacent transpositions. Below is an example:
$\sigma =
\begin{pmatrix}
1 & 2 & 3 & ...
- 23
4
votes
1
answer
87
views
Let $T$ be the following set of ordered triplets,$T=\{(a,b,c):a,b,c\in N\}$. Find the number of elements in $T$ such that $L.C.M(a,b,c)=72$.
Let $T$ be the following set of ordered triplets,$T=\{(a,b,c):a,b,c\in N\}$. Find the number of elements in $T$ such that $L.C.M(a,b,c)=72$.
My Attempt
Let $a=2^{x_1}3^{y_1}$,$b=2^{x_2}3^{y_2}$ and $c=...
- 7,837
0
votes
0
answers
16
views
What is the trace of the second tensor component?
My teacher asks to prove that for any matrix $A \in \operatorname{Mat}(N, \mathbb{C})$ there is true:
$$
A=\operatorname{tr}_2\left(P_{12} A_2\right)
$$
where $A_{2}=E_{N}\otimes A$ and $P_{12}$ is ...
- 23
-1
votes
0
answers
13
views
Inclusion exclusion principle (proper definition and where it works) [closed]
What is actually inclusion exclusion principle? Can you explain it briefly along with an example.
0
votes
0
answers
55
views
Permuting the letters of "COCONUT" [closed]
Find the number of ways in which all the letters of the word "COCONUT" can be arranged such that at most one "C" comes at odd place.
My answer is coming out to be 540. Is it ...
- 113
2
votes
1
answer
64
views
Proof for order of composition for permutations on indices into a sequence
Suppose I have a sequence $s$ that contains some elements in a well-defined order. Furthermore, let $i$ be an integer (an index into the sequence) and $s[i]$ shall denote the $i$-th element from $s$.
...
- 249
2
votes
1
answer
26
views
Number of $6$ digit numbers which can be formed with $4$ specific different digits such that each digit appears at least once
My problem is that I'm getting different answers with two different approaches:
Approach 1:
I have taken two cases:
Case 1: $2$ alike, $2$ alike, $2$ different
Number of ways of such a case is $$\...
0
votes
1
answer
34
views
What is the probability that there will be 1 ministerial position with two claims, 1 position with no claims, and 8 positions with one claim?
I have a question regarding a counting problem:
a)Within the coalition of five parties ten ministerial positions must be divided between the parties. Each party is allowed to claim two such positions, ...
- 41
0
votes
0
answers
42
views
On coset equalities
Let $H \le \textrm{Sym}(n)$, where $n \in \mathbb{Z}$ and Sym(n) stands for the symmetric group over $n$ elements. Furthermore let $g \in \textrm{Sym}(m)$ where $m \in \mathbb{Z} \land m \ge n$. This -...
- 249
4
votes
2
answers
36
views
Confusion Over The Definition of a Transposition Cipher
In our Discrete Mathematics class, the way the textbook introduces the transposition cipher is as follows:
As
a key we use a permutation $\sigma$ of the set $\{1, 2, \ldots , m\}$ for some positive ...
- 217
0
votes
1
answer
33
views
Forming a 3-digit number from a set of 5 digits, given restrictions.
The given question is:
A three-digit number is formed from the digits 3, 4, 5, 6 and 7 (no repetitions allowed). Find the probability that…
a) the number contains the digits 3 and 5.
b) the number ...
- 394
0
votes
0
answers
31
views
How many super-increasing functions are there? [closed]
Let $f:[n] \to [k]$ such that $n,k \in \mathbb{N}$, where $[n]=\{1,2, \ldots, n\}$. How many functions satisfy $f(i)+i \leq f(i+1)$ in terms of $n$ and $k$?
To start with, we know there are $k^n$ ...
2
votes
0
answers
58
views
Generating Function for the number of $n$-permutations whose square is the identity permutation.
I am learning the concept of generating functions and am working on the following problem:
Let $r(n)$ be the number of $n$-permutations whose square is the identity permutation. We proved that
$$r(n+...
- 89
7
votes
1
answer
85
views
How to find an element fixed by a given group?
In Dummit's 1991 paper he presents an element $\theta \in \mathbb{Q}(x_1, x_2, x_3, x_4, x_5)$ that, when you ponder it, can be seen to be invariant to the 2 permutations $\{(1 \, 2 \, 3 \, 4 \, 5), (...
- 387
0
votes
0
answers
45
views
NOT Every permutation can be expressed as the product transpositions
I read the following claim:
Every permutation can be expressed as the product of one and only one
of the following:
an odd number of transpositions ⟺ odd permutation an even number of
transpositions ⟺...
- 151
-2
votes
1
answer
146
views
Abelian subgroups of $S_n$? [closed]
I was playing around with the group $S_4$ and it’s subsets, and I came to this conclusion and wanted to write my first paper on it. (my question is so stupid it might not be valued though)
The set $\...
- 21
0
votes
1
answer
28
views
Are transitive permutation groups of prime degree 2-generated?
According to
Primitive permutation groups that are 2-generated
all 2-transitive permutation groups are 2-generated. There are, however, primitive groups of non prime degree, for example $ ...
- 5,696
2
votes
0
answers
45
views
Number of permutations of $[n]$ that have no increasing subsequence of length $k$
How many permutations are there that have no increasing subsequence of length $k$. Alternatively, lower bounds are welcome.
For $k=3$, it is known that the answer is the Catalan number: $C_n=\frac{1}{...
- 1,938
0
votes
1
answer
53
views
how to check how many words can be made? [closed]
how many words with length 30 can I create using only 0,1,2 when we use at least 12 2's and the difference of times we use 0 and 1 is 2 at most?
it is possible not to use 0's or 1's or both if the ...
1
vote
2
answers
85
views
In how many ways can $2^5\times 3^7$ be factored into three setwise coprime integers?
Let $T$ be the following set of ordered triples, $T=\{(a,b,c):a,b,c\in \mathbb{N}\}$.
Find the number of elements in $T$ such that $abc=2^5\times 3^7$ and $\gcd(a,b,c)=1$
My Attempt
If $a=2^x;b=3^y;c=...
- 7,837
-1
votes
0
answers
20
views
problem of combination and permutations.. I tried to make the problem a little more difficult.. can't verify whether answer of right or wrong
Four visitors A, B, C and D arrived at a town that has 5 hotels. In how many ways, can they disperse themselves among 5 hotels?
Since it is not mentioned in the question that whether more than more ...
- 113
0
votes
1
answer
42
views
Is there a relation between principle of addition, principle of multiplication and mutually exclusive, independent events?
My understanding is as follows:
(a) If we have two events that are independent, then we can directly apply the principle of multiplication
(b) If we have two events that are mutually exclusive, then ...
- 157
0
votes
0
answers
55
views
The product of two odd permutations is even intuition [duplicate]
I dont understand why the product of two odd permutations is even. I tried searching on the internet but I did not find a good answer where I understand. Thus, I am asking for an intuitive ...
- 557
1
vote
1
answer
53
views
What is the connection between the notions of cyclic permutation and cyclic group?
I am working with the following definitions:
If a permutation consists of exactly one cycle (that is, if the $m$ for which $\pi^m = id_X$ is equal to the cardinality of $X$, $m = n$) then we say that ...
- 785
4
votes
3
answers
101
views
Sum of signed permutations of digits equals zero
After playing around with signed permutations lately, (as part of studying properties of antisymmetric tensors and wedge products which are not really related to what I want to ask about), I noticed ...
- 331
0
votes
0
answers
19
views
Arrangement of element such that no two share the same position nor the same order [duplicate]
My friend asked me an interesting question yesterday:
Say you have six names, which you have to sort in six groups. The order of the names must always be different between the groups, such that:
...
