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

OShine

Bonjour,

Comme je revois entièrement le cours de sup, je me dis qu'en même temps je peux commencer à préparer des leçons et cette dernière me semble correspondre à ce que je viens de réviser.
Je viens de revoir le cours + démos + tous les exercices du chapitre de MPSI sur le dénombrement.

J'ai une question : est-ce mal vu si je présente que des exercices de niveau maths sup dans cette leçon ? 
J'ai beaucoup d'idées d'exercices qui me semblent très intéressants et qui ne sont pas triviaux.
En maths spé, avez-vous des idées pour des domaines où sont présents les dénombrements ? 

Merci d'avance.

Milas

Bonjour oshine
Regarde sur la page de preparation a l'agregation interne de grenoble 2025 il y a un petit polycopie sur le denombrement 

OShine

Bonjour, 
Je n'ai pas besoin de cours sur le dénombrement, j'ai déjà un cours très clair dans le dunod.
Mais j'aimerais savoir s'il faut forcément mettre du dénombrement avec des groupes, groupes quotients, actions de groupes ou bien on peut se limiter à des dénombrements de niveau maths sup - L1.
Ma liste d'exercice comporte des exercices difficiles.

OShine

Je pensais mettre ces deux exercices pour commencer.
L'exercice 2 aborde les listes et les partitions.
L'exercice 1 permet de travailler les partitions, les parties d'un ensemble, le cardinal de l'ensemble des parties, la formule du binôme, les bijections, les applications et l'image réciproque.
C'est un exercice extrêmement riche.

Exercice 1 : 
Soit $E$ un ensemble fini de cardinal $n$. Dénombrer le nombre de couples $(A,B)$ de parties de $E$ tels que $A \subset B$ de deux manières différentes.

Exercice 2 : 
Pour $(n,p) \in \N^{*} \times \N$, on note $u_{n,p}$ le nombre de $n$-listes $(x_1, \cdots, x_n)$ d'entiers naturels telles que $x_1+\cdots +x_n=p$.
Montrer que, pour tout $n \geq 2$ et $p \in \N$ : 
$u_{n,p}=\displaystyle\sum_{k=0}^p u_{n-1,k}$.

Santanni

Bonjour,

Dans cette leçon, je pense qu'un exercice de théorie des graphes serait bien placé : voir l'exercice 9.27 page 103-104 de ce document : https://webusers.imj-prg.fr/~georges.skandalis/AlGenLin.pdf . Ce document est dans la bibliothèque numérique fournie le jour J.

Edit : Dans une leçon d'exercices il est attendu une certaine progressivité dans les exercices proposés, donc tes exercices conviennent je pense. Attention quand même à penser aux recasages, typiquement ton premier exercice je ne vois pas trop où le recaser, alors que l'exercice du document peut être utilisé dans la leçon sur les puissances de matrices. Un autre sujet un peu classique sur cette leçon ce sont les nombres de Bell, recasable aussi.

Bonne journée

ybreney

Bonjour,

