Questions tagged [permutations]
For questions related to permutations, which can be viewed as re-ordering a collection of objects.
13,130 questions
1
vote
2
answers
42
views
Problem with 3 urns and balls of 3 different colors
Suppose we have 4 red balls, 5 green balls and 6 blue balls. In how many ways can we distribute these balls into 3 numbered urns, $U_1, U_2$, and $ U_3$? Note that the balls can be distributed in any ...
- 402
-3
votes
0
answers
14
views
How to Simplify a Summation of Products Involving Consecutive Integers? [closed]
I am trying to evaluate the summation:
1⋅2⋅3⋅4+2⋅3⋅4⋅5+⋯+n⋅(n+1)⋅(n+2)⋅(n+3).
1⋅2⋅3⋅4+2⋅3⋅4⋅5+⋯+n⋅(n+1)⋅(n+2)⋅(n+3).
In general, the summand can be written as:
k(k+1)(k+2)(k+3),for k ranging over {1,2,...
1
vote
1
answer
33
views
The number of the double cosets $K\backslash G/H$ equals $ \langle \pi_{G/K} , \pi_{G/H} \rangle$
$H$ and $K$ are subgroups of $G$. $\pi_{G/K}$ is the permutation character of the set $G/K$ (the left cosets).
My thoughts
I think we are finding the number of the $K$-orbit on the set of left cosets $...
- 55
0
votes
0
answers
30
views
Summation of Permutations: $\sum n=4NnP4 \sum n=4NnP4$ [closed]
I am working on evaluating the summation:
4⋅3⋅2⋅1+5⋅4⋅3⋅2+6⋅5⋅4⋅3+⋯+N⋅(N−1)⋅(N−2)⋅(N−3),
4⋅3⋅2⋅1+5⋅4⋅3⋅2+6⋅5⋅4⋅3+⋯+N⋅(N−1)⋅(N−2)⋅(N−3),
which can be compactly written as:
∑n=4NnP4,
n=4∑NnP4,
where ...
4
votes
1
answer
64
views
Find number of $7$ digit numbers using all non-zero digits such that $a_{1}<a_{2}<a_{3}<a_{4}>a_{5}>a_{6}>a_{7}$
Find number of $7$ digit numbers of the form $a_{1}a_{2}a_{3}a_{4}a_{5}a_{6}a_{7}$ using all non-zero digits such that $a_{1}<a_{2}<a_{3}<a_{4}>a_{5}>a_{6}>a_{7}$ and repetiton of ...
- 4,224
2
votes
1
answer
40
views
Cataloging the Core-free Subgroups of the Permutation Group
A subgroup H of G is called core-free if for every normal subgroup $N\subset G$ we have that $N\subset H$ implies $N=\{1\}$. That is, H is a core-free subgroup of G iff $\{1\}$ is the only normal ...
- 503
4
votes
1
answer
95
views
Characterization of transpositions in symmetric group?
For a symmetric group on an arbitrary (indeed potentially infinite) set, is it true that $x$ is a transposition if and only if $x^2=1$, $x \not= 1$, and $y^2=1$ and $C(x) \subseteq C(y)$ implies $y=x$ ...
- 123
1
vote
0
answers
62
views
Game with objects, 4 objects in 4 slots, but each guess is remembered
Let's say that there is a game that requires you to put letters A,B,C,D in some order.
If you placed A on 1st position and it was wrong, you remove it and remember that it was wrong on 1st position. ...
- 21
1
vote
2
answers
63
views
On $\mathrm{Gal}(\mathbb{Q}(e^{\frac{2i\pi}{n}}/Q)$
I want to show that $\mathrm{Gal}(\mathbb{Q}(e^{\frac{2i\pi}{n}}/Q)$ is abelian but without using or proving the fact that $\mathrm{Gal}(\mathbb{Q}(e^{\frac{2i\pi}{n}}/Q) \cong (\mathbb{Z}/n\mathbb{...
- 41
2
votes
0
answers
33
views
Logic of a set of permutations in $S_{10}$
Consider the following permutations $a,b,c\;{\in}\;S_{10}$;
$$a=(1\;2\;3\;4\;5),\;b=(6\;7\;8\;9\;10),\;c=(2\;7)(1\;6)$$
The question i am stuck on is whether a permutation, lets call it $\alpha$, ...
3
votes
5
answers
301
views
Arrangement of a word within a word
I came across this question from a trial paper today that has me scratching my head.
The letters of the word IMPRESSION are rearranged such that the letters of the word
PRESS appear in order but not ...
- 519
2
votes
0
answers
66
views
Multinomial Theorem Coefficients
I came across a question that combined the concept of inclusion-exclusion with the multinomial theorem, and would like help with understanding it.
Find the sum of all terms
i) that contain all four ...
-1
votes
2
answers
73
views
Proving combinatorics identity using reasoning
I want to prove this identity using reasoning rather than expansions:
$$
\mathcal{P}(n,r)=\mathcal{P}(n-1,r)+r\cdot\mathcal{P}(n-1,r-1)
$$
Where $\mathcal{P}(n,r)$ the number of permutations of all ...
1
vote
0
answers
22
views
Do Stirling permutations have Inverses, Cycles, or RSK Analogues?
I am interested in Stirling permutations, introduced by Gessel and Stanley
(cf. https://en.wikipedia.org/wiki/Stirling_permutation),
and I am wondering whether Stirling permutations share fundamental ...
- 51
3
votes
1
answer
338
views
IMO 1989 Problem 6
Does the formula $(2n)!-(2n-2)!⋅(n-1)⋅4$ hold for all $n\in\Bbb N$ such that it gives the value of the number of permutations of the set $\{1,2,\ldots, 2n\}$ with the property $P$ (the difference ...
- 59
3
votes
1
answer
76
views
Number of ways of colouring 7 points of an hexagon satisfying some conditions
Question
Let $ABCDEF$ be a regular hexagon and let point $O$ be its centre. How many ways can you colour these seven points either red or blue such that there doesn't exist any equilateral triangle ...
- 505
0
votes
1
answer
41
views
Groups in circular permutations
Let's say that there are $4$ entities: $A$, $B$, $C$ and $D$ that are to be permutated around a round table. There are $(4-1)!$ permutations for them to be seated. However, if $A$ and $B$ were a ...
- 11
0
votes
0
answers
78
views
Number of different arrangements of 6 letters
Find the number of ways to rescramble the word ROBLOX by reordering at least some of its letters in new orders.
I've tried 6! as an answer (720), but it doesn't work I'm assuming due to the condition: ...
0
votes
1
answer
49
views
What's this construction combining a group action with a pointwise group?
A symmetry of the $n$-dimensional cube $[-1,1]^n$ is a permutation of the $n$ coordinate axes and an optional reflection in each axis direction (applied before the permutation, say).
Generalizing this,...
- 12.2k
0
votes
2
answers
76
views
How many unique permuted strings of length 5 can be formed from the characters of string "balloon"?
If the permuted strings would be of length 7, equalling given string length, it would have been simple, that is $$ \frac{7!}{2! \cdot 2!} $$ equalling 1260. Each permutation included all characters ...
1
vote
1
answer
96
views
Embedding of a cyclic group of order $n=2^r$ inside $A_{n+1}$
I'm looking for a proof regarding the following question.
If $r\geq1$ be a positive integer and $n=2^r$ then prove that a cyclic group of order n cannot be embedded inside the Alternating group $A_{n+...
- 73
3
votes
3
answers
249
views
Calculate the number of ways to arrange the letters in the word "freezer" without having any adjacent (double) letters
I am looking for guidance as to how to account for the three e's in the word "freezer" where where double letters are not allowed.
The word consists of the following letters:
• f: 1
• z: ...
- 53
-1
votes
1
answer
72
views
In how many ways can we seat 6 people around a table if two person insist on sitting opposite each other [closed]
In how many ways can we seat 6 people around a table if two person insist on sitting opposite each other?
It is a permutation and combination question.
I tried solving it like - two persons have 3 ...
0
votes
1
answer
64
views
Ways of selecting $4$ shoes out of $5$ pair to form exactly $1$ pair of shoes
The question is to find the number of ways in which 4 shoes can be selected from 5 pair shoes such that we have exactly 1 pair.
My try-
Suppose the five pair of shoes are $ (a_1,a_2)(b_1,b_2)(c_1,...
- 135
1
vote
1
answer
42
views
Probability that a permutation of length $n$ has no cycle great than length $k$.
For example, lets say we have elements, $(012)(34)(567)(89)\in S_{10}$ and $(0123456)(789)\in S_{10}$; which are a 2x(2-cycle),2x(3-cycle) vs (7-cycle),(3-cycle). Based on this question, the ...
- 3,253
2
votes
0
answers
46
views
Cycle decomposition of the power of a cycle
I have a question regarding this Math stack exchange article:
Raising a cycle to a power, cycle decomposition
The author states that
$$
ord(\alpha^s) = \frac{m}{gcd(m,s)}
$$
which makes sense.
But ...
3
votes
1
answer
98
views
Help understanding circular permutation with restrictions
I need some help understanding a bit the intuition behind circular permutations and the inclusion–exclusion principle in practice.
Let's suppose there is a circular table for seven people.
If a pair ...
- 51
0
votes
0
answers
47
views
Is there a formula for the number of isomers given n carbon atoms?
I saw the following list of alkanes along with the number of isomers they have on Wikipedia:
C1: 1
C2: 1
C3: 1
C4: 2
C5: 3
C6: 5
C7: 9
C8: 18
C9: 35
C10: 75
C12: 355
C32: 27,711,253,769
C60: 22,158,...
- 690
3
votes
0
answers
59
views
Is there an optimal solution for the inverse of the 100 prisoner problem?
There's the famous https://en.wikipedia.org/wiki/100_prisoners_problem 100 prisoners problem. There are 100 numbered boxes, each containing the number of one of 100 prisoners. Each prisoner can open ...
- 131
1
vote
1
answer
30
views
Different traversals of a line graph with the same distance between adjacent nodes hit an endpoint at the same time
Suppose you have a path graph on $n$ nodes. Then take a permutation $s \in S_n$ and traverse the nodes in this order. Then this produces a sequence $a_1,...,a_{n-1}$ where $a_i = d(s(i),s(i+1)) = |s(i)...
- 57
1
vote
2
answers
123
views
How to solve this question about permutations, where my approach is wrong?
This a question from book "The Theory of Probability" by Santosh S. Venkatesh.
Let $\pi_1,\pi_2,…,\pi_n$ be a random permutation of numbers $1…n$. If it is told that $\pi_k>\pi_1,\pi_k&...
- 607
1
vote
2
answers
58
views
The number of positive integrals of $x_1x_2x_3= y$ in given set.
Let $y$ be an element of the $set A={1,2,3,5,6,10,15,30}$ and $x_1x_2x_3=y$, such that $x_1, x_2, x_3$ are positive integers. The number of positive integral solution of $x_1x_2x_3=y$ is what.
My ...
- 108
3
votes
0
answers
48
views
Find total ways such that Mr. A’s $3$ digit number is greater than Mr. B’s $3$ digit number:
If Mr. A randomly picks $3$ distinct numberrs from the set $\{1,2,3,....,9\}$ and arranges
them in descending order to form a three digit number, and Mr.B randomly picks $3$
distinct numbers from the ...
- 4,224
3
votes
1
answer
157
views
How to find the probability that no two hockey players are standing together
A school has $n$ pupils,
of whom $r$ play hocket,
where $n\geqslant r\geqslant2$.
All $n$ pupils are arranged in a row at random.
(i)
What is the probability that there is a hockey player at each end ...
- 260
0
votes
0
answers
35
views
Hall subgroups of the symmetric group.
I am trying to prove that $S_n$, or $A_n$ (perhaps working with $A_n$ is easier because it is simple), does not have Hall subgroups (for any set with more than one prime) for n other than a prime ...
- 59
1
vote
1
answer
38
views
Number of Multiset Pemutations with a Given Property
For a multiset with $n_1$ 1's, $n_2$ 2's, ..., and $n_k$ $k$'s, the total number of multiset permutations is
$$
\frac{n!}{n_1!n_2!\cdots n_k!}.
$$
where $n=n_1+\cdots+n_k$. Out of this set, some ...
- 13
0
votes
0
answers
60
views
Total Probability of Bridge hands
For the question "Find the probability of being dealt a bridge hand of 13 cards containing 5 spades, 2 hearts, 3 diamonds, and 3 clubs", the following awnser was given
$$\frac {\binom {13}5\...
5
votes
1
answer
80
views
Number of non-decreasing functions from set $A$ to $B$, where $f(i)$ does not equal $i$.
Given two sets $A=\{1,2,3,4\}$ and $B=\{1,2,3,4,5,6,7\}$.
The question is to find the number of non decreasing functions from $A$ to $B$ such that $f(i)$ is not equal to $i$.
My attempt went as ...
- 53
0
votes
1
answer
28
views
Row permutations of a column-block-diagonal adjacency matrix
Suppose I have an $n\times m$ matrix $\mathbf{A}$ which has a "column-block-diagonal" form in the sense that it consists of $m$ column-blocks of unit vectors, such that:
$$\mathbf{A} = \...
- 124
1
vote
1
answer
67
views
Combinations -arranging Groups of Identical Items in two distinct rows.
I have encountered the following permutations question:
How many ways are there to arrange 4 different types of fruit, 3 of each kind into 2 rows with six pieces of fruit in each row.
I think that the ...
- 13
1
vote
1
answer
97
views
Series that involves permutation in the denominator
Hi I have another factorial series exercise and I don't know how to solve it
$$\sum_{k=m}^{n} \frac{1}{(k-2)!(k^2-1)}$$
for $ m \geq 2$
and if I subtitute I get :
$$\frac{1}{3}+\frac{1}{8}+\frac{1}{30}...
- 63
4
votes
1
answer
109
views
How many subgroups of order 25 are contained in this group?
Let $G = C_{15} \times C_{50}$. How many subgroups of order $25$ does $G$ contain?
I immediately thought of cyclic groups, so I counted the elements of order $25$. $(x,y)$ with $x \in C_{15}$ and $y \...
3
votes
2
answers
84
views
For the symmetric group $S_n$, all subgroups of index $n$ are point stabilizers (natural action on the set $\{1,.\ldots,n\}$) when $n \neq 6$.
Theorem: For the symmetric group $S_n$, all subgroups of index $n$ are point stabilizers (for the natural action of $S_n$ on $\{1,\ldots,n\}$) when $n\neq 6$.
I am looking for a proof of this fact. ...
- 59
0
votes
0
answers
44
views
Reference to the result that each proper subgroup of $S_n$, apart from $A_n$, has index at least n? [duplicate]
In the book "Permutation Groups" by Dixon and Mortimer (chapter 5.2) it's stated that "An early observation in the theory of permutation groups was that, apart from $A_n$, each proper ...
- 343
2
votes
1
answer
69
views
Counting four-digit numbers divisible by 5 with specific restrictions
How many four-digit numbers divisible by 5 can be formed using the digits 0, 1, 3, 5, 7, 9 if repetition is not allowed and the digits 0 and 1 are not allowed to be placed next to each other?Note that ...
- 3,756
2
votes
2
answers
174
views
Finding the number of integers between $3456$ and $6000$ that have all unique digits
Finding the number of integers between $3456$ and $6000$ that have all unique digits.
How would one go about solving this question? Here is my approach:
Case $1$: Numbers of the type $34XX$
3 valid ...
6
votes
1
answer
301
views
The Coarsest Topology Which Topologizes a Group
Does there exist a coarsest topology which makes a general group $G$ a Hausdorff topological group? If so, can it be described in general, does it have a name?
In particular, I would like to show that ...
- 691
0
votes
0
answers
60
views
Is there a "nice" categorization of graphs of size $n$ whose automorphism group is $n!/O(n^4)$ or larger?
It is known that for graphs on $n$ vertices, only $K_n$ and the empty graph have the highest possible automorphism group size. It is also known that removing one edge from the complete graph (or ...
- 175
0
votes
1
answer
29
views
Why does the permutation of the indices ijk in the epsilon tensor imply the permutation of 123 when ijk are variables?
The epsilon tensor is defined as +1 when i,j,k are an even permutation of 1,2,3 and -1 when they are a uneven permutation of 1,2,3 and 0 when two Indices are the same. For example (I will just write ...
- 1
3
votes
0
answers
94
views
Expected Number of Coin Tosses Until n-th Head or n-th Tail
I'm working on finding the expected number of coin tosses required until either the $n$-th head or $n$-th tail appears, whichever comes first. The coin is fair, so the probability of heads or tails is ...
- 894