Leçon 310 agrégation interne : exercices faisant intervenir des dénombrements

bd2017

@Oshine, je ne comprends pas ta solution en particulier $|C_{ij}|=i \times j$.

Concernant  les autres exercices que tu proposes c'est un survol qui me dit que certains exercices sont très (trop) élevés.  mais je peux me tromper.

De toute façon pour donner un avis à peu près valable, il faudra qu'à la fin tu fasses un choix  et c'est sur ce choix qu'on pourrait donner un avis 

(bien entendu en étant informé des consignes générales du concours ... ) .

Je ne sais pas si dans tes exercices, il y a une identité avec "des binomials" à démontrer par le dénombrement mais perso j'en mettrais un aussi.

De mémoire, il y a en déjà eu sur le forum, pas trop évident à démontrer par le calcul  et plus facile à démontrer par le dénombrement (pourvu qu'on sache trouver ce qu'il faut démontrer). 

OShine

@bd2017
Oui j'en ai un. 
Certains exercices sont un peu durs, mais je dispose d'une correction détaillée, et j'ai bien compris les étapes et les résultats de cours qu'on utilise.

Exercice 3 : formule de Vandermonde.
1) Soit $m,n,p$ trois entiers naturels. Démontrer que : 
$\displaystyle\sum_{k=0}^p \binom{m}{k} \binom{p-k}{n}=\binom{m+n}{p}$
Indication : 
Considérer une ensemble de cardinal $m+n$, réunion d'un ensemble de cardinal $m$ et d'un ensemble de cardinal $n$.
2) En déduire que l'on a, tour tout entier naturel $n$ : 
$\displaystyle\sum_{k=0}^p \binom{n}{k} ^2=\binom{2n}{n}$.

OShine

En gros, le rectangle de taille $n \times p$ et la réunion de tous les rectangles possibles, qui sont les rectangles de tailles $i \times j$ avec $(i,j)$ parcourant $[|1,n|] \times [|1,p|]$.
Il s'agit d'une partition donc le calcul du cardinal se résume au calcul de la somme $\displaystyle\sum_{(i,j) \in [|1,n|] \times [|1,p|]} ij$ qui est très facile et qui donne $\dfrac{n(n+1)}{2} \times \dfrac{p(p+1)}{2}$.

bd2017

Oui, d'accord il est bien dans l'esprit dont je parlais. Mais ceux auxquels je pense me semblent plus difficiles et peut être un peu moins classiques  (mais je n'arrive pas à les refabriquer ou les retrouver) .. Sinon ça va ...Sauf que je ne comprends pas la deuxième question....Je crois que le jury ne comprendrait pas aussi.

Une question malgré tout, est-ce que tu peux démontrer l'identité par le calcul? (le Jury serait capable de te le demander pour voir tes capacités).

bd2017

Je ne comprends toujours pas!   Avec toi  $|C_{np}|= n p$  et ça c'est archi-faux!

Tu as zappé le problème en disant maintenant "Il s'agit d'une partition donc le calcul du cardinal se résume au calcul de la somme", ce qui me laisse croire que l'exercice que j'ai donné doit  surement  exister quelque part avec son corrigé.... mais quelque chose t'a échappé dans la compréhension du corrigé... 

Le problème est que le jour de l'oral, tu seras interrogé sur un exercice sans corrigé.... et alors patatrac.... 

lourrran

L'autre truc qui me fait dire 'refus d'obstacle'.... Sur l'algèbre, tu as fait plein d'exercices, un nombre incalculable. Sans jamais te poser la question de savoir lequel tu retiendrais pour l'agreg. Tu étais dans une démarche 'apprendre l'algèbre'.
Là, tu as travaillé les dénombrements pendant 3 jours, et tu abandonnes. Tu ne cherches pas à maitriser le chapitre sur les dénombrements, parce que tu sais que tu n'en es pas capable, tu cherches à apprendre par coeur un exercice (de préférence un exercice où tu disposes d'un corrigé détaillé !),un seul exercice, celui que tu présenteras à l'agreg si tu tombes sur cette leçon.

OShine

@lourran
Non, le dénombrement tombe souvent dans les sujets de concours que j'ai traités et la question sur le nombre de partitions d'un entier par exemple tombe très souvent.
Mais si je passe un an sur le dénombrement, comment je pourrais passer l'agreg un jour ? Il y a une centaine de leçons à préparer.
Je vais continuer de faire du dénombrement quand je vais revoir les chapitres de sup et de spé et préparer les autres leçons, il y a beaucoup de dénombrement dans les probabilités.