@OShine: la question n'est pas de savoir si l'exercice est facile ou difficile (ce qui est d'ailleurs en partie subjectif), mais de savoir si ta sélection d'exercices, sans prétendre à l'exhaustivité, permet de faire le tour de la notion et si chaque exercice est pertinent, la présentation doit d'ailleurs mettre l'accent sur pourquoi tel ou tel a été choisi.

Suivant l'intitulé, on peut très bien s'en sortir - au sens avoir une note très correcte - avec des exercices loin d'être stratosphériques.

Cela a été mon cas il y a quelques années avec la leçon actuellement numérotée 314.

Au final, c'est évident mais il ne faut pas oublier que l'agrégation est un concours de recrutement de professeurs.
Dans son quotidien, un professeur ne choisit pas un exercice parce qu'il est facile ou difficile mais bien parce qu'il lui semble adapté à ce qu'il veut faire comprendre à ses élèves.

Cordialement.

Y.

pozzar

Salut, et comme c'est un concours, ta note dépendra aussi de la prestation des autres (niveau, et qualité) ce qui est imprévisible : moralité, présenter des exercices de ton niveau, et croiser les doigts...
Personne ne peut te dire avec certitude que si tu mets tels exercices, tu auras telle note !
Une sélection jolie sur le papier mais mal présentée (mal justifié, mal résolu, bref mal maîtrisé) vaudra moins qu'une présentation plus modeste, mais où le candidat maîtrise...

Dom

J’ose croire qu’à l’oral, le jury est moins dupe que lorsqu’il lit une copie. 

OShine

@Santanni
J'ai regardé l'exercice mais si je présente cet exercice je suis foutu. Je ne comprends rien à l'exercice et au corrigé qui utilise des matrices d'adjacence, je n'ai pas de connaissances en théories des graphes. 
Je pense que c'est une mauvaise idée compte tenu de mes connaissances. 
Enfin, il me semble beaucoup trop compliqué par rapport à mon niveau.
PS : je n'apprécie pas spécialement les ouvrages de Mr Skandalis, que je trouve trop fouillis.

@ybreney
Ah d'accord merci.

Je comptais faire ensuite.

Exercice 3 : formule de Vandermonde.
L'intérêt de l'exercice est de calculer une somme, utiliser les coefficients binomiaux, utiliser le dénombrement pour calculer une somme.
On utilise les partitions, la symétrie du coefficient binomial, le changement d'indice dans une somme.
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{m}{k} ^2=\binom{2n}{n}$.

OShine

pozzar a dit :

Salut, et comme c'est un concours, ta note dépendra aussi de la prestation des autres (niveau, et qualité) ce qui est imprévisible : moralité, présenter des exercices de ton niveau, et croiser les doigts...
Personne ne peut te dire avec certitude que si tu mets tels exercices, tu auras telle note !
Une sélection jolie sur le papier mais mal présentée (mal justifié, mal résolu, bref mal maîtrisé) vaudra moins qu'une présentation plus modeste, mais où le candidat maîtrise...

Oui, je veux juste savoir si les exercices ne sont pas trop faciles, trop difficiles, ou hors-sujet avec la leçon.
Et s'il serait bien par exemple, de mélanger le dénombrement et les espaces vectoriels ou la théorie des groupes.

OShine

Dom a dit :

J’ose croire qu’à l’oral, le jury est moins dupe que lorsqu’il lit une copie. 

Je ne présente que des choses que je maitrise, si je ne comprends pas un exercice ou sa correction, je ne le mettrai jamais dans une leçon. 

darbouka

OShine, pour l'oral d'exercices, il faut effectivement maîtriser les exercices que tu présentes, mais il faut aussi maîtriser un minimum le cours portant sur ces exercices; on peut te demander par exemple de citer tel ou tel théorème qui est utilisé dans la résolution de l'exercice

darbouka

Et pour ton commentaire sur les graphes, même si la leçon d'exercices portant sur les graphes a disparu de la liste des leçons, je pense que c'est un thème intéressant. D'une part c'est une notion qui apparaît en terminale, qui n'est pas très difficile à comprendre, et que tu peux recaser dans beaucoup de leçons d'exos; de mémoire j'avais des graphes en dénombrements, en probas, en algèbre (matrices).

OShine

Exercice 4 : 
Soit $E$ un ensemble fini de cardinal $n$.
Calculer :  
1) $\displaystyle\sum_{X \subset E} card (X)$
2) $\displaystyle\sum_{X,Y \subset E } card (X \cap Y)$

On calcule des sommes indexées sur des parties simples et doubles, on utilise le théorème de sommation par paquet,, on utilise la notion de complémentaire d'un ensemble et on utilise le cardinal de l'ensemble des parties de $E$.

