# Tag Info

### 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

### 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

### 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
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
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

### 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
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
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

### 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
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
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
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

### 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.
Accepted

• 92.7k

### 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
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

### 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

### 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
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

### 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. ...
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

### 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
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 ...