@bd2017
J'ai fait un erreur en effet.
Oui je serai interrogé sur un exercice sans corrigé, mais avoir la correction ça rassure, si on nous pose une question sur l'exercice qu'on propose.
Je me vois mal présenter un exercice sans corrigé.
Ok je vais essayer de voir une deuxième méthode pour la formule de Vandermonde.

bd2017

@bd2017
J'ai fait un erreur en effet.

Oui mais tu ne corrige pas!

OShine

Il faut choisir les extrémités du rectangle.

• $\binom{2}{n+1}=\dfrac{n(n+1)}{2}$ choix d'extrémités pour le segment horizontal.
• $\binom{2}{p+1}=\dfrac{p(p+1)}{2}$ choix d'extrémités pour le segment horizontal.

Donc : $\dfrac{n(n+1)}{2} \times \dfrac{p(p+1)}{2}$ choix.
Après le jour d'un oral je ne sais pas si ils posent des exos aussi durs que celui de noobey. 

bd2017

Je n'en sais rien. Même si l'exercice est difficile le jury va étudier  la réaction du candidat....et puis au besoin il va donner une indication ...et il va de  nouveau  regarder la réaction du candidat.... et ainsi de suite....

OShine

Formule de Vandermonde par le calcul. C'est une bonne question, pour montrer ses capacités en calculs.
Montrons que : 
$\displaystyle\sum_{k=0}^p \binom{m}{k} \binom{n}{p-k}=\binom{m+n}{p}$
Posons : $P(X)=(1+X)^{m+n}=(1+X)^m (1+X)^n$.
D'une part : 
$\boxed{(1+X)^{m+n}=\displaystyle\sum_{k=0}^{m+n} \binom{m+n}{k}  X^k}$.
D'autre part : 
$(1+X)^m (1+X)^n= \displaystyle\sum_{0 \leq i \leq m \\ 0 \leq j \leq n }  \binom{m}{i}  \binom{n}{j} X^i X^j  $
On a la partition : 
$[|0,n|] \times [|0,m|]= \displaystyle\bigcup_{k=0}^{m+n} \Delta_k$ où $\Delta_k = \{ (i,j) \in [|0,n|] \times [|0,m|] \ | \ i+j=k \}$.
Le théorème de sommation par paquets donne : 
$(1+X)^m (1+X)^n= \displaystyle\sum_{k=0}^{m+n} \displaystyle\sum_{(i,j) \in \Delta_k}  \binom{m}{i}  \binom{n}{j} X^i X^j  $
$\boxed{(1+X)^m (1+X)^n= \displaystyle\sum_{k=0}^{m+n} \left(  \displaystyle\sum_{i=0}^k  \binom{m}{i}  \binom{n}{k-i} \right) X^k }$

En regardant le coefficient du polynôme devant $X^p$, on obtient : 
$ \boxed{\displaystyle\binom{m+n}{p}=  \displaystyle\sum_{k=0}^p  \binom{m}{k}  \binom{n}{p-k}}$

OShine

noobey a dit :

De combien de façons $C(n)$ peut-on décomposer $n$ comme somme décroissante de puissances de $2$ où chaque puissance apparait au maximum $3$ fois?

Par exemple :

$\begin{aligned}8 &= 8 \\&= 4 + 4 \\&= 4 + 2 + 2 \\&= 4 + 2 + 1 + 1 \\&= 2 + 2 + 2 + 1 + 1\end{aligned}$ 

Donc $C(8) = 5$

Je bloque sur cet exercice.
A un oral, je n'aurais rien pu écrire, tableau blanc assuré.

gai requin

L'exercice de @Ericpasloggue .

Soit $\Omega$ l'ensemble des $p$-listes $(c_1,\ldots,c_p)$ de couleurs telles que $\#\{c_1,\ldots,c_p\}\geq 2$.
On a facilement $\#\Omega=a^p-a$.
Soit $G$ le groupe engendré par le cycle $(1\; 2\ldots p)$.
$G$ agit sur $\Omega$ comme on pense.
Sous cette action, le stabilisateur de tout élément de $\Omega$ est trivial donc les orbites sont toutes de cardinal $p$.
Donc $p$ divise $a^p-a$.

Ericpasloggue