Exercice 5 :  
Soit $n \in \N^{*}$.
1) Combien y a-t-il de surjections de $[|1,n|]$ dans $[|1,n|]$ ?
2) Combien y a-t-il de surjection de $[|1,n+1|]$ sur $[|1,n|]$ ? 
3) Combien y a-t-il de surjection de $[|1,n+2|]$ sur $[|1,n|]$.

On aborde la notion de surjection. 
On utilise que si l'ensemble d'arrivée et de départ sont égaux, il y a équivalence entre injection surjection et bijection.
On utilise le cardinal de l'ensemble des bijection d'un ensemble fini de cardinal $n$.
Il est conseillé de faire un dessin en petite dimension pour comprendre le dénombrement des questions 2 et 3. 
On calcule avec des factorielles pour simplifier le résultat final. 

Le dernier est difficile.
Exercice 6 :  
On considère $n$ poteaux numérotés de $1$ à $n$ sur lesquels on veut répartir $r$ drapeaux distincts. 
Chaque poteau peut accueillir un nombre quelconque de drapeaux entre $0$ et $r$. 
Lorsqu'un poteau accueille plusieurs drapeaux, on tient compte de l'ordre dans lequel les drapeaux sont disposés sur ce poteau. 
1) On suppose $r=2$ et $n=2$. De combien de façons peut-on disposer les drapeaux sur les poteaux ? 
2) Même question dans le cas général. On pourra raisonner par récurrence sur $r$.

Cet exercice fait le lien entre le dénombrement et les récurrences.
On commence par comprendre l'exercice sur un exemple en petite dimension, puis en posant $u_{n,r}$ le nombre recherché on trouve une relation de récurrence entre $u_{n,r}$ et  $u_{n,r-1}$.
A la fin, on calcule $u_{n,r}$ de proche en proche. 
Cet exercice nécessite d'introduire des notations, comme $d_i$ le nombre de drapeaux sur le $i$-ième poteau, on utilise aussi encore une partition pour obtenir la relation de récurrence.

 

OShine

darbouka a dit :

OShine, pour l'oral d'exercices, il faut effectivement maîtriser les exercices que tu présentes, mais il faut aussi maîtriser un minimum le cours portant sur ces exercices; on peut te demander par exemple de citer tel ou tel théorème qui est utilisé dans la résolution de l'exercice

Oui j'ai entièrement revu le cours de dénombrement avant de préparer cette leçon d'exercices.

OShine

@darbouka
Possible mais je n'ai jamais étudié de cours sur les graphes et le DUNOD n'aborde pas cette notion.
Le problème des graphes et qu'il faut introduire plein de notions et définitions, mais on est sur la leçon dénombrement, je ne comprends pas comment on peut mettre un exo sur les graphes dedans sans s'éparpiller.
L'exercice du Skandalis est incompréhensible si on n'a pas de bases sur les graphes comme moi.

OShine

Sinon il faut trouver un exo sur les graphes qui redéfinit les notions, mais dans le skandalis l'exercice ne définit rien.

Champagne

@oshine, "faisant intervenir" n'est pas "sur le". Qu'il y ait un voire deux exercices sur le dénombrement, genre échauffement rappel pour les suivants, pourquoi pas. Mais selon moi, il faut dans ta fiche des exercices dans lesquels on n'attend pas a priori d'avoir à utiliser le dénombrement.

Santanni

@OShine : Je t'assure que l'exercice ne nécessite aucune connaissance en théorie des graphes, il suffit juste de comprendre ce qu'est une matrice d'adjacence, le reste c'est de l'algèbre linéaire. 

Attention à ne pas te faire de fausses idées sur les bouquins : certains peuvent paraître trop difficiles (comme les X-ENS) mais possèdent quelques démonstrations très utiles pour les oraux, il serait dommage de s'en passer.

OShine

@champagne
Intéressante ta remarque.
Auriez-vous un exemple d'un exercice dans lequel on ne s'attend pas d'avoir à utiliser le dénombrement ? 
Il faut que je regarde du côté des probabilités ?  
J'ai en stock un exercice intéressant sur le problème du scrutin, mais il est difficile.

