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} \\

Leave a comment