Merci Gai Requin, mais pourquoi t'embêter alors que Oshine a annoncé qu'il ne voyait pas le rapport avec Fermat, autrement dit qu'il n'avait pas réfléchi deux secondes à l'exercice que je proposais.

Dans le bouquin de Quinn et Benjamin que je donne en référence, il n'est pas question d'action de groupe (le livre se place à un niveau très élémentaire), mais bien sûr l'idée de la démonstration est celle que tu donnes.

Autre exercice dans le même bouquin deux pages plus loin.

Combien de permutations de $\{0,1,\dotsc,p-1\}$ ont exactement un cycle ? Le but est (bien sûr) de démontrer le théorème de Wilson (je précise puisque Oshine ne fera pas l'effort de réfléchir deux secondes) de façon combinatoire (donc encore une fois, il faut compter de deux façons différentes).

OShine

@gai requin
Merci beaucoup, très intéressant. Un peu d'action de groupe, ça fait 6 mois que je n'y ai pas touché, mais ça revient très vite, j'ai de bons restes. 
Pour $\boxed{\# \Omega=a^p-a}$ c'est clair, il y a $a^p$ liste et on retire les $a$ listes où il y a une unique couleur.
On a $G= \langle (1 \ 2 \ \cdots \ p) \rangle$.
$G$ agit sur $\Omega$ par : $G \times \Omega \longrightarrow \Omega \\ 
(\sigma,c=(c_1, \cdots, c_p) ) \mapsto \sigma. c = (x_{\sigma(1)}, \cdots, x_{\sigma(p)})$
Déterminons le stabilisateur de tout élément de $\Omega$.
Soit $c=(c_1, \cdots, c_p) \in \Omega$.
On a $St_c = \{ \sigma \in \Omega \ | \ \sigma . c =c \}$
$St_c = \{ \sigma \in \Omega \ | \ (c_{\sigma(1)}, \cdots, c_{\sigma(p)}) =(c_1, \cdots, c_p \}\}$
$St_c = \{ \sigma \in \Omega \ | \ \forall i \in [|1,p|] \ c_{\sigma(i)}=c_i \}= \{ id_{S_n} \}$
Le stabilisateur de tout élément de $\Omega$ est donc trivial.
Or, on sait que $\forall c \in \Omega$, on a : $\dfrac{\# G}{ \# St_x}=\# O_x$.
Ainsi : $\boxed{\# O_x= \# G}$.
Mais $(1 \ 2 \ \cdots \ p)$ est un $p$ cycle, donc il est d'ordre $p$. Ainsi, $\# G=p$.
Toutes les orbites sont de cardinal $p$.
Soit $n$ le nombre d'orbites. 
L'équation aux classes fournit $\# \Omega = \displaystyle\sum_{i=1}^n \# O_{x_i}=np$.
Ainsi $a^p-a=np$ donc $\boxed{a^p \equiv a [p]}$.
C'est le petit théorème de Fermat.

OShine

@Ericpasloggue
Je veux bien continuer à réfléchir à ton exercice avec les couleurs, mais déjà je ne comprends pas à quoi sert l'hypothèse $p$ premier. 

OShine

Exercice : 
Combien de permutation de $\{0,1, \cdots, p-1 \}$ ont exactement un cycle ? 

Merci pour cet exercice, avec mon expérience sur le groupe symétrique, j'ai déjà des idées pour résoudre cet exercice.
Je vais commencer par compter le nombre de cycles de longueur $k$, avec $1 \leq k \leq p$.
Puis, quand j'aurais réussi à les dénombrer je n'ai plus qu'à tout sommer.
Par contre, je vais compter que d'une seule façon ici. 

gai requin

@Oshine : Est-ce que $4$ divise $3^4-3$ ?

Si non, c’est que ta démo est au moins incomplète !

OShine

Je crois savoir où on utilise $p$ premier. C'est le théorème de Lagrange.
$G = \langle (1 2 \cdots p) \rangle$.
$(1 2 \cdots p)^p= id$ avec $p$ premier donc $(1 2 \cdots p)$ est d'ordre $p$ donc $\# G=p$.

Amédé

Salut,

un exercice intéressant est de compter les classes d'équivalence par les différentes actions de groupes sur les espaces de matrices.

OShine

gai requin a dit :

@Oshine : Est-ce que $4$ divise $3^4-3$ ?

Si non, c’est que ta démo est au moins incomplète !

Je n'arrive pas trop à voir où on utilise que $p$ est premier, il doit y avoir un passage qui m'échappe.

gai requin

Avec tes notations, $St_c$ est un sous-groupe de $G$ donc $St_c=\{I\}$ ou $G$.

biguine_equation

Bonjour,
avez-vous eu connaissance de preuves par dénombrement des deux résultats suivants.
Soit $q=p^n$, $p$ premier.
$\bullet$ $-1$ est un résidu quadratique dans $\mathbb{F}_q$ si et seulement si $q \equiv 1 \pmod 4$.
$\bullet$ $2$ est un résidu quadratique dans $\mathbb{F}_q$ si et seulement si $q \equiv {\pm 1} \pmod 8$.

NB: $x$ est un résidu quadratique dans un corps $K$ si il existe un $y \in K$ tel que $x=y^2$.

J’ai lu un cours à ce sujet et il me semble que l’idée était de créer une partition de $\mathbb{F}_q$ en se servant de l’orbite de l’action du groupe des transformations de Möbius sur $\mathbb{F}_q \cup \{\infty\}$.
Dans le premier cas, si je me souviens bien, le groupe est $G=\{x, -x, 1/x, -1/x \: ; \:  \circ \}$.

bisam

@Oshine : Pour ton exercice 4, si tu invoques le théorème de sommation par paquets, je pense que l'on va te rire au nez et ensuite te soumettre à la question (façon torture moyen-âgeuse !).

Utiliser ce théorème dans le cadre d'une somme finie qui n'utilise par conséquent que la commutativité (et l'associativité, bien entendu... mais sans cela, on n'écrit même pas le symbole $\Sigma$) c'est soit montrer son incompréhension, soit provoquer le jury afin qu'il pose des questions sur les familles sommables.

D'après moi, le seul principe utilisé est le "lemme des bergers".

En revanche, l'astuce utilisant la bijection $(X,Y)\mapsto (X,E\setminus Y)$ pour la deuxième question (voire $X\mapsto E\setminus X$ pour la première) mérite d'être évoquée.

noobey

OShine a dit :

noobey a dit :

De combien de façons $C(n)$ peut-on décomposer $n$ comme somme décroissante de puissances de $2$ où chaque puissance apparait au maximum $3$ fois?

Par exemple :

$\begin{aligned}8 &= 8 \\&= 4 + 4 \\&= 4 + 2 + 2 \\&= 4 + 2 + 1 + 1 \\&= 2 + 2 + 2 + 1 + 1\end{aligned}$ 

Donc $C(8) = 5$

Je bloque sur cet exercice.
A un oral, je n'aurais rien pu écrire, tableau blanc assuré.

Ben je t'ai donné une indication, réfléchis y. Regarde par exemple le monôme de degré 8 du produit...
L'exo est trop dur pour être posé en oral d'agreg interne sans indication, par contre il est de assez bon niveau pour être présenté dans ta leçon une fois l'indication donnée

OShine

@biguine_equation
J'ai ces résultats dans le cours du Liret, mais je mettrais plutôt ça en oral de leçon, j'ai bossé ça déjà quand j'ai travaillé sur le corps $F_p ^{*}$.

OShine

@bisam
Merci pour ta remarque.
J'ai des connaissances sur les familles sommables, mais mieux vaut éviter de me faire coincer là-dessus.
Je n'utilise pas le lemme des bergers... Ce lemme n'est pas évoqué dans le DUNOD, qui n'utilise dans les corrigés que les partitions et la formule permettant de calculer le cardinal d'un ensemble qui est partionné. 

@gai requin 
Ok merci.

bisam

@noobey : $C(n) = \frac{2n+3+(-1)^n}{4}$ ?

biguine_equation

OShine: je ne savais pas que le Liret en causait. Je le consulterai à l’occasion. Mais je crois avoir compris le principe de la démonstration. J’y reviendrai peut-être dans un fil à part.

OShine

noobey a dit :

Petite indication : 

Penser au produit suivant  


$$\prod_{i = 0}^{\infty} (1 + x^{2^i} + x^{2 \times 2^i} + x^{3 \times 2^i})$$

On a $P=(1+x+x^2+x^3)(1+x^2+x^4+x^6)(1+x^4+x^8+x^{12}) \cdots $

Je ne comprends pas pourquoi il y a des $x^{2^i}$ ni le lien exacte avec l'exercice.

noobey

Regarde le monôme de degré 8. Je t'avais donné la liste des possibilités + le nombre de possibilités

OShine

Je ne comprends rien.

noobey

Je comprends pas ce que tu comprends pas, développer et identifier tu sais faire ça depuis la première
Juste trouver le monôme de degré 8 ça devrait pas être dur non?

OShine

Ah d'accord j'avais mal compris.
Ça je sais faire.

noobey

bisam a dit :

@noobey : $C(n) = \frac{2n+3+(-1)^n}{4}$ ?

Oui autrement dit 

$\lfloor n/2 \rfloor + 1$

OShine

noobey a dit :

Regarde le monôme de degré 8. Je t'avais donné la liste des possibilités + le nombre de possibilités

Il y a beaucoup de cas, c'est plus dur que ce que je pensais.
On a rarement des distributivités aussi compliquées à traiter.

OShine

On a :
$P=(1+x+x^2+x^3)(1+x^2+x^4+x^6)(1+x^4+x^8+x^{12})(1+x^8+x^{16} +x^{24}) (1+x^{24}+x^{48}+x^{72}) \cdots$

Je ne vois pas comment trouver le monôme de degré $8$ sans oublier de termes, il y en a beaucoup. 
J'ai déjà passé plus d'une demi-heure sur cette question et je ne m'en sors pas.
J'ai développé les 3 premières parenthèses, mais je ne vois pas la logique.

gerard0

"J'ai développé les 3 premières parenthèses"

Quel fainéant !

Ou quel idiot, puisque la seule chose qui compte c'est d'avoir $x^8$ à la fin ...

OShine

@gerard0
Tu as raison, ce n'est pas dur en fait.

J'ai calculé : 
$(1+x+x^2+x^3)(1+x^2+x^4+x^6)=1+x+2x^2+2x^4+2x^5+2x^6+2x^7+x^8+x^9$
Puis : 
$(1+x+x^2+x^3)(1+x^2+x^4+x^6) (1+x^4+x^8+x^{12}) \\ 
=1+x+2x^2+2x^3+3x^4+3x^5+4x^6+4x^7+4x^8 + Q$ avec $\deg Q >8$

$(1+x+x^2+x^3)(1+x^2+x^4+x^6) (1+x^4+x^8+x^{12}) (1+x^8+x^{16}+x^{24})= \\
1+x+2x^2+2x^3+3x^4+3x^5+4x^6+4x^7+5x^8 + R$ avec $\deg(R) >8$.

Donc le monôme recherché est : $\boxed{M=1+x+2x^2+2x^3+3x^4+3x^5+4x^6+4x^7+5x^8}$

Rescassol

Bonjour,

Il suffit de développer partiellement $(1+x+x^2+x^3)(1+x^2+x^4+x^6)(1+x^4+x^8)(1+x^8)$, ce n'est pas la mer à boire.

Cordialement,
Rescassol

OShine

@Rescassol
Tu es malin, j'ai mis 1 heure à m'en rendre compte   
Je voulais utiliser la formule de distributivité générale, j'ai perdu du temps inutilement.

Rescassol

Bonjour,

Et même seulement $(1+x^2)(1+x^2+x^4+x^6)(1+x^4+x^8)*(1+x^8)$.

Cordialement,
Rescassol

OShine

Oui par contre je ne vois pas en quoi ça aide à résoudre l'exercice avec les puissances de 2.

OShine

J'ai trouvé un autre exercice mais je ne sais pas s'il correspond à cette leçon.
C'est le problème du scrutin.

biguine_equation

Deux ultimes suggestions: une sommation ensembliste et un problème de $p$-listes.

$\bullet$ Soient $X$, un ensemble fini de cardinal $n$ et $E$, l’ensemble des parties de $X$ qui contiennent un élément $x_0$ fixé.
Calculer
\begin{equation}
\displaystyle S=\sum_{A \in E} 2^{\vert A \vert}
\end{equation}

$\bullet$ Soient $n$ et $p$ deux entiers naturels vérifiant $2 \leq p \leq n$. Soit $l$ un entier naturel fixé.
Nombre de $p$-listes $(i_1, i_2,…, i_p)$ d’éléments de $\llbracket 1, n \rrbracket$ qui sont telles que 
\begin{equation}
\forall k \in \llbracket 1, p-1 \rrbracket , \: \: \: i_{k+1} - i_k > l.
\end{equation}
(I.e. entre deux termes consécutifs de ces $p$-listes, il y a la place pour au moins $l$ entiers).

Il existe une version  « circulaire » plus difficile du lemme précédent qui est peut-être plus adaptée à l’agrégation interne.

OShine

@biguine_equation
Merci, mais la leçon c'est "exercices faisant intervenir le dénombrement" et pas des exercices de pur dénombrement. 
Au moins tes exercices sont faisables, contrairement à celui de noobey.

Pour le premier.
$E= \{ X \subset E \ | \ x_0 \in X \}$.
On a $E=\displaystyle\bigcup_{k=1}^n E_k$ avec $E_k = \{ X \in E \ | \ card (X)= k \}$.
On a $S=\displaystyle\sum_{k=1}^n \displaystyle\sum_{A \in E_k} 2^{|A|}$
$S=\displaystyle\sum_{k=1}^n card (E_k) 2^k$.
Il reste à déterminer $card(E_k)$.
Il s'agit des parties de $E$ de cardinal $k$ contenant au moins un élément $x_0$.
Pour créer une telle partie, on choisit $x_0$, $n$ choix, puis on prend $k-1$ éléments parmi les $n-1$ restants dans $E$.
Donc $card(E_k)=n \binom{n-1}{k-1}$.
$S=n \displaystyle\sum_{k=1}^n \binom{n-1}{k-1} 2^k=2 n \displaystyle\sum_{j=0}^{n-1} \binom{n-1}{j} 2^j $
Enfin : $\boxed{S=\displaystyle\sum_{A \in E} 2^{|A|} = 2 \times 3^{n-1} \times n}$

Vérification : 
Soit $E$ un ensemble de cardinal $E$. 
On a $E= \{x_0 \}$.
$S=2^1=2$ et $2 \times 3^{1-1} \times 1=2$, ça semble cohérent.

Ton deuxième exercice est assez dur, je vois pas l'intérêt de le compliquer encore plus. Je ne vois pas pourquoi il faudrait faire encore plus dur pour l'agreg interne.
Pour le deuxième, je compte les $p$ listes, il y en a $n^p$.
Il faut enlever les éléments tel qu'il existe $k \in [|1,p-1|]$ tel que $i_{k+1}-i_k \leq l$.
Et ça je ne sais pas le dénombrer.

OShine

Ericpasloggue a dit :

Merci Gai Requin, mais pourquoi t'embêter alors que Oshine a annoncé qu'il ne voyait pas le rapport avec Fermat, autrement dit qu'il n'avait pas réfléchi deux secondes à l'exercice que je proposais.

Dans le bouquin de Quinn et Benjamin que je donne en référence, il n'est pas question d'action de groupe (le livre se place à un niveau très élémentaire), mais bien sûr l'idée de la démonstration est celle que tu donnes.

Autre exercice dans le même bouquin deux pages plus loin.

Combien de permutations de $\{0,1,\dotsc,p-1\}$ ont exactement un cycle ? Le but est (bien sûr) de démontrer le théorème de Wilson (je précise puisque Oshine ne fera pas l'effort de réfléchir deux secondes) de façon combinatoire (donc encore une fois, il faut compter de deux façons différentes).

Un $k$ cycle s'écrit $(a1 \cdots a_k)$.
Le nombre de cycles de longueur $k$ est $\dfrac{n!}{(n-k)! k}$
Donc le nombre de permutation qui ont exactement un cycle est :    
$\boxed{S=\displaystyle\sum_{k=1}^{n} \dfrac{n!}{(n-k)! k}}$
Cette somme ne se calcule pas.

OShine

@noobey
J'ai trouvé le monôme de degré  $8$ mais je n'ai toujours pas compris comment résoudre ton exercice. 

@bisam
Comment tu as fait ? 

gai requin

Pour le dernier exo de @Ericpasloggue, je trouve que le nombre de cycles vaut $\sum\limits_{k=2}^p (k-1)!\binom p k\equiv (p-1)!\bmod p$.
Soit $G$ le groupe engendré par $(0\;1\ldots p-1)$.
$G$ agit par conjugaison sur l'ensemble des cycles et, comme déjà dit, les stabilisateurs sont de cardinal $1$ ou $p$.
Je trouve que c'est $p$ pour les éléments de $G$ seulement.
Donc il existe $\alpha$ tel que le nombre de cycles vaut $p-1+\alpha p$.

D'où $(p-1)!\equiv -1\bmod p$.

Sans garantie, j'ai gribouillé vite fait...

OShine

@gai requin Remplacer $n$ par $p-1$ dans ma formule. Pas besoin d'action de groupe on peut dénombrer directement.