OShine

@santanni
D'accord je suis votre conseil, normalement je suis à l'aise en algèbre linéaire.
Je vais revoir calmement l'exercice.

Ericpasloggue

J'ouvre mon Proofs that really count de Benjamin et Quinn, MAA, 2003 (parce que tant qu'à parler de dénombrement, autant utiliser une référence qui compte vraiment...), et je vois page 115 : combien y a-t-il de façon de colorier les éléments de l'ensemble $\{1,\dotsc,p\}$, où $p$ est un nombre premier, avec un ensemble de $a$ couleurs, de sorte que tous les éléments ne soient pas colorier avec la même couleur ?

Comme toute démonstration combinatoire, il s'agit de compter de deux façons différentes.

Question subsidiaire (pour Oshine) : quel théorème s'agit-il de démontrer dans la situation exposée ci-dessus ?

OShine

@Ericpasloggue
Je ne sais pas, ton exercice semble très difficile.

Ericpasloggue

Tu demandes un exercice, je t'en donne un et tu viens couiner... comme d'hab ! Dommage pour le théorème de Fermat.

OShine

Je ne vois pas le rapport avec le théorème de Fermat. 
Sans corrigé ou questions intermédiaires, malheureusement cet exercice est hors de portée de mon niveau.

OShine

@Champagne
J'ai trouvé un exercice très intéressant dans le Liret qui utilise le dénombrement et qui est très riche au niveau des connaissances : arithmétiques, morphismes, groupes, groupes cycliques, sous-groupes, corps $F_p ^{*}$, théorème d'isomorphisme.

Exercice : 
Soit $p$ un nombre premier et $n$ un entier positif. On se propose de compter le nombre de puissances n-ièmes dans $\mathbf{F}_p ^{*}$.
Soit : $f : \mathbf{F}_p ^{*} \longrightarrow \mathbf{F}_p ^{*}$ l'application définie par $f(x)=x^n$ et soit $P= \{ x^n \ : \ x \in \mathbf{F}_p ^{*} \}$. 
1) Montrer que $f$ est un morphisme de groupes. En déduire que $P$ est un sous-groupe de $\mathbf{F}_p ^{*}$.
2) Montrer que pour tout $x \in \mathbf{F}_p ^{*}$, on a l'équivalence : 
$x^n=1 \iff x^{pgcd(n,p-1)}=1$. 
3) Montrer que $\ker (f)$ possède $pgcd(n,p-1)$ éléments.
En déduire : $card (P)=\dfrac{p-1}{pgcd(n,p-1)}$.

Demain, j'essaierai de voir si je ne trouve pas d'autres exercices de qui utilisent le dénombrement sans se focaliser uniquement sur le dénombrement. 

LeVioloniste

Il y a des classiques comme les nombres de Bell ou de Catalan.
C’est en lien avec les séries.
on peut trouver ces exos dans les X-ENS. 

À voir si cela te convient.

OShine

@LeVioloniste
D'accord, mais les XENS tout le monde les prend je veux me démarquer des autres candidats et prendre des exercices qui ne sont pas choisis.

J'ai trouvé un exercice dans le Liret (un de mes livres préférés) encore, très intéressant et de niveau assez consistant.
J'espère qu'il n'est pas hors-sujet avec le titre de la leçon.
Exercice : 
Soit $n$ et $p$ des entiers au moins égaux à $2$.
1) Montrer qu'il existe un morphisme de groupes surjectif $\Z / n \Z \longrightarrow \Z / p \Z$ si et seulement si $n$ est un multiple de $p$.
2) Montrer qu'il existe un morphisme de groupes injectif $\Z / n \Z \longrightarrow \Z / p \Z$ si et seulement si $n$ divise $p$.
3) Montrer que le nombre de morphismes de groupes $\Z / n \Z \longrightarrow \Z / p \Z$ est $pgcd(n,p)$.

LeVioloniste

