14
votes
Arranging people in a jeep.
Lots of good things in this near-solution! There's only one mistake: each legal seating configuration actually arises $6=3!$ different ways in the construction, depending on the order in which the ...
- 84.8k
13
votes
Arranging people in a jeep.
As indicated in Greg Martin's answer, you are currently overcounting because every configuration is considered $6$ times.
Imagine starting with the pair $(A, B)$ and assigning them to the left-most ...
- 7,969
12
votes
Number of ways a chess king can move from a1 to h8
Such paths consisting of only north (N), east (E), and northeast (NE) steps are counted by the Delannoy numbers. In particular the one you've asked for, moving seven steps north and seven steps east, ...
- 23.6k
12
votes
Accepted
Expected number of numbers that stay at their place after k swaps
Let $P(k)$ be the probability that a given number returns to its position after $k$ swaps. Then $P(0) = 1$, and for $k \geq 0$,
\begin{aligned}
P(k + 1) &= \frac{n-2}{n} P(k) + \frac{2}{n^2-n} \...
- 1,253
11
votes
Accepted
How can I tell if a permutation can be expressed as the commutator of another 2 permutations?
For the question in the post (now edited):
In any group other than the trivial group and the group of two elements, every element can be written as the product of two nontrivial elements. In ...
- 407k
10
votes
Showing There is No Group Epimorphism from $S_n \longrightarrow \mathbb{Z}/2\times\mathbb{Z}/2$, $n\geq 1$
Here is a simpler approach (I think). It avoids things like maps out of $\mathbf Z/(2) \times \mathbf Z/(2)$ to a smaller group, and all it relies on is that $\mathbf Z/(2) \times \mathbf Z/(2)$ is ...
- 48.7k
10
votes
Accepted
What are the best known asymptotic bounds on the size of the largest non-trivial subgroup of the symmetric group?
Since the alternating subgroup trivializes this question for $S_n$ we can re-ask the question for $A_n$. We always have a subgroup $A_{n-1}$ of index $n$ (for $n \ge 3$). If $G$ is a subgroup of index ...
- 441k
10
votes
Accepted
Representing permutation groups as equivalence relations
$S_3$ and $A_3$ induce the same equivalence relation on the power set of $\{1,2,3\}$, namely that two subsets are equivalent if and only if they have the same size.
This is clear for the empty set, ...
- 407k
9
votes
What exactly is the orbit-stabilizer theorem?
The way I state it in my final year group theory course is:
Let $G$ act on $\Omega$ and let $\alpha \in \Omega$. Then there is a bijection
between the right cosets $G_\alpha g$ of $G_\alpha$ in $G$ ...
- 92.7k
9
votes
Accepted
Is there a permutation of a given length in which every element divides sum of the elements before it?
Let $p = (x + 1, 1, x + 2, 2, \ldots)$, with $x = \left \lfloor \frac{n}{2} \right \rfloor$. It's not hard to check that $p$ is indeed a permutation and the condition holds.
- 310
8
votes
Accepted
Algorithm for finding intersection of two groups from generators
There is a backtrack algorithm for this problem, which is described in detail in Section 4.6.6 of "Handbook of Computational Group Theory" by Holt, Eick and O'Brien, or in Section 9.1.2 of &...
- 92.7k
8
votes
Accepted
Minimal permutation degree of the dihedral group
This is correct if $n\geq 3$. To see this, note that if $D_n$ embeds in $S_m$ then $S_m$ must have an element of order $n$. If $n$ is the product of the $q_i$ then the only way to get an element of ...
- 11.4k
7
votes
Number of ways a chess king can move from a1 to h8
The mistake here is that you replaced $7!7!$ with $2\cdot 7!$, while it is actually $(7!)^2$. Other than that the solution seems to be correct.
- 328
7
votes
Accepted
What is the number of possible orders for this list of real numbers?
There are $n!\times 2^n$ possible orders. The $n!$ comes from ordering the $a_i$, and the $2^n$ comes from choosing, for each of the first $n$ positions in the order (corresponding to the values $<...
- 12k
7
votes
Asymptotically, how many permutations on $S_n$ have order exactly $k$, when $k$ is fixed and $n$ goes to infinity?
Equation (2.6) of a 1986 paper by Wilf gives an asymptotic formula for $f(k,n)$, the number of permutations $\sigma$ in $S_n$ such that $\sigma^k$ is the identity. In the subsequent lines is the ...
- 84.8k
6
votes
Are all isomorphic subgroups of $S_\omega$ conjugate?
No. Consider the subgroup of permutations that fix all odd numbers. This is isomorphic to the whole group, but not identical to it (and the whole group always conjugates only to itself).
- 167k
6
votes
Accepted
Permutation of cartesian product
For determining the sign, you have a small mistake. Each transposition $(i\;j)$ in $\sigma$ corresponds to $n$ transpositions in $\xi$, switching $(i,y)$ with $(j,y)$ for each $y\in Y$. Similarly, ...
- 79.8k
6
votes
Accepted
A fair coin is tossed 9 times, then find the probability that at least 5 consecutive heads occur.
The error is in the way you have applied inclusion-exclusion. You found that the number of ways of getting $5$ heads consecutively (with overcounting) is $5 \cdot 2^4$, and $6$ heads consecutively (...
- 10.9k
6
votes
A fair coin is tossed 9 times, then find the probability that at least 5 consecutive heads occur.
A simple way to conceive it is that there are $5$ possible starting points for a streak of at least $5$ heads in $9$ tosses, and that except for the streak starting from the beginning, all other ...
- 43.6k
6
votes
Does $\sum\limits_{n=1}^\infty\frac{1}{\text{Sum of permutations of digits of }n}$ converge?
Let $\mathcal{W}_d = \{1, \ldots, 9\} \times \{0, \ldots, 9\}^{d-1}$ denote the set of all strings for the $d$-digit decimal expressions. If we denote OP's sum by $S$, then
\begin{align*}
S
&= \...
- 172k
6
votes
Accepted
Triple-Transitivity/"Specify three know all" property of exotic transitive $S_5\subset S_6$
The group you call the exotic $S_5$ is otherwise (and better) known as ${\rm PGL}(2,5)$, and the three properties you described are collectively known as sharp triple transitivity. The group ${\rm PSL}...
- 92.7k
6
votes
Permutations of 10 players within 2 Badminton courts: Covering $10$-vertex complete graph $K_{10} $ by two disjoint $K_4$
It is related to covering graph problems, in which the minimum number of subgraphs of a given graph $G$ with a specific property is determined such that the union of the subgraphs is $G$. The problem ...
- 10.2k
6
votes
Accepted
Is the alternating group of degree infinity a normal subgroup of symmetric group of degree infinity?
I expect this has appeared here previously, but there is a result classifying all normal subgroups of the symmetric group ${\rm Sym}(X)$ on an infinite set $X$. For a proof, see for example Theorem 8....
- 92.7k
6
votes
Arranging Letters in a string
Successively apply the well known "gap" and "subtraction" methods.
Firstly, keep the $B's$ separate by placing them in the gaps of $-A-A-C-D-D-$ and permute the other letters, ...
- 43.6k
6
votes
Diameter of $S_{n^2}$ with respect to two copies of $S_{n} \wr S_{n}$
Edit The answer was incomplete with Step 3 before, but thanks to @Steve D's answer I have added it now
I will show that the diameter of this graph is $3$ for all $n$. To prove this, I will construct ...
- 1,165
6
votes
Accepted
Diameter of $S_{n^2}$ with respect to two copies of $S_{n} \wr S_{n}$
OK here is an answer, showing the diamater is $3$ for almost all $n$.
The diameter cannot be $2$, simply by size considerations of $|HH'|$, which has relative size in $S_{n^2}$ at most (by Stirling's ...
- 4,997
6
votes
How many ways are there to place 6 salamanders on a 6-by-6 grid such that no 2 salamanders share the same row, column, or diagonal?
Your program claims that there are only 4 solutions. The problem must be very highly constrained. This suggests that a simple search of the space will result in most partial placements pruned early.
...
6
votes
Accepted
Given $X=\{1,2,3,4,5\}$ and $Y=\{1,2,3,...,15\}$. Find number of injective functions $f:X\to Y$ such that $f(i)>i$ for all $i\in \{1,2,3,4,5\}$..
To summarize the discussion in the comments:
There are $10$ options for $f(5)$. Having fixed that value, there are now $10$ options for $f(4)$, as you acquire $5$ as an option but lose $f(5)$. This ...
- 72.5k
5
votes
intuitively Understanding meaning of a Combinatorics problem to reach solution
For each natural $n$ let $f(n)$ be the number of steps to identify the correct switch among $n$ switches in the worst case.
I claim that $f(n)=\lceil \log_2 n\rceil$, that is $f(n)$ is the smallest ...
- 95.4k
5
votes
Accepted
How many 3 digit numbers are there which are divisible by 2,6and 10 but not divisible by 13,29?
The numbers divisible by 2, 6 and 10 are the same as the numbers divisible by LCM[2,6,10] = 30. These would be 120, 150, ...,990 totaling to $\left\lfloor\frac{900}{30} \right \rfloor = 30 $ 3-digit ...
- 238
Only top scored, non community-wiki answers of a minimum length are eligible