Skip to main content
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 ...
Qiaochu Yuan's user avatar
5 votes

How many permutations of n elements exist, such that for each pair of permutations, they are still distinct after removing any element?

As mentioned in a comment, one approach is to solve a maximum independent set problem in a graph with a node for each permutation $p\in P$ and an edge $(p,q)\in E$ for each pair of permutations that ...
RobPratt's user avatar
  • 47.5k
4 votes
Accepted

Prove that $\frac{(n + 1)!}{((n + 1) - r)!} = r \sum_{i=r - 1}^{n} \frac{i!}{(i - (r - 1))!}$

If you divide both sides by $r!$, you find: $$\frac{(n + 1)!}{(n + 1 - r)! r!} = {n + 1 \choose r} = \sum_{i = r - 1}^{n} \frac{i!}{(i - (r - 1)!) (r - 1)!} = \sum_{i = r - 1}^{n} {i \choose r - 1}$$ ...
jvdhooft's user avatar
  • 7,679
4 votes

How many permutations of n elements exist, such that for each pair of permutations, they are still distinct after removing any element?

We can achieve $\tfrac{n!}{(n-1)^2+1}$. Each permutation that we put in the set eliminates $(n-1)^2$ other permutations from consideration. (Proof: We can choose any of the numbers $1$ through $n$ and ...
David E Speyer's user avatar
4 votes
Accepted

How to prove that $\Pi_{\substack{1\leq i\leq m}\\{m+1\leq j\leq n}}\dfrac{1}{i-j}=\Pi_{\substack{1\leq i\leq m}\\{m+1\leq j\leq n}}\dfrac{1}{j-i-n}$?

Let $$u=m-i+1\quad\text{and}\quad v=n-j+m+1.$$ Then, $$\prod_{1\le u\le m\atop m+1\le v\le n}\frac1{u-v}=\prod_{1\le i\le m\atop m+1\le j\le n}\frac1{j-i-n}.$$
Anne Bauval's user avatar
  • 39.8k
3 votes
Accepted

Two vectors with same numbers in different order

You can say, depending on taste, that $a$ and $b$ "are equivalent up to permutation (of the coordinates)," "are permutations of each other," "are in the same orbit of the ...
Qiaochu Yuan's user avatar
2 votes

Prove that $\frac{(n + 1)!}{((n + 1) - r)!} = r \sum_{i=r - 1}^{n} \frac{i!}{(i - (r - 1))!}$

Induction on $n$ should work. For $n=r-1$ it is true and for the induction step note that $r!(\binom{n+2}{r}-\binom{n+1}{r})=r!\binom{n+1}{r-1}=r\frac{(n+1)!}{(n-r+2)!}$.
dialegou's user avatar
  • 432
2 votes

Prove that $\frac{(n + 1)!}{((n + 1) - r)!} = r \sum_{i=r - 1}^{n} \frac{i!}{(i - (r - 1))!}$

Let's modify your approach. LHS: Select $r$ distinct elements from the set $S_n = \{0, 1, 2, \ldots, n\}$, then arrange them in a sequence of length $r$, which can be done in $$P(n + 1, r) = \binom{n ...
N. F. Taussig's user avatar
2 votes

How many permutations of n elements exist, such that for each pair of permutations, they are still distinct after removing any element?

Here is a lower bound, although one which is much worse than $(n-1)!$: I can show that there are at least $\tfrac{n!}{2^n-1}$ such permutations. This is the best I can achieve constructively, although ...
David E Speyer's user avatar
1 vote
Accepted

An element of order p in $S_p$ is a p-cycle and there is no element of order kp for $k \geq 2$

Suppose there exists an element $\sigma$ of order $kp$ in $S_p$ for $k\ge 2$. What would that mean? Well, since $p$ is prime, we need a cycle $\pi$ of length $p$ such that $\sigma=\tau\pi$ for some $\...
Shaun's user avatar
  • 45.8k

Only top scored, non community-wiki answers of a minimum length are eligible