Je ne suis pas convaincu que cela soit du dénombrement.
Plutôt en lien avec l’arithmétique.

Après au jury on aime bien les classiques maîtrisés.

noobey

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$

OShine

J'ai un exercice sur la loi de réciprocité quadratique mais j'ai peur de viser trop haut car il fait bien maîtriser le corps $F_p ^{*}$.
Sinon j'ai trouvé aussi un exercice intéressant sur les anneaux quotients.

C'est fou comme préparer une leçon d'exercice fait travailler, je viens de revoir plein de choses en algèbre et arithmétique mais ça revient vite, j'avais ça ancré dans ma mémoire.

OShine

Trouver le nombre de morphisme ce n'est pas du denombrement ?
J'ai besoin d'autres avis svp.

OShine

@noobey
Très intéressant ton exercice.

noobey

Petite indication : 

Penser au produit suivant  


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

OShine

Pas compris l'indication. 
J'ai réfléchi à l'exo 15 minutes en mangeant.
Un dénombrement direct me paraît impossible car on ne connaît pas le nombre de termes de la somme à chaque fois.
Ca ressemble à l'exercice sur le nombre de partitions d'un entier (déjà très dur) en plus difficile encore.
Il faut raisonner par récurrence je pense. Mais ça me semble extrêmement difficile.
Car même passer de $n$ à $n+1$ me semble compliqué.

bd2017

Bonjour J'ai un exercice de collège à donner.... On a un tableau rectangulaire de longueur $n$ et $p$ (entiers) quadrillé par   carré de 1 unité. Combien ce tableau contient-il de rectangles?

C'est peut être trop simple mais à la limite ça peut passer pour le jury qui préfèrera des exercices que le candidat sait faire. Présenter des exos qui dépassent son niveau, ça ne sert à rien.

biguine_equation

Pour l’agrégation interne, ça me semble jouable.

$\bullet$ Compter le nombre de matrices $n \times n$ à coefficients dans $\mathbb{Z}/p\mathbb{Z}$ dont les valeurs propres sont dans $\mathbb{Z}/p\mathbb{Z}$, $p$ premier.

$\bullet$ Un exercice qui mêle dénombrement et arithmétique. 
Soit $p$ premier impair et $a \not \equiv 0 \pmod p$. Nombre de solutions de la congruence 
\begin{equation}
(x+y+z)^2 \equiv 2axyz \pmod p
\end{equation}

OShine

@bd2017
Dans ma liste quels exos dépassent mon niveau ?
Je n'ai choisi que des exercices à mon niveau.

biguine_equation

Nombre de matrices $X$ de taille $m \times m$ sur le corps fini à $q$ éléments telles que $X^2 - I=0$.

biguine_equation

Si il y avait des groupes en sup et en spé, un exercice original serait de se demander pour quels nombres $n$ il est possible de dénombrer $n$ éléments d’ordre $n$ dans un groupe fini $G$. 
C’est une question simple qui permet d’utiliser des notions basiques comme les classes d’équivalence. 
Il est intéressant de voir des notions abstraites « en action » quand elles sont appliquées à des cas concrets de dénombrement.

LeVioloniste

Ils sont intéressants tes exos @biguine_equation.

biguine_equation

Merci LeVioloniste. Disons qu’ils changent des classiques du genre comme trouver le cardinal de $GL_n(F_q)$ et ils n’exigent que des notions élémentaires.
Il y a d’autres sources d’inspiration (sur le thème du dénombrement)sur la chaîne YT de Caldéro.

lourrran

L'exercice que tu présentes ici, il a un avantage, c'est que tu peux aussi le préparer pour la leçon algèbre. Un seul exercice à préparer au lieu de 2. Si tu le sors pour la leçon 'dénombrement', et que le jury ne voit pas que c'est un 'refus d'obstacle', bingo. Après avoir volé le bac puis le Capes, tu auras volé l'agreg.

jean-éric

Bonjour OS,

Deux exercices :

