Intereting Posts

Could someone explain rough path theory? More specifically, what is the higher ordered “area process” and what information is it giving us?
Evaluating $\int _0^{\frac{\pi }{2}}\:\frac{\sqrt{\sin^2\left(x\right)}}{\sqrt{\sin^2\left(x\right)}+\sqrt{\cos^2\left(x\right)}}dx$
How to prove that an operator is compact?
Proving a relation between inradius ,circumradius and exradii in a triangle
Maximal Hamming distance
What is the symbol ''$\divideontimes$'' (DIVIDE TIMES) for?
lim$_{n\rightarrow \infty}\int _{-\pi}^\pi f(t)\cos nt\,dt$
$\mathbb{Z}/(X^2-1)$ is not isomorphic with $\mathbb{Z}\times \mathbb{Z}$
If $R=\{(x,y): x\text{ is wife of } y\}$, then is $R$ transitive?
The asymptotic expansion for the weighted sum of divisors $\sum_{n\leq x} \frac{d(n)}{n}$
How to find all subgroups of a group in GAP
Is the $n^{\text{th}}$ homotopy group isomorphic to $$
Non combinatorial proof of formula for $n^n$?
The tensor product of non algebraic extensions is not a field
Need to show that $\lim_{x\to\infty}\left(\sum_{n\le x}^{}\frac{1}{n}-\ln x \right)$ exist and is less than $1$

I have been working on this exercise for a while now. It’s in B.L. van der Waerden’s *Algebra (Volume I)*, page $19$. The exercise is as follows:

The order of the symmetric group $S_n$ is $n!=\prod_{1}^{n}\nu$. (Mathematical induction on $n$.)

I don’t comprehend how we can logically use induction here. It seems that the first step would be proving $S_1$ has $1!=1$ elements. This is simply justified: There is only one permutation of $1$, the permutation of $1$ to itself.

- Help me to prove that group is cyclic
- $G$ be a non-measurable subgroup of $(\mathbb R,+)$ ; $I$ be a bounded interval , then $m^*(G \cap I)=m^*(I)$?
- Subgroup of matrices exercise
- Proving a defined group $(G,*)$ is isomorphic to $(\mathbb{R},+)$
- Proving a set is an abelian group.
- Showing a free abelian group is generated by its basis

The next step would be assuming that $S_n$ has order $n!$. Now here is where I get stuck. How do I use this to show that $S_{n+1}$ has order $(n+1)!$?

Here is my attempt: I am thinking this is because all $n!$ permutations of $S_n$ now have a new element to permutate. For example, if we take one single permutation

$$

p(1,\dots,n)

=

\begin{pmatrix}

1 & 2 & 3 & \dots & n\\

1 & 2 & 3 & \dots & n

\end{pmatrix}

$$

We now have $n$ modifications of this single permutation by adding the symbol $(n+1)$:

\begin{align}

p(1,2,\dots,n,(n+1))&=

\begin{pmatrix}

1 & 2 & \dots & n & (n+1)\\

1 & 2 & \dots & n & (n+1)

\end{pmatrix}\\

p(2,1,\dots,n,(n+1))&=

\begin{pmatrix}

1 & 2 & \dots & n & (n+1)\\

2 & 1 & \dots & n & (n+1)

\end{pmatrix}\\

\vdots\\

p(n,2,\dots,1,(n+1))&=

\begin{pmatrix}

1 & 2 & \dots & n & (n+1)\\

n & 2 & \dots & 1 & (n+1)

\end{pmatrix}\\

p((n+1),2,\dots,n,1)&=

\begin{pmatrix}

1 & 2 & \dots & n & (n+1)\\

(n+1) & 2 & \dots & n & 1

\end{pmatrix}

\end{align}

There are actually $(n+1)$ permutations of that specific form, but we take $p(1,\dots,n)=p(1,\dots,n,(n+1))$ in order to illustrate and prove our original statement. We can make this general equality for all $n!$ permutations: $p(x_1,x_2,\dots,x_n)=p(x_1,x_2,\dots,x_n,x_{n+1})$ where $x_i$ is any symbol of our finite set of $n$ symbols and $x_{n+1}$ is strictly defined as the symbol $(n+1)$.

We can repeat this process for all $n!$ permutations in $S_n$. This gives us $n!n$ permutations. Then, adding in the original $n!$ permutations, we have $n!n+n!=(n+1)n!=(n+1)!$. Consequently, $S_n$ has order $n!$.

