TD6 : Groupes cycliques, Actions de groupe et théorème de Fermat, Séries Formelles, Nombres de Catalans

1.

1.

a).

\(∀x, y ∈ H_m, \underbrace{(x-y)+ ⋯ + (x-y)}_{m \text{ fois}} \\ = x + ⋯ + x - (y + ⋯ + y) = 0 + 0 + 0\) (car $ℤ/nℤ$ est un anneau)

b).

Lemme : Tout sous-groupe $H$ d’un groupe cyclique $G = ⟨x⟩$ est cyclique

En notant $r$ la plus petite puissance de $x$ tel que $x^r ∈ H$, on montre aisément que

\[H = ⟨x^r⟩\]

(l’inclusion $H⊆⟨x^r⟩$ s’obtient par division euclidienne de l’exposant d’un élément de $H$ par $r$)

Donc

$ℤ/nℤ = ⟨1⟩$

$H_m$ est cyclique, et engendré par le (la classe du) plus petit entier $r$ tel que \(\underbrace{r+ ⋯ + r}_{m \text{ fois}} = 0\)

Soit : plus plus petit entier $r$ tel que

\[mr ∈ nℤ\]

Montrons que :

\[r = n/(m∧n)\]

En effet :

• par définition, $mr = m∨n$

2.

1.

Évident : \(or((1, ⋯, p))=p\)

2.

Il y a :

• $𝜑(p) = p-1$ éléments d’ordre $p$
  • ce sont les éléments $𝛾^k$, pour $1≤k≤p-1$
• 1 élément d’ordre $1$
  • c’est $id$

3.

a).

C’est clairement une action de groupe :

• $id$ a pour action l’identité
• On vérifie qu’elle est stable par composition

b).

Le fixateur de $𝛾^i$, pour tout $1≤i≤p-1$, est l’ensemble des mots formés d’une seule lettre.

Le fixateur de l’identité est l’ensemble des mots.

c).

C’est Burnside, avec $G = ⟨𝛾⟩$.

d).

Petit théorème de Fermat :

Si $p$ est premier :

\[∀a ∉ pℤ, a^{p-1} = a \mod p\]

donc :

\[∀a ∈ ℤ, a^p = a \mod p\]

On considère la relation précédente modulo $p$ :

\[|𝛴|^p = |𝛴| \mod p\]

4.

1.

• $C_0 = 1$
• $C_1 = 1$
• $C_2 = 2$

2.

Soit $n∈ℕ$.

\[C_{n+1} = \sum\limits_{i=0}^n C_i C_{n-i}\]

clair, si on pense au fait que $C_n$ est le nombre de manière d’interpréter un produit non associatif de $n$ éléments.

Soit

\[x_0 \star ⋯ \star x_n\]

un produit non associatif de $n$ éléments : où mettre les deux premières parenthèses ?

• $(x_0 \star x_2) \star ⋯ \star x_n$
  • puis : $C_1 \times C_{n-1}$ interprétations possibles
• $(x_0 \star x_2 \star x_3) \star ⋯ \star x_n$
  • puis : $C_2 \times C_{n-2}$ interprétations possibles
• $(x_0 \star x_2 \star ⋯ \star x_k) \star ⋯ \star x_n$
  • puis : $C_k \times C_{n-k}$ interprétations possibles
• $(x_0 \star x_2 \star ⋯ \star x_{n-1}) \star x_n$
  • puis : $C_{n-1} \times C_1$ interprétations possibles

1.

\[\begin{align*} S - 1 &= \sum\limits_{n≥1} C_n X^n \\ &= X \sum\limits_{n≥0} C_{n+1} X^n \\ &= X \sum\limits_{n≥0} (\sum\limits_{i=0}^n C_i C_{n-i}) X^n \\ &= X S^2 \end{align*}\]

2.

\[S^2 - \frac 1 X S + \frac 1 X = 0\] \[S = \frac{1}{2X} (1±\sqrt{1-4X})\]

Or :

\[\sqrt{1-4X} = 2 \int_1^X \frac{1}{\sqrt{1 - 4\bullet}} \\ = 2 \int_1^X \sum_{n≥0} \frac{(2n)!}{(n!)^2} \bullet^n \\ = 2 (\sum_{n≥0} \frac{(2n)!}{(n+1)(n!)^2} X^{n+1} + 1) \\ = 2 (\sum_{n≥0} \frac{(2n)!}{(n+1)(n!)^2} X^{n+1}) + 1 \\\]

car \((1+x)^{-1/2} = \sum\limits_{n≥0} (-1)^n \frac{(2n)!}{4^n (n!)^2} x^n\)

Donc

\[S = \frac{1}{2X} (1-\sqrt{1-4X}) \\ = \frac 1 X (\sum_{n≥0} \frac{(2n)!}{(n+1)(n!)^2} X^{n+1}) \\ = \sum_{n≥0} \underbrace{\frac{\binom{2n}{n}}{(n+1)}}_{= C_n} X^{n} \\\]