1° combien y a-t-il de permutations $\sigma$ dans $S_{11}$ telles que $\sigma^5=(1,2)$ ?

2° Soit $X=\left\lbrace 1, \ 2,\dots, \ 100\right\rbrace$.

Déterminer le nombre de paires d'éléments ${a, \ b }$ de $X$ telles que $ab\equiv a+b \ \text{mod}\ 3.$

Je donnerai ma source plus tard.

Jean-éric.

OShine

Merci.
Il y a du denombrement dans les ensembles quotients et aussi dans les actions de groupes.

OShine

lourrran a dit :

L'exercice que tu présentes ici, il a un avantage, c'est que tu peux aussi le préparer pour la leçon algèbre. Un seul exercice à préparer au lieu de 2. Si tu le sors pour la leçon 'dénombrement', et que le jury ne voit pas que c'est un 'refus d'obstacle', bingo. Après avoir volé le bac puis le Capes, tu auras volé l'agreg.

Pas compris l'histoire du refus d'obstacle.

OShine

bd2017 a dit :

Bonjour J'ai un exercice de collège à donner.... On a un tableau rectangulaire de longueur $n$ et $p$ (entiers) quadrillé par   carré de 1 unité. Combien ce tableau contient-il de rectangles?

C'est peut être trop simple mais à la limite ça peut passer pour le jury qui préfèrera des exercices que le candidat sait faire. Présenter des exos qui dépassent son niveau, ça ne sert à rien.

J'ai réussi.

OShine

Par contre l'exercice de noobey me semble infaisable.

OShine

@bd2017
Notons $\mathcal T$ le tableau rectangulaire de taille $n \times p$.
Notons $\forall (i,j) \in [|1,n|] \times [|1,p|] \ C_{i,j} = \{ \text{rectangles de taille} \ i \times j \}$.
On a la partition suivante : $\mathcal T = \displaystyle\bigcup_{i=1}^n \displaystyle\bigcup_{j=1}^p | C_{i,j} |$.
Avec $|C_{i,j}| = i \times j$ car pour construire un rectangle de taille $i \times j$, on choisi $i$ lignes et $j$ colonnes.
Ainsi : $| \mathcal T|= \displaystyle\sum_{i=1}^n \displaystyle\sum_{j=1}^p i \times j$
Un calcul élémentaire donne : $\boxed{| \mathcal T|=\dfrac{n p(n+1)(p+1)}{4}}$.

@biguine_equation
Un ouvrage à recommander qui contient tes exercices ? 

lourrran

 L'histoire du refus d'obstacle, c'est pour dire que dans une leçon sur les dénombrements, à mon avis, on doit aborder des 'vrais dénombrements' (factorielles, arrangements, combinaisons...) ; ton exercice avec une vague question de  partitionnement, c'est juste une arnaque, pour éviter un sujet où tu n'es pas à l'aise.

Mais je n'ai jamais passé l'agreg, et je ne connais pas les règles du jeu. Peut-être que ça peut passer.

OShine

@lourrran
En fait au départ j'ai donné que des exos avec du pur dénombrement mais on m'a dit que l'énoncé était "faisant intervenir du dénombrement" et donc qu'il fallait que je prenne des exercices plus variés.
Après j'ai un bel exo qui traîne avec le problème du scrutin, du pur dénombrement, mais il est assez difficile et très long. 

J'ai trouvé un exercice sympa qui mélange dénombrement et permutations, pas si simple, il y a beaucoup de cas à considérer. Par contre, le corrigé est ultra détaillé et très clair.

Exercice : 
Soit $\tau=(a b)$ une transposition de $S_n$ et $\sigma=(a \ a_1 \cdots \  a_p)$ un cycle de longueur $p+1$ de $S_n$. Donner la décomposition sous forme de produit de cycles à supports disjoints de la permutation $\tau \sigma$.
Comparer le nombre d'orbites de $\sigma$ et celui de $\tau \sigma$.