How is my reasoning here? Furthermore, is there a more elegant argument? I do not really see my argument here as *incorrect*, it just seems to lack elegance. My reasoning may well be very incorrect, however. If so, please point it out to me.

- If $p$ is an odd prime, does every Sylow $p$-subgroup contain an element not in any other Sylow $p$-subgroup?
- subgroups of finitely generated groups with a finite index
- A finite Monoid $M$ is a group if and only if it has only one idempotent element
- Isomorphisms: preserve structure, operation, or order?
- Are the primitive groups linearly primitive?
- If $H$ is a proper subgroup of a $p$-group $G$, then $H$ is proper in $N_G(H)$.
- How to count the closed left-hand turn paths of planar bicubic graphs?
- Examples of group extension $G/N=Q$ with continuous $G$ and $Q$, but finite $N$
- May a group have two disjoint subgroups?
- Is the “binary operation” in the definition of a group always deterministic?

You can actually just use a combinatorial argument for this. The permutation group is a bijection from a set of $n$ elements to itself. So look at the first element in the permutation. There are $n$ choices to send that element to. Now for the second element, there are only $n-1$ choices left (because it is a bijection you cannot send two different elements in the domain to the same element in the codomain), and so on until you only have $1$ choice left for the last element. Thus we get $n!$ ways to arrange the permutation.

I start to get confused by the notation around halfway through. Here’s what I’d do: identify $S_n$ with the subgroup of $S_{n + 1}$ consisting of those permutations that fix $n + 1$. Choose elements $\sigma_1, \ldots, \sigma_{n + 1}$ of $S_{n + 1}$ such that $\sigma_i(n + 1) = i$. For example, you could take $\sigma_i$ to be $[i,n+1]$. Then prove that these are left coset representatives for $S_n$ in $S_{n + 1}$. In more detail, you need to do two things:

- If $\sigma \in S_{n + 1}$, then find an $i$ such that $\sigma_i^{-1}\sigma$ fixes $n + 1$.
- If $i \neq j$, then show that $\sigma_j^{-1}\sigma_i$ does not fix $n + 1$.

Here’s my answer using induction (it’s a similar proof, but seems more concise and understandable):

Our base is true.

Assume $S_n$ has $n!$ permutations.

Define all the original $n!$ permutations as permutations where $(n+1)$ is sent to itself. Thus, by definition, all other permutations (“the new permutations”) are the original permutations, except $(n+1)$ is sent to a place other than itself. There are $n$ places to send $(n+1)$ if we exclude $(n+1) \to (n+1)$. Since there are $n!$ original permutations, there must be $n!n$ new permutations. The reason for this is because, for all $n!$ permutations, there is $n$ different modifications of the $n!$ permutations (e.g. $(n+1) \to 1$, $(n+1) \to 2$, etc.). Therefore, the total amount of permutations of $S_{n+1}$ is $n!+n!n=(n+1)!$.

P.S. I only used induction because I wanted to do precisely as the exercise states; I try not to deviate in order to avoid erroneous proofs (in this case, I would prefer to deviate).

- Is it possible to build a circle with quadratic Bézier curves?
- Equilibrium existence proof
- Prove that the equation $x^4+(2k^2)x^2+2k^4$ is not a perfect square
- ($n$-dimensional) Inverse Fourier transform of $\frac{1}{\| \mathbf{\omega} \|^{2\alpha}}$
- Evaluating the limit: $\lim\limits_{x \to \infty} \sum\limits_{n=1}^{\infty} (-1)^{n-1}\frac{x^{2n-1}}{(2n)! \log (2n)}$
- What is the result of $ \lim_{n \to \infty} \frac{ \sum^n_{i=1} i^k}{n^{k+1}},\ k \in \mathbb{R} $ and why?
- Express in terms of Legendre polynomials
- Closed unit ball of $B(H)$ with wot topology is compact
- Is $f(x)=10$ a periodic function?
- cardinality of the set of $ \varphi: \mathbb N \to \mathbb N$ such that $\varphi$ is an increasing sequence
- Probability of picking a random natural number
- Minimum radius of N congruent circles on a sphere, placed optimally, such that the sphere is covered by the circles?
- How many ways are there for 8 men and 5 women to stand in a line so that no two women stand next to each other?
- Evaluate: $I=\int\limits_{0}^{\frac{\pi}{2}}\ln\frac{(1+\sin x)^{1+\cos x}}{1+\cos x}dx$
- A generalization of the connected sum of links