Comment reconnaître deux nombres premiers jumeaux ?

Deux nombres premiers p et p+2 qui ne diffèrent que de 2 s’appellent une paire de nombres premiers jumeaux. Par exemple, les nombres 3 et 5 forment une paire de nombres premiers jumeaux. Le 14 Septembre 2016, le projet de calcul distribué PrimeGrid annonçait avoir découvert que les nombres

2 \, 996 \, 863 \, 034 \, 895 \times 2^{1 \, 290 \,  000} - 1 et 2 \, 996 \, 863 \, 034 \, 895 \times 2^{1 \, 290 \,  000} + 1

sont eux aussi des nombres premiers jumeaux. Ces nombres, au demeurant gigantesques (ils sont composés de 388 342 chiffres chacun !), sont la plus grande paire de nombres premiers jumeaux qu’on n’ait jamais trouvée !

Si l’on en croît l’annonce officielle de la découverte, on a vérifié que chacun de ces deux nombres est premier en leur appliquant à chacun le test de primalité LLR. Mais saviez-vous qu’il existe une formule très simple et qui tient en une ligne permettant de dire si deux nombres quelconques qui diffèrent de 2 sont des nombres premiers jumeaux ? Bon, c’est vrai que cette formule est peu efficace en pratique comme nous le verrons, mais elle a tout de même le mérite d’exister !

Un critère de gémellité

Voici donc le critère très simple permettant de dire si deux nombres n et n+2 forment une paire de nombres premiers jumeaux:

Soit n>1 un entier naturel. Les nombres n et n+2 sont deux nombres premiers jumeaux si, et seulement si,

4 \times [(n-1)! + 1] + n \equiv 0 \mod [n(n+2)]

Comme vous l’avez peut-être noté, ce critère se rapproche beaucoup du théorème de Wilson (qui dit que n est premier si, et seulement si, (n-1)!+1 \equiv 0 \mod [n]) et ce n’est pas un hasard !

Ce critère ne s'applique pas à Igor et Grichka. Impossible donc de savoir s'ils sont premiers, ni même jumeaux.

Ce critère ne s’applique pas à Igor et Grichka. Impossible donc de savoir s’ils sont premiers, ni même jumeaux.

Quelques exemples

Pour bien comprendre ce critère permettant de déterminer des nombres premiers jumeaux, prenons quelques exemples faciles:

Exemple 1: Si l’on prend n=3 alors n(n+2) = 3 \times 5 = 15. Il s’agit de regarder le nombre 4 \times [(3-1) ! +1] + 3 modulo 15 pour savoir si 3 et 5 forment bien une paire de nombres premiers jumeaux:

4  \times [(3-1) ! +1] + 3 = 4 \times ( 2! +1) + 3 = 4 \times (2+1) + 3 = 15 \equiv 0 \mod [15]

Voilà, nous venons de démontrer en un calcul que 3 et 5 sont bien des nombres premiers jumeaux !

• Exemple 2: Si l’on souhaite montrer que 8 et 10 ne sont pas des nombres premiers jumeaux, prenons n=8 et calculons modulo 8 \times 10 = 80:

4  \times [(8-1) ! +1] + 8 =  20172 \equiv 12 \mod [80]

Comme nous n’obtenons pas 0, c’est qu’il ne s’agissait pas d’une paire de nombres premiers jumeaux. En fait, ni 8, ni 10 n’est premier mais je voulais simplement illustrer le fait que ce critère marche vraiment avec tous les nombres !

• Exemple 3: Prenons l’exemple de 9 et 11, où seul 11 est premier. Puisque n=9, alors n(n+2) = 99 et :

4  \times [(9-1) ! +1] + 9 =  161293 \equiv 22 \neq 0 \mod [99]

et on retrouve bien le fait que 9 et 11 ne forment pas une paire de nombres premiers jumeaux.

Exemple 4: Pour finir, redémontrons que 11 et 13 sont bien des nombres premiers jumeaux en prenant n=11. On a

4  \times [(11-1) ! +1] + 11 = 4 \times ( 3628800 +1 ) + 11 = 14 \, 515 \, 215 

Comme 14 \, 515 \, 215 = 11 \times 13 \times 101 \, 505 (je vous invite à vérifier mes calculs par vous-même !), c’est qu’on a bien

4  \times [(11-1) ! +1] + 11 \equiv 0 \mod[11 \times 13]

Encore une fois, le critère marche !

Vous l’avez sans doute compris, cette formule permet de montrer en une fois que deux nombres qui diffèrent de 2 sont simultanément premiers.

La démonstration (1ère mi-temps)

La démonstration de ce critère va reposer sur le théorème de Wilson que nous avons mentionné plus haut. Puisque ce critère est une équivalence, il s’agit de montrer une implication et sa réciproque.

Le sens direct: Soit n>1 tel que n et n+2 sont deux nombres premiers. Il s’agit de montrer que

4 \times [(n-1)! + 1] + n \equiv 0 \mod [n(n+2)]

Comme n+2 est premier, d’après le théorème de Wilson, nous savons que

(n+1)! + 1 \equiv 0 \mod[n+2]

Or, n \equiv -2 \mod[n+2] et n+1 \equiv -1 \mod[n+2] donc n \times (n+1) \equiv (-1) \times (-2) = 2 \mod [n+2]. Ainsi,

(n+1)! + 1 = (n-1)! \times n \times (n+1) + 1 \equiv 2(n-1)! + 1\mod[n+2]

En reprenant alors l’égalité du théorème de Wilson, on a

2 (n-1)! +1 \equiv 0 \mod[n+2]

Si on quitte le (magnifique) langage des congruences un moment, cela signifie qu’il existe un entier k tel que

2(n-1) ! + 1 = k (n+2) \,\, \, \, (\star)

(gardez bien cette relation à l’esprit, nous allons nous en resservir !). Si on regarde cette égalité modulo n, cela donne

2 (n-1)! + 1 \equiv k ( 0 + 2) \mod[n]

Mais comme n est premier, alors (n-1)! \equiv -1 \mod[n] (toujours d’après le théorème de Wilson !) et donc

2 \times (-1) + 1 \equiv 2 k \mod[n]

Nous venons donc de montrer que -1 \equiv 2k \mod[n]. Autrement dit, il existe un entier q tel que 2k = -1 + qn. Si on reprend alors la relation (\star) et qu’on la multiplie par 2, on obtient

4(n-1)! + 2 = 2k (n+2)

En remplaçant à présent 2k par 1 + qn, on a alors

4(n-1)!  + 2 = (-1 + qn)(n+2)

et en distribuant (n+2) sur (-1 + qn), on en déduit que

4(n-1)! + 2 = -(n+2) + qn(n+2)

qui est encore équivalent à

4 \times [ (n-1)! + 1] + n = q n (n+2)

En revenant au langage des congruences, cela veut exactement dire que

\boxed{4 \times [ (n-1)! + 1] + n \equiv 0 \mod[n(n+2)]}.

Je vous laisse souffler un peu avant d’attaquer la suite. Profitez-en pour faire une petite pause pipi qui fait toujours du bien en milieu d’article.

La démonstration (2ème mi-temps)

Le sens réciproque: On suppose à présent que 4 \times [ (n-1)! + 1] + n \equiv 0 \mod[n(n+2)]. Autrement dit, il existe un entier k tel que

4 \times  (n-1)! + 4 + n = k n(n+2) \, \, \, (\star \star)

a) Commençons par montrer que cela implique que n (et donc n+2) est nécessairement impair. Par l’absurde, si on suppose que n est pair, alors n+2 est lui aussi pair. Nous avons ainsi deux nombres pairs consécutifs, donc il y en a un des deux qui est divisible par 4 (et l’autre non).

Si c’est n qui est divisible par 4 alors n=4q avec avec q <n. Ainsi, la relation (\star \star ) implique que

4 (n-1)! + 4 + 4q = k \times 4q \times (n+2)

En la simplifiant par 4, on a alors (n-1)! + 1 + q = k \times q \times (n+2) ce qui entraîne que q divise (n-1)! + 1 + q. Or, comme q divise q (comme d’habitude, chaque article a sa phrase débile, donc la voici pour celui-là) alors q divise (n-1)! +1. Mais, q divise aussi (n-1)! car q<n. On en déduit que q divise (n-1)! + 1 - (n-1)! = 1. Ainsi, q= 1 et donc n=4. Mais cela n’est pas possible car

4 \times ( (4-1) ! + 1) + 4 = 32 \neq 0 \mod [4 \times 6]

ce qui contredit notre hypothèse de départ. Tout cela montre donc que n n’est pas divisible par 4 et que c’est n+2 qui doit l’être. En d’autres termes, n+2 \equiv 0 \mod [4] et donc n \equiv 2 \mod[4]. Sachant cela, si on regarde la relation (\star \star) modulo 4, elle donne

0 \times (n-1)! + 0 + 2 \equiv k \times 2 \times 0 \mod[4]

c’est-à-dire 2 \equiv 0 \mod [4], ce qui est, bien entendu, fichtrement absurde (si je puis me permettre).

b) Maintenant que nous avons prouvé que n est nécessairement impair, reprenons notre hypothèse de départ: 4 \times [ (n-1)! + 1] + n \equiv 0 \mod[n(n+2)].  En particulier, elle implique que

4 \times [ (n-1)! + 1] + n \equiv 0 \mod[n+2]

car si un nombre est divisible par n(n+2), il est a fortiori divisible uniquement par n+2. Nous pouvons réécrire cela sous la forme

2 \times 2  (n-1)! + 4 + n \equiv 0 \mod[n+2]

Or, nous avions vu plus haut dans cette démonstration (voir le sens direct) que 2(n-1)! \equiv (n+1)! \mod[n+2]. Cela, plus le fait que 4+n \equiv 2 \mod [n+2], nous permet de dire que

2 (n+1)! + 2 \equiv 0 \mod [n+2]

et en factorisant, on a

2 [ (n+1)! + 1 ] \equiv 0 \mod [n+2]

C’est à présent que nous allons utiliser le fait que n+2 est impair: il est donc premier avec 2, ce qui veut dire que 2 admet un inverse modulo n+2. Bref, tout cela permet de simplifier par 2 et on obtient

(n+1)! + 1 \equiv 0 \mod [n+2]

D’après le théorème de Wilson, cette relation entraîne alors que n+2 est premier. Pour montrer que n est lui aussi premier, on suit un raisonnement analogue: de l’hypothèse de départ on tire que

4 \times [ (n-1)! + 1] + n \equiv 0 \mod[n]

comme n \equiv 0 \mod [n], cela est équivalent à

4 \times [ (n-1)! + 1]  \equiv 0 \mod[n]

Comme n est impair, il est premier avec 4 et donc on peut simplifier cette relation par 4, ce qui donne

(n-1)! + 1 \equiv 0 \mod [n]

et donc d’après le théorème de Wilson, n est premier. Les nombres n et n+2 sont bien des nombres premiers jumeaux ! CQFD.

Que donne ce critère en pratique ?

A l’instar du théorème de Wilson, en pratique, ce critère est inutilisable: à cause de la présence d’une factorielle dans la relation, le temps de calcul devient beaucoup trop long lorsque n devient très grand. Il faudrait une éternité (au sens propre) pour montrer que les gigantesques nombres découverts en Septembre dernier sont bien des premiers jumeaux en utilisant ce critère !

Malgré tout, on peut utiliser ce critère pour des nombres d’une taille raisonnable. Par exemple, ce test n’a mis « que » 14 secondes sur mon pauvre petit PC bien frêle pour montrer que 18 409 199 et 18 409 201 sont bien des nombres premiers jumeaux (à eux deux, ils forment la 100 000ème paire de nombres premiers jumeaux). Le programme utilisé se trouve ici.

Ce qui a pris 14 secondes pour mon ordi aurait sans doute pris des mois et des mois pour Euler... Vive les ordinateurs !

Ce qui a pris 14 secondes à mon ordi aurait sans doute pris des mois et des mois à Euler… Vive les ordinateurs !

3ème mi-temps: une généralisation

Le critère que nous avons donné peut se généraliser pour déterminer non plus des paires de nombres premiers jumeaux, mais des triplets de nombres premiers, c’est-à-dire trois nombres premiers de la forme n, n+2 et n+6 (on n’a pas mis n+4 car parmi l’un des trois nombres n, n+2 et n+4 l’un au moins est divisible par 3…). Plus précisément, on peut montrer que

Soit n>1 un entier naturel. Les nombres n, n+2 et n+6 sont trois nombres premiers si, et seulement si,

4320 \times ( 4 \times [(n-1)! + 1] + n ) + 361n(n+2) \equiv 0 \mod [n(n+2)(n+6)]

Par exemple, si on prend n=11:

4320 \times ( 4 \times [(11-1)! + 1] + 11 ) + 361 \times 11 \times ( 11 +2) = 62 \, 705 \, 780 \, 423

et comme 62 \, 705 \, 780 \, 423 = 11 \times 13 \times 17 \times 25 \, 794 \, 233 , cela veut dire que

4320 \times ( 4 \times [(11-1)! + 1] + 11 ) + 361 \times 11 \times 13 \equiv 0 \mod [11 \times 13 \times 17]

Nous avons bien redémontré que 11, 13 et 17 forment un triplet de nombres premiers !

Référence:

Congruences for Sets of Primes, P. A. Clement, The American Mathematical Monthly, Vol. 56, No. 1 (Jan., 1949), pp. 23-25

(Dans cet article, la démonstration de la réciproque du critère est vraiment torchée, pour ne pas dire laissée au lecteur en exercice… L’auteur donne aussi à la fin de son article un critère du même type pour que quatre nombres n, n+2, n+6 et n+8 soient tous premiers !)

Publié dans Arithmétique | Tagué , , , , , , | 2 commentaires

Le Roi des Catalans (2ème partie)

Dans la première partie de cet article, nous nous étions intéressés au problème suivant:

Si on place un Roi sur un échiquier de (n +1) \times (n +1) cases, et s’il ne peut se déplacer que vers la droite ou vers le haut à chaque étape, de combien de façons C_n peut-il aller de la case (0,0) à la case (n,n) sans jamais aller au-dessus de la diagonale principale ?

roi_des_catalans2_rappel_du_problemeNous avions déterminé une relation de récurrence suivie par la suite (C_n), à savoir:

\displaystyle C_{n+1} = \sum_{i=0}^n C_i C_{n-i}

Grâce à celle-ci, nous avions trouvé que, pour un échiquier standard (8 cases sur 8 cases), il y avait C_7 = 429 chemins possibles pour le Roi.

roi_des_catalans2_un_des_429_chemins

Un des 429 chemins possibles pour le Roi sur un échiquier standard.

Dans cette seconde partie, nous allons essayer de déterminer une formule explicite de la suite C_n. Rien de moins !

Rencontre du 3ème type

Plaçons-nous sur un échiquier à (n+1) \times (n+1) cases. Afin de trouver le nombre C_n de chemins du Roi qui ne dépassent jamais la diagonale principale, nous allons commencer par définir d’autres types de chemins qui, eux, seront plus simples à dénombrer. Plus précisément, voici les trois types de chemins que nous allons étudier:

■ Les chemins simples: ce sont les chemins allant de (0,0) à (n,n) sans contrainte particulière (si ce n’est qu’à chaque étape, le Roi ne se déplace que vers la droite ou vers le haut). Nous noterons S_n le nombre total de chemins simples.

Un exemple de chemin simple.

Exemple de chemin simple.

■ Les chemins légaux: ce sont les chemins allant de la case (0,0) à la case (n,n) qui ne dépassent jamais la diagonale principale. Comme nous l’avons dit, nous appelons C_n la nombre total de chemins légaux.

roi_des_catalans2_exemple_de__chemin_legal

Exemple de chemin légal.

■ Les chemins illégaux: ce sont les chemins allant de (0,0) à (n,n) qui dépassent au moins une fois la diagonale principale. Nous noterons I_n le nombre total de chemins illégaux.

Un exemple de chemin illégal. (Mais que fait la police ?)

Un exemple de chemin illégal. (Mais que fait la police ?)

Vous l’avez sans doute compris, notre problème de départ revient donc à déterminer le nombre de chemins légaux C_n. Comme tout chemin simple est soit un chemin légal, soit un chemin illégal, on en déduit la relation suivante:

S_n = C_n + I_n

Ainsi, pour déterminer le nombre C_n, il va nous falloir déterminer le nombre de chemins simples et le nombre de chemins illégaux.

Les chemins simples

Déterminer le nombre S_n de chemins simples va être quelque chose de plutôt… simple (cette blague est tellement drôle que je songe sérieusement à renommer ce blog en blaguedemaths). Lorsque le Roi effectue un chemin simple, il effectue au total exactement n déplacements vers la droite et n déplacement vers le haut. En fait, si on note D chaque fois que le Roi se déplace vers la droite et H chaque fois que le Roi se déplace vers le haut, on peut alors représenter un chemin simple par une suite de 2n lettres contenant n fois la lettre D et n fois la lettre H. Par exemple, sur un échiquier standard (c’est-à-dire pour n=7), voici un exemple de suite représentant un chemin simple du Roi:

D H D D D H H D H H D D H H

et voici le chemin que cette suite représente:roi_des_catalans2_exemple_de_chemin_simple_correspondant_a_une_suite_de_lettres

Si on revient à un échiquier quelconque, on peut dire que déterminer le nombre de chemins simples revient à déterminer le nombre de suites de 2n lettres contenant  n fois la lettre D et n fois la lettre H. Pour choisir une telle suite, on peut commencer par placer n lettres D parmi les 2n emplacements possibles de cette suite. Cela donne {2n \choose n} possibilités. Une fois toutes les lettres D placées, il n’y a guère plus le choix pour placer les H. Ainsi, nous voyons que le nombre de chemins simples vaut

\displaystyle S_n = {2n \choose n}

Les chemins illégaux

Déterminer le nombre de chemins illégaux va nous demander d’être beaucoup plus astucieux. L’idée va être la suivante: puisqu’on ne sait finalement bien dénombrer que des chemins simples, nous allons construire une bijection allant de l’ensemble des chemins illégaux vers l’ensemble des chemins simples d’un certain échiquier qui, lui, sera rectangulaire (et non pas carré !). Plus précisément, à tout chemin illégal, nous allons lui associer un chemin « symétrique » grâce à ce que j’appelle personnellement l’astuce du miroir.

Miroir, mon beau miroir…

Considérons un chemin illégal. Puisqu’il est illégal, il passera à un moment donné par au moins une case située dans la zone interdite et la première case illégale par laquelle il passera aura des coordonnées de la forme (k-1, k).roi_des_catalans2__chemin_illegal_avec_1ere_case_interdite

En fait, la première case de la zone interdite sur laquelle il passera est toujours située sur la petite diagonale allant de (0,1) à (n-1,n):roi_des_catalans2_petite_diagonale

Le « symétrique » de ce chemin illégal désignera le chemin obtenu de la façon suivante:

  • au départ, tant que le chemin illégal n’a pas encore été dans la zone interdite, le chemin illégal et son « symétrique » seront les mêmes;
  • à partir du moment où le chemin illégal entre dans la zone interdite (donc à partir de la case (k-1,k)), on effectue une symétrie axiale par rapport à la petite diagonale pour obtenir le deuxième morceau du chemin « symétrique » (d’où l’expression astuce du miroir).

Voici ci-dessous un exemple sans doute plus parlant que tout mon blabla; à gauche un chemin illégal et à droite son « symétrique »:roi_des_catalans2_chemin_illegal_et_son_symetrique

Comme vous le constatez, il faut tout de même agrandir l’échiquier d’une ligne sur le haut pour obtenir le chemin « symétrique ». Vous remarquez aussi que ce symétrique a toujours pour point de départ la case (0,0) et pour point d’arrivée la case (n-1, n+1) (qui est la case symétrique de la case d’arrivée (n,n) du chemin illégal).

Enfin, dernière remarque importante: quand vous prenez le « symétrique » d’un « symétrique », vous retombez sur votre chemin de départ !

Il ne nous reste plus qu’à montrer que cette opération est une bijection. Plus précisément, nous allons démontrer la proposition suivante:

A tout chemin illégal allant de (0,0) à (n,n) correspond un et un seul chemin simple allant de (0,0) à (n-1,n+1) par l’astuce du miroir.

La démonstration

Tout d’abord, le « symétrique » d’un chemin illégal est bien un chemin simple car lorsqu’on prend le symétrique d’un chemin illégal, chaque déplacement vers la droite sera transformé en un déplacement vers le haut et chaque déplacement vers le haut sera transformé en un déplacement vers la droite. De plus, nous avons déjà expliqué pourquoi les points de départ et d’arrivée du  symétrique sont (0,0) et (n-1,n+1).

Ensuite, nous allons montrer que tout chemin simple allant de (0,0) à (n-1,n+1) est le symétrique d’au moins un chemin illégal (autrement dit, on montre la surjectivité de notre opération de « symétrie »). Si on prend un chemin simple allant de (0,0) à (n-1,n+1), alors il traversera nécessairement la petite diagonale au moins une fois, disons en la case (k-1, k). Si, à partir de ce chemin simple, on prend le chemin obtenu de la  même façon que par la méthode de l’astuce du miroir décrite plus haut, alors le chemin obtenu est bien un chemin illégal (et il va de la case (0,0) à la case (n,n)) dont la première case interdite qu’il franchira est (k-1,k).

Enfin, montrons que chaque chemin simple allant de (0,0) à (n-1,n+1) ne peut pas être l’image de plus d’un chemin illégal (il s’agit donc de l’injectivité). Rappelez-vous que nous avions noté que quand on prend le « symétrique » du « symétrique », on retrouve le chemin de départ. Donc si deux chemins illégaux ont même « symétrique », en prenant le « symétrique » de ce « symétrique » on doit retrouver le chemin initial mais comme un chemin n’a qu’un seul « symétrique », c’est que les chemins de départ étaient identiques !

Nombres de chemins illégaux

 Nous pouvons enfin calculer le nombre I_n de chemins illégaux. Puisqu’il y autant de chemins illégaux que deux chemins simples allant de (0,0) à (n-1,n+1), il suffit de dénombrer ces derniers pour trouver le nombre de chemins illégaux. Or, un raisonnement similaire à ce qu’on a fait plus haut nous dit qu’un chemin simple allant de (0,0) à (n-1,n+1) est une suite de 2n lettres dont n-1 lettres D et n+1 lettres H. Ainsi,

\displaystyle I_n = {2n \choose n-1}

ou encore \displaystyle I_n = {2n \choose n+1}

Les chemins légaux

Le nombre de chemins légaux, c’est-à-dire la réponse à notre problème de départ, est alors facile à déterminer. Puisque

C_n = S_n - I_n

on en déduit que

\displaystyle C_n = {2n \choose n} - {2n \choose n+1}

Ainsi, on a

C_n = \dfrac{(2n)!}{(2n-n)! n!} - \dfrac{(2n)!}{(2n - (n+1)) ! (n+1)!}

donc

C_n = \dfrac{(2n)!}{n! n!} - \dfrac{(2n)!}{(n-1) ! (n+1)!}

En remarquant que (n-1)! (n+1)! = n! n! \times \dfrac{n+1}{n}, on en déduit que:

C_n = \dfrac{(2n)!}{n! n!} - \dfrac{n}{n+1} \times \dfrac{(2n)!}{n! n!}

c’est-à-dire:

\displaystyle C_n = {2n \choose n} - \frac{n}{n+1} {2n \choose n}

En factorisant, on obtient:

\displaystyle C_n = \left( 1 - \frac{n}{n+1} \right) {2n \choose n}

ce qui nous donne enfin la formule tant attendue pour les nombres de Catalan (que nous avons bien mérité d’obtenir après tant d’efforts !):

\boxed{ \displaystyle C_n = \frac{1}{n+1} {2n \choose n} }

Par exemple, pour un échiquier standard (n=7), on obtient

\displaystyle C_7 = \frac{1}{7+1} {14 \choose 7 } = \frac{1}{8}  \times 3432 = 429

ce qui était bien ce qu’on avait déjà trouvé !

Utilisation des nombres de Catalan

On ne retrouve pas les nombres de Catalan seulement sur un échiquier mais aussi dans une multitude de situations ! En fait, si on analyse ce qu’on a fait dans cet article, les nombres de Catalan permettront (entre autres) de dénombrer toute liste d’éléments composée de deux types d’éléments « A » et « B » telle que:

  • il y a autant de A que de B;
  • à chaque étape quand on parcourt la liste de la gauche vers la droite, il y a toujours plus (ou autant) de A que de B

Dans notre exemple, un chemin du Roi qui ne traverse pas la diagonale n’est rien d’autre qu’une suite de n déplacements vers la droite (D) et de n déplacements vers le haut (H) telle qu’à chaque étape, il y a toujours plus (ou autant) de D que de H (si à un moment il y a plus de H que de D, c’est qu’on est entré dans la zone interdite !).

Autre exemple: on voit que les nombres de Catalan permettent de dénombrer facilement le nombre de façons de disposer n paires de parenthèses car lorsqu’on place des parenthèses, il faut que:

  •   il y ait autant de parenthèses ouvrantes « ( » que fermante « ) »
  •   à chaque étape quand on lit une expression de la gauche vers la droite, il y a toujours plus ou autant de parenthèses ouvrantes « ( » que de parenthèses fermantes « ) ».

Ainsi, il y a C_n façons de disposer n paires de parenthèses.

roi_des_catalans2_les_14_facons_de_placer_4_paires_de_parentheses

Les C4 = 14 façons de placer 4 paires de parenthèses.

Un dernier exemple, pour la route…

Un autre exemple un peu moins trivial avec des parenthèses est le suivant: imaginons une opération qui n’est pas associative (par exemple le produit vectoriel). De combien de façons différentes peut-on interpréter le calcul du produit suivant ?

A \times B \times C \times D

Par exemple, une façon d’interpréter ce calcul est:

((A \times B) \times (C \times D))

ou bien:

(A \times (B \times (C \times D))

On peut remarquer que pour se donner une expression, il suffit de savoir où sont placées les parenthèses ouvrantes ainsi que les produits; le reste (les parenthèses fermantes et les variables) est alors entièrement déterminé. Par exemple, si je vous donne l’expression

(\times (( \times \times

alors on place les variables A, B et C à gauche des signes \times et la variable D à droite du dernier signe \times:

(A\times((B\times C \times D

Ensuite, il n’y a plus guère le choix pour placer les parenthèses fermantes de façon à ce que l’expression ait du sens:

(A\times((B\times C) \times D))

(en fait, on commence par fermer la parenthèse ouvrante la plus « intérieure » et on continue comme cela jusqu’à la parenthèse ouvrante la plus « extérieure »).

Tout cela pour dire que, pour se donner une expression valide, il suffit de se donner une suite de ( et de \times telle que:

  • il y a au total autant de parenthèses ouvrantes ( que de symboles \times
  • à chaque étape quand on lit l’expression de gauche à droite, il y a plus ou autant de parenthèses ouvrantes ( que de signes \times

D’après ce qu’on a dit plus haut, le nombre d’expressions de ce type possédant 3 parenthèses ouvrantes et 3 symboles \times est donné par le nombre de Catalan C_3 = 5. Voici toutes les possibilités:

  • ( \times ( \times ( \times
  • ( \times (( \times \times
  • ((\times \times ( \times
  • (( \times ( \times \times
  • ((( \times \times \times

et voici les 5 expressions possibles qu’elles donnent:

  • ( A\times ( B \times ( C \times D)))
  • ( A\times (( B\times C) \times D))
  • ((A\times B) \times ( C \times D))
  • (( A \times ( B\times C)) \times D)
  • ((( A \times B) \times C) \times D)

Bien entendu, on peut généraliser cela de la façon suivante:

Le nombre de façons de parenthéser l’expression x_1 \times x_2 \times \cdots \times x_n est C_{n-1}

Bref, on pourrait parler des nombres de Catalan encore pour longtemps car ils apparaissent souvent lorsqu’on fait du dénombrement ! J’espère juste que le Roi sur son échiquier ne m’en voudra pas trop de l’avoir mis entre parenthèses…

Notes:

Publié dans Dénombrement | Tagué , , , , , | 4 commentaires

Le paradoxe des anniversaires à l’Euro 2016

Vous avez sans doute déjà entendu parlé du paradoxe des anniversaires qui dit que dans un groupe de 23 personnes, il y a 50% de chances pour que deux d’entre elles soient nées le même jour de l’année (mais pas forcément la même année). Ça tombe bien, 23 c’est aussi le nombre de joueurs qui composent chaque équipe lors de l’Euro 2016 !

Dimitri Payet (à gauche) et N'Golo Kante (à droite) sont tous les deux nés le 29 Mars.

Dimitri Payet (à gauche) et N’Golo Kanté (à droite) sont tous les deux nés le 29 Mars.

Démonstration du paradoxe

Avant de parler des joueurs de l’Euro, j’aimerais tout de même qu’on revienne un peu sur le paradoxe des anniversaires et qu’on le démontre car, après tout, il n’a rien du tout d’intuitif.

Commençons par traduire le paradoxe de manière un peu plus mathématique: dire que dans un groupe de 23 personnes au moins deux sont nées le même jour revient à dire que si on choisit 23 nombres au hasard entre 1 et 365, au moins deux sont égaux. Précision: les nombres seront choisis de manière équiprobable entre 1 et 365 (même si, en pratique, ce n’est pas tout à fait exact qu’il y ait autant de gens nés chaque jour de l’année, mais nous en reparlerons).

Quant à la valeur 23, elle est a priori arbitraire, donc au lieu de choisir 23 nombres au hasard entre 1 et 365, nous allons en choisir k et nous allons calculer la probabilité de l’événement « Au moins deux des k nombres choisis sont égaux ». On va même plutôt calculer la probabilité de l’événement contraire — à savoir « Tous les nombres choisis sont distincts » — car cela sera plus facile. Plus précisément:

Propriété: Si on choisit k nombres a_1, a_2, \cdots, a_k au hasard entre 1 et 365, la probabilité qu’ils soient tous distincts est:

\dfrac{365\times 364 \times 363 \times \cdots \times (365 -k +1)}{365^k}

Pour démontrer cette propriété, il faut commencer par déterminer l’univers associé à cette expérience aléatoire. Autrement dit, il faut dire combien il y a de façons de choisir k nombres au hasard entre 1 et 365. Pour cela, remarquons que choisir k nombres revient à choisir une liste (a_1, a_2, \cdots, a_k).  Pour le premier nombre a_1, il y a 365 possibilités; pour le deuxième nombre a_2, il y a aussi 365 possibilités; et ainsi de suite. Au total, cela donne 365 \times 365 \times \cdots \times 365 = 365^k listes possibles.

A présent, dénombrons les listes pour lesquels tous les nombres a_i sont distincts:

  • On commence par choisir un premier nombre a_1: puisque c’est le premier nombre à être choisi, il peut prendre n’importe quelle valeur, ce qui donne 365 possibilités.
  • Choisissons ensuite un deuxième nombre a_2: comme il doit être différent du premier nombre déjà choisi, il y a 364 possibilités de le choisir.
  • Puis, on choisit un troisième nombre a_3: comme il doit être différent de a_1 et a_2, il y a 363 possibilités seulement pour ce nombre.
  • On procède ainsi jusqu’au dernier nombre a_k à choisir. Ce dernier devant être différent des k-1 nombres déjà choisis précédemment, cela donnera 365 – (k-1) = 365 – k +1 possibilités.

En résumé, il y a donc 365\times 364 \times 363 \times \cdots \times (365 -k +1) listes de k nombres qui sont tous distincts. Pour obtenir la probabilité voulue, il faut diviser par le nombre total de listes possibles, ce qui donne une probabilité de

\dfrac{365\times 364 \times 363 \times \cdots \times (365 -k +1)}{365^k}

En passant à l’événement contraire, on a donc:

Propriété: Si on choisit k nombres a_1, a_2, \cdots, a_k au hasard entre 1 et 365, la probabilité p_k qu’au moins deux soient égaux est:

p_k = 1- \dfrac{365\times 364 \times 363 \times \cdots \times (365 -k +1)}{365^k}

En calculant cette probabilité pour différentes valeurs de k, on obtient le graphe suivant:

Anniversaires_Euro_Graphe_des_probabilitesEn particulier, si on prend la valeur k=23, on trouve une probabilité égale à 0,507. Ainsi, dans un groupe de 23 personnes, il y a un tout petit peu plus de 50% de chances que deux d’entre elles soient nées le même jour. Voilà donc qui démontre le paradoxe des anniversaires ! On pourrait alors s’arrêter là, mais tout n’est pas si simple dans la vie…

Non uniformité des naissances

Comme nous l’avons dit, dans la réalité il n’est pas vrai qu’une personne ait la même probabilité de naître chaque jour de l’année. Il y a des jours avec plus de naissances et d’autres avec moins. Par exemple, en France le nombre de naissances par jour est plus élevé au mois de Juillet qu’au mois de Novembre (à croire que les gens font plus l’amour en Octobre qu’en Février !). Est-ce que pour autant notre probabilité de 0,507 est très éloignée de la réalité ? Est-ce que le paradoxe des anniversaires est encore valable en pratique ?

Dans un article intitulé The Uniformity Assumption in the Birthday Problem (voir lien en fin d’article), l’auteur Geoffrey C. Berresford a pris en compte le fait que les naissances ne sont pas exactement uniformément réparties sur une année et a estimé, en se basant sur les statistiques des naissances de l’État de New York, que la probabilité que deux personnes soient nées le même jour dans un groupe de 23 personnes est de 0,5101. Nous pouvons donc dire qu’en pratique, même avec le fait que les naissances ne sont pas tout à fait uniformes, le paradoxe des anniversaires tient toujours !

Anniversaires_Euro_graphe_des_naissances_Etat_de_New_York_1977

Fréquences des naissances par jour de l’année relevées dans l’État de New-York en 1977 (image extraite de l’article de Berresford)

On considérera dans la suite que la probabilité que deux personnes soient nées le même jour dans un groupe de 23 personnes choisies au hasard est de 51%.

Les joueurs de l’Euro 2016

Lors de l’Euro 2016, 24 équipes nationales sont en compétition, chacune étant formée d’un groupe de 23 joueurs. Et si dans chacune d’entre elle on regardait si au moins deux joueurs sont nés le même jour ? C’est ce que j’ai fait à partir des informations données sur cette page Wikipédia qui recense les joueurs de chaque équipe. Voici ce qu’il en ressort:

Pays Joueurs nés le même jour
Albanie Orges Shehi et Arlind Ajeti (25 Septembre)
Allemagne Aucun
Angleterre Kyle Walker et John Stones (25 Mai)
Autriche Aucun
Belgique Kevin De Bruyne et Jason Denayer (28 Juin)
Croatie Mateo Kovačić et Marko Pjaca (6 Mai)
Espagne Koke et David Silva (8 Janvier)
France Dimitri Payet et N’golo Kanté (29 Mars)
Anthony Martial et André-Pierre Gignac (5 Décembre)
Hongrie Barnabás Bese et Péter Gulácsi (6 Mai)
Irlande du Nord Michael McGovern et Shane Ferguson (12 Juillet)
Islande Ragnar Sigurðsson et Ögmundur Kristinsson (19 Juin)
Italie Aucun
Pays de Galles James Chester et Joe Ledley (23 Janvier)
Ashley Williams et James Collins (23 Aout)
Pologne Wojciech Szczęsny et Łukasz Fabiański (18 Avril)
Portugal Anthony Lopes et Eliseu (1er Octobre)
José Fonte, Raphaël Guerreiro et Éder (22 Décembre)
République d’Irlande Aiden McGeady et Stephen Quinn (4 Avril)
République Tchèque Tomáš Vaclík et Marek Suchý (29 Mars)
Roumanie Aucun
Russie Roman Shishkin et Denis Glushakov (27 Janvier)
Aleksei Berezutski et Vasili Berezutski (20 Juin… Ce sont des jumeaux !)
Slovaquie Ján Mucha et Ondrej Duda (5 Décembre)
Suède Robin Olsen et Patrik Carlgren (8 Janvier)
Andreas Isaksson et Zlatan Ibrahimović (3 Octobre. Désolé M. Ibrahimović, mais vous n’avez rien de spécial !)
Suisse Aucun
Turquie Semih Kaya et Yunus Malli (24 Février)
Hakan Balta et Ozan Tufan (23 Mars)
Ukraine Aucun

Comme vous pouvez le constater, il y a 18 équipes sur 24 qui possèdent au moins deux joueurs nés le même jour, ce qui représente 75% des équipes. Le paradoxe des anniversaires prédisait, quant à lui, qu’environ 50% des équipes auraient au moins deux joueurs nés le même jour. Y a pas quelque chose de louche ? Le nombre d’équipes avec des joueurs nés le même jour n’est-il pas un peu élevé ? Ou bien, cette valeur de 75% est-elle normale et n’est que le fruit du hasard ?

« Tu peux pas test »

Pour le savoir, nous allons faire ce qu’on appelle un test d’hypothèse.

1ère étape: Pour faire un test d’hypothèse, on commence par faire une hypothèse (j’écris vraiment des trucs très cons sur ce blog…) dont on veut tester la validité. Cette hypothèse que l’on veut étudier s’appelle l’hypothèse nulle et dans notre cas nous ferons l’hypothèse nulle suivante:

Dans un groupe de 23 joueurs de l’Euro, la probabilité p que deux soient nés le même jour vaut p = 0,51.

Autrement dit, nous allons tester si les joueurs de l’Euro ont des naissances qui ressemblent à celles du reste de la population. Dans un test d’hypothèse, on se donne aussi une hypothèse alternative. Ici, ce sera:

La probabilité précédente est telle que p>0,51.

2ème étape: On se donne, de manière arbitraire, une certaine probabilité de se tromper lors de notre test, qu’on appelle seuil. Le choix le plus courant est un seuil de 5%: cela signifie que si on arrive à la conclusion que l’hypothèse nulle n’est pas valable, cela sera avec une probabilité de 5% de se tromper (et donc 95% de dire vrai).

3ème étape: On reprend les résultats de notre échantillon de 24 équipes de l’Euro qui disait que 18 équipes avaient au moins deux joueurs nés le même jour et nous allons déterminer quelle était la probabilité d’avoir au moins 18 équipes qui ont au moins deux joueurs nés le même jour, dans le cas où on considère que l’hypothèse nulle est vraie. Cette probabilité qu’on souhaite calculer est la fameuse valeur p ou p-value en Anglais.

Pour calculer cette probabilité, on considérera en première approximation que lorsque nous avons étudié les équipes de l’Euro, nous avons fait 24 tirages indépendants de groupes de 23 personnes, chaque tirage ayant une probabilité p=0,51 de donner un groupe où deux personnes au moins sont nées le même jour. Vous l’avez compris, il s’agit ici d’une loi binomiale de paramètres n=24 et p=0,51. Si on note X le nombre d’équipes qui ont au moins deux joueurs nés le même jour, le calcul de la valeur p revient donc à calculer P(X \geqslant 18) (en rouge sur le schéma suivant).Anniversaires_Euro_loi_binomialeCe qui est bien avec la loi binomiale, c’est qu’on sait parfaitement la calculer. Avec une calculatrice, on trouve P(X \geqslant 18) \simeq 0,015.

4ème étape: Pour finir un test d’hypothèse, on confronte la valeur p avec notre seuil:

  • si la valeur p est plus grande que le seuil, alors on ne peut pas rejeter notre hypothèse nulle;
  • si elle est plus petite, c’est que notre hypothèse nulle est fausse et on peut donc la rejeter.

Ici, il est clair que la valeur p de 0,015 est plus petite que notre seuil de 5\% = 0,05. Autrement dit, il y avait moins de 5% de chances d’avoir au moins 18 équipes qui possèdent au moins deux joueurs nés le même jour (ça fait beaucoup d’ « au moins » !). On peut donc affirmer, avec 5% de chances de se tromper, que la probabilité que, dans un groupe de 23 joueurs de l’Euro, deux soient nés le même jour est strictement plus grande que p=0,51. Il y a donc bien quelque chose qui cloche dans les dates de naissance des joueurs de l’Euro !

Enquête en profondeur

Nous venons de voir que la proportion de 75% d’équipes possédant deux joueurs nés le même jour est anormale et elle suppose que la répartition des naissances des joueurs de l’Euro n’est pas conforme à celle de l’ensemble de la population. Pour comprendre pourquoi, il faut se plonger plus précisément dans les statistiques des dates de naissance des 552 joueurs qui participent à cet Euro. Je m’y suis collé et les voici représentées sous forme de graphique:

Anniversaires_Euro_naissances_par_jourJe précise que les jours de l’année vont jusque 366 car il y a un joueur à cet Euro qui est né le 29 Février (il s’agit de Benedikt Höwedes de l’équipe d’Allemagne). On voit qu’il y a quand même plus de naissances dans la première partie de l’année que dans la deuxième. Pour préciser cela, regroupons les dates de naissance par mois de naissance:

Anniversaires_Euro_naissances_par_moisOn voit maintenant clairement que les cinq premiers mois de l’année sont quand même prédominants (même le mois de Février, qui compte pourtant le moins de jours dans l’année, est le 3ème mois avec le plus de naissances). Si on compare avec les mois de naissance dans la population globale en Europe (voir schéma ci-dessous), on remarque qu’il y a une vraie différence.

Anniversaires_Euro_naissances_par_mois_population_globale source: Wikipédia

Tout est relatif

Pourquoi donc la répartition des naissances chez les joueurs de l’Euro n’est pas la même que dans le reste de la population ? Cette question possède une réponse dans un phénomène appelé Relative age effect (l’effet de l’âge relatif en Français). Ce phénomène dit que les personnes nées en début d’année ont plus de chance de devenir footballeurs professionnels que celles nées dans la 2ème partie de l’année. Il est dû au fait que les catégories de jeunes joueurs sont déterminées par l’âge (moins de 15 ans, moins de 16 ans, moins de 17 ans…) et qu’il y a une date-limite qui est le 1er Janvier pour chaque catégorie. Ainsi, dans une même catégorie d’âge, un jeune né en Janvier aura un écart de développement physique et de maturité plus important qu’un jeune né en Novembre ou Décembre (puisqu’ils auront entre 11 mois et un an d’écart !) et il aura donc plus de chance d’être repéré par des recruteurs. Si vous doutez encore de ce phénomène, consultez l’effectif actuel de l’équipe de France des moins de 17 ans et vous remarquerez que tous, sauf deux, sont nés dans les 6 premiers mois de l’année !

L’effet de l’âge relatif est très marqué pour les footballeurs des jeunes catégories d’âge mais tend à s’estomper dans les catégories plus âgées, sans toutefois jamais disparaître complètement. L’effet de l’âge relatif ne concerne d’ailleurs pas que le Football puisqu’on le retrouve dans tout un tas de sport dont le Hockey ou encore le Baseball. Là encore, c’est la présence d’une date-limite qui crée ce phénomène.

Pour revenir au paradoxe des anniversaires, puisque les naissances des joueurs de l’Euro sont plus concentrées sur certains mois, il y avait donc plus de chances que plusieurs d’entre eux soient nés le même jour.

Sur ce, je vous laisse, je retourne regarder les matchs…

Références:

Publié dans Dénombrement, Probabilités | Tagué , , , , , , | 12 commentaires

Le Roi des Catalans (1ère partie)

Un Roi situé sur la case tout en bas à gauche d’un échiquier souhaite (pour des raisons personnelles que nous ne détaillerons pas ici) se rendre sur la case située tout en haut à droite.Roi_des_Catalans_figure_initialeContrairement au jeu d’Échecs où il peut se déplacer d’une case dans toutes les directions, notre Roi ne pourra ici se déplacer que d’une case vers la droite ou d’une case vers le haut à chaque fois.Roi_des_Catalans_deplacements_possibles_du_RoiEn plus de ça, notre Roi ne peut pas aller dans la partie haute de l’échiquier (trop fainéant), c’est-à-dire qu’il devra rester toujours en-dessous ou sur la diagonale principale:Roi_des_Catalans_figure_initiale_contrainte_de_la_diagonale(Remarquez au passage la belle illusion d’optique créée par cette figure…)

Voici donc la question qui va nous intéresser: de combien de façons un Roi sur un échiquier partant de la case la plus en bas à gauche peut-il rejoindre la case la plus en haut à droite en se déplaçant à chaque étape uniquement soit d’une case vers la droite, soit d’une case vers le haut, sans jamais aller au-delà de la diagonale principale ?

Nous verrons que ce problème d’apparence anecdotique renferme en fait une des suites de nombres les plus intéressantes en mathématiques.

Généralisation

En bons mathématiciens que nous sommes, nous voyons qu’il n’y a aucune raison de se restreindre à un échiquier de 8 cases par 8 cases. D’une part, parce qu’il est plus facile de comprendre et de résoudre ce problème si les échiquiers sont plus petits (on peut considérer des échiquiers de 1 par 1, ou de 2 par 2 pour commencer) et d’autre part, parce que vous n’êtes pas curieux de savoir ce qui se passe pour un échiquier de 9, 10 ou même 30 000 cases de côté ? Moi, si…

Si on reformule notre problème de façon plus générale, cela donne: si n est un entier naturel, et si on place le Roi sur un échiquier de (n +1) \times (n +1) cases, de combien de façons peut-il aller de la case (0,0) à la case (n,n) sans jamais aller au-dessus de la diagonale principale ?

Nous appellerons C_n ce nombre de chemins et notre but va être de déterminer le nombre C_7 (qui correspond au nombre de chemins sur un échiquier standard de 8 par 8).

Quelques cas particuliers

Comme on l’a dit, pour comprendre cette suite (C_n) le mieux est encore de regarder comment elle se comporte pour de petites valeurs de n. Je vous propose donc de commencer par voir ce qui se passe pour n=0. Car, non, il n’y a rien de honteux à commencer à n=0. On a tous un ami, ou un proche qui a commencé à n=0 un jour dans sa vie.Roi_des_Catalans_n_egale_0Nous voyons donc qu’il n’y a qu’un seul chemin, celui qui consiste à ne pas se déplacer puisqu’on est déjà sur la case d’arrivée dès le départ ! Ainsi, C_0=1. Passons au cas n=1, qui correspond à un échiquier de 2 par 2:Roi_des_Catalans_n_egale_1_videEt nous voyons facilement qu’il n’y a qu’un seul chemin possible:Roi_des_Catalans_n_egale_1_avec_parcoursNous venons de démontrer, non sans fierté, que C_1 = 1. Et pour n=2 alors ? Eh bien sortons un échiquier de 3 cases sur 3 cases et comptons:Roi_des_Catalans_n_egale_2On voit alors qu’il n’y a que deux chemins possibles donc C_2 = 2.

La marche de l’empereur

Vous pouvez vous amuser à compter tous les chemins pour n=3, 4, 5, mais à partir de n=6 cela commence à devenir fastidieux. Alors imaginez pour n=7… Donc, plutôt que de compter tous les chemins, nous allons plutôt essayer de trouver une relation de récurrence vérifiée par la suite (C_n) afin de laisser le soin à un ordinateur de faire le calcul à notre place (y a pas que le Roi qui est fainéant !)

Supposons que nous connaissions déjà C_0, C_1, C_2, …, C_n et essayons de voir comment en déduire C_{n+1}. Il nous faut pour cela nous placer sur un échiquier à (n+2) \times (n+2) cases:Roi_des_Catalans_echiquier_C_n_plus_1_videTout d’abord, si un chemin va de (0,0) à (n+1, n+1), il passera au moins une fois par la diagonale principale autrement qu’en (0,0) (au pire, en (n+1,n+1)). Considérons un chemin quelconque, et notons k>0 le plus petit entier strictement positif tel que ce chemin passe par la case caca… pardon, (k,k):Roi_des_Catalans_echiquier_C_n_plus_1_CACALOLAinsi, avant la case (k,k) aucune case de la diagonale n’est visitée (hormis (0,0) bien sûr). Après cette case, une ou plusieurs cases de la diagonale pourront être traversées. Notre but va être de dénombrer combien de tels chemins passant par (k,k) sont possibles. Mais avant cela, pour bien comprendre la situation, voici un exemple de tel chemin:Roi_des_Catalans_echiquier_C_n_plus_1_exemple_de_cheminCe chemin peut être décomposé en deux morceaux: un chemin allant de (0,0) à (k,k) (en bleu sur le schéma ci-dessous) et un chemin allant de (k,k) à (n+1,+1) (en vert sur le schéma):Roi_des_Catalans_echiquier_C_n_plus_1_exemple_avec_chemins_bleu_et_vertPour obtenir le nombre total de chemins passant pour la première fois sur la diagonale en (k,k), il suffira de faire le produit du nombre de chemins bleus possibles par le nombre de chemins verts possibles.

Dénombrement des chemins bleus

Pour dénombrer tous les chemins allant de (0,0) à (k,k) qui ne passent par aucune case de la diagonale principale, il faut d’abord remarquer deux choses:

  1. Puisque le Roi ne se déplace que vers la droite ou vers le haut, alors le tout premier déplacement qu’il effectue au départ est nécessairement vers la droite, donc vers la case (1,0).
  2. Pour la même raison, lorsque le Roi arrive à la case (k,k), c’est forcément en provenance de la case située juste en dessous, c’est-à-dire de la case (k,k-1).

Roi_des_Catalans_echiquier_C_n_plus_1_chemins_bleus_cases_forceesPuisque ces deux déplacements sont forcés, pour déterminer le nombre de chemins bleus il suffit de déterminer tous les chemins allant de (1,0) à (k,k-1) qui ne passent pas par la diagonale principale.Roi_des_Catalans_echiquier_C_n_plus_1_chemins_bleus_sous_echiquierCela revient donc à déterminer tous les chemins ne dépassant pas la diagonale principale d’un sous-échiquier à k \times k cases. Par définition, il y a donc C_{k-1} chemins bleus.

Dénombrement des chemins verts

Le dénombrement des chemins verts est beaucoup plus immédiat. En effet, un chemin vert est un chemin allant de (k,k) à (n+1,n+1) qui ne va pas au-delà de la diagonale (mais qui peut tout à fait passer sur celle-ci).Roi_des_Catalans_echiquier_C_n_plus_1_chemins_verts_sous_echiquierIl y a donc autant de chemins verts que de chemins ne dépassant pas la diagonale dans un échiquier de ((n+1)-k+1) \times ((n+1)-k+1) cases, c’est-à-dire C_{n-k+1} chemins, par définition.

Dénombrement final

D’après ce que nous venons de voir, il y a donc C_{k-1} \times C_{n-k+1} chemins allant de (0,0) vers (n+1,n+1) ne passant jamais au-dessus de la diagonale et passant pour la première fois sur celle-ci en (k,k).Roi_des_Catalans_echiquier_C_n_plus_1_denombrement_finalAinsi, si on prend un chemin quelconque, alors:

  • Soit la première case de la diagonale par laquelle il passe est (1,1) (c’est-à-dire k=1), ce qui donne C_{1-1} \times C_{n-1+1} = C_0 \times C_{n} possibilités;
  • Soit la première case de la diagonale par laquelle il passe est (2,2), ce qui donne C_1 \times C_{n-1} possibilités;
  • Soit la première case de la diagonale par laquelle il passe est (3,3), ce qui donne C_2 \times C_{n-2} possibilités;
  • etc.
  • Soit la première case de la diagonale par laquelle il passe est (n+1,n+1), ce qui donne C_n \times C_{0} possibilités.

Puisque tous ces cas sont disjoints, le nombre total de chemins est donc:

C_{n+1}  = C_0 \times C_n + C_1 \times C_{n-1} + C_2 \times C_{n-2} + \cdots + C_n \times C_0

ce qu’on peut réécrire sous la forme plus compacte et plus jolie suivante:

\boxed{ C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i} }

Le calcul pour un échiquier standard

Par exemple, si on souhaite calculer C_3, on écrira:

C_3 = C_0 \times C_2 + C_1 \times C_1 + C_2 \times C_0

Comme nous avions vu que C_0 = 1, C_1 = 1 et C_2 = 2, alors:

C_3 = 1 \times 2 + 1 \times 1 + 2 \times 1 = 5

De la même façon, on peut facilement calculer le nombre chemins sur un échiquier de 8 par 8, mais comme les ordinateurs font ça beaucoup mieux que nous, il est préférable d’écrire un petit programme (non optimal), qui nous dit que C_7 = 429. Et voilà, nous avons la réponse à notre question de départ !

Pour le plaisir, on peut s’amuser à calculer les valeurs suivantes de cette suite:

n C_n
0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
11 58786
12 208012
13 742900
14 2674440

Enquête de satisfaction

Nous avons donc réussi à trouver une formule de récurrence pour la suite (C_n) mais, franchement, pensez-vous vraiment que nous allons nous satisfaire de cela ? Nous valons mieux que ça, voyons… visons plus haut ! Pourquoi ne pas essayer de trouver une formule explicite de cette suite ? C’est ce que nous tenterons de faire dans la deuxième partie de cet article… ce qui nous donnera l’occasion de faire encore plus de dénombrement !

Note:

Les nombres C_n que nous avons étudiés dans cet article s’appellent les nombres de Catalan, du mathématicien Eugènes Charles Catalan, qui, comme son nom ne l’indique pas, était un mathématicien franco-belge.

Publié dans Dénombrement, Nombres | Tagué , , , , , , , | 8 commentaires

Séries géométriques, géométriquement !

Prenez un nombre x (disons positif), et formez la somme de toutes les puissances de x:

x^0 + x^1 + x^2 + x^3 + \cdots + x^n + \cdots

Vous calculez alors ce qu’on appelle la somme de la série géométrique de raison x. Par exemple, la somme de la série géométrique de raison x=\frac12, est:

1 + \dfrac12 + \dfrac14 + \dfrac18 + \cdots + \dfrac{1}{2^n} + \cdots

Les séries géométriques sont connues depuis très longtemps et apparaissent un peu partout en mathématiques (par exemple, pour montrer que tôt ou tard vous gagnerez au Loto !). En fait, on les connaît tellement bien qu’on sait même calculer leur somme. En effet, on peut montrer que pour 0 \leqslant x <1:

\boxed{ 1+x+x^2 + \cdots + x^n + \cdots = \dfrac{1}{1-x} }

(En fait, cette formule est valable même pour -1<x<1, mais nous ne nous occuperons pas des x négatifs dans cet article. Et si x \geqslant 1 ? la somme tend grossièrement vers +\infty, donc nous ne nous en occuperons pas non plus…)

Tout ça est bien beau mais comment prouver cette formule pour les séries géométriques ? Eh bien, grâce à de la géométrie ! (ce qui est quand même la moindre des choses, vu leur nom…)

Le cas 1/2

Commençons par un cas particulier, celui de la somme de la série géométrique de raison x=\frac12. Si on en croit la formule précédente, nous devrions trouver que:

1 + \dfrac12 + \dfrac14 + \dfrac{1}{8}\cdots = \dfrac{1}{1-\frac12}=2

Voyons voir comment montrer géométriquement cette égalité. Pour cela, commençons par considérer un carré de côté 1. Ce carré a donc pour aire totale 1:series_geometriques_de_raison_un_demi-carre_1Coupons ce carré en deux:
series_geometriques_de_raison_un_demi-carre_2L’aire en rouge vaut donc \frac12. Coupons à nouveau en deux la partie restante en blanc:series_geometriques_de_raison_un_demi-carre_3Comme l’aire en blanc valait \frac12 à l’étape précédente, quand on la coupe en deux, elle devient \frac12 \times \frac12 =\frac14. On recommence ainsi de suite, et on coupe en deux à chaque fois la partie restante:series_geometriques_de_raison_un_demi-carre_4Si on découpe indéfiniment le carré, nous voyons que l’aire totale en rouge sera de \frac12 + \frac14 + \frac18 + \cdots Comme cette aire en rouge va remplir tout le carré (qui a pour aire 1, rappelons-le), on peut affirmer que:

\dfrac12 + \dfrac14 + \dfrac18 + \cdots = 1

et donc :

1 + \dfrac12 + \dfrac14 + \dfrac18 + \cdots  = 2

Joli, n’est-ce pas ? Mais inutile… car cette démonstration, aussi élégante soit-elle, ne se généralise pas très bien au cas d’une série géométrique de raison x quelconque (essayez par exemple de couper le carré en 3 à chaque étape, vous verrez que vous ne remplirez jamais tout le carré…). Certes, il existe des découpages du carré qui permettent de prouver la formule dans le cas général (voir figure ci-dessous) mais, hormis pour x=\frac14, je ne les trouve pas géométriquement très parlants (si tant est que cette phrase ait un sens… et si tant ait que vous partagiez mon opinion !).

series_geometriques_Proof_without_words

Source: https://www.maa.org/sites/default/files/Ajose61740393.pdf
Je ne sais pas pour vous, mais la figure de droite ne me parle pas du tout…

Je vous ai quand même promis une preuve géométrique en début d’article (oui, je vends du rêve !), donc il va falloir trouver autre chose. On va changer de stratégie: au lieu d’utiliser la notion d’aire, nous allons plutôt utiliser la notion de distance.

Une figure étrange…

Voici la figure que nous allons utiliser pour déterminer la somme de la série géométrique de raison x:series_geometrique_demonstration_par_les_distances_fig_1_figure_de_base

Si vous n’êtes pas convaincu que cette figure permettra bel et bien de calculer la somme 1+x+x^2 + \cdots, attendez de voir la suite…

Expliquons tout de même comment construire cette figure: tracez un segment horizontal [OA] de longueur 1, puis, à partir de A, construisez un segment vertical [AB] de longueur x (où x représente la raison de notre série géométrique). Vous obtenez donc un triangle OAB rectangle en A. Ensuite, à partir de A, prolongez le segment [OA] en un segment [AC] de longueur 1. Et à partir de C, tracez un segment vertical [CD] de longueur 1 lui aussi:series_geometrique_demonstration_par_les_distances_fig_2_explication_de_la_construction

A partir de là, prolongez les demi-droites [OB) et [AD). Elles se coupent en un point P. Le point N est défini alors comme le pied de la perpendiculaire à (OA) passant par P:series_geometrique_demonstration_par_les_distances_fig_3_explication_de_la_construction_suite

(Remarque: vous comprenez sans doute à ce moment-là que les demi-droites [OB) et [AD) ne se coupent en un point P que si x<1; je vous laisse méditer là-dessus pour le moment…)

Il se trouve alors que le triangle APN est isocèle. Si vous voulez vous en convaincre, un petit coup de théorème de Thalès donne  \frac{AC}{AN}= \frac{CD}{PN} c’est-à-dire \frac{1}{AN}=\frac{1}{PN} donc AN=PN.

Quel est l’intérêt de cette figure ?

Si on était dans un repère, on dirait que la droite (OP) a pour coefficient directeur x et que la droite (AP) a pour coefficient directeur 1.

series_geometrique_demonstration_par_les_distances_fig_4_intepretation_coefficient_directeur

Vous vous souvenez peut-être qu’au collège, votre prof vous a dit que pour trouver graphiquement le coefficient directeur d’une droite, il faut partir d’un point de cette droite, se décaler d’une unité horizontalement vers la droite et alors la distance (algébrique, c’est-à-dire positive ou négative) qu’il faut parcourir verticalement pour retomber sur la droite est le coefficient directeur.

On en déduit la propriété suivante:

Propriété 1: Si on part d’un point de la droite (OP) et qu’on se déplace horizontalement d’une distance y, alors il faut se déplacer verticalement d’une distance y \times x pour revenir sur cette droite.series_geometrique_demonstration_par_les_distances_fig_5_propriete_1

Dans un repère, cette propriété peut se comprendre de la façon suivante: puisque la droite (OP) a pour coefficient directeur x, un vecteur directeur de cette droite est \begin{pmatrix} 1 \\ x\\  \end{pmatrix} donc pour tout y non nul , le vecteur y \times \begin{pmatrix} 1 \\ x\\  \end{pmatrix} = \begin{pmatrix} y \\ y \times x\\  \end{pmatrix} est aussi un vecteur directeur de cette droite.

On a une propriété équivalente pour l’autre droite:

Propriété 2: Si on part d’un point de la droite (AP) et qu’on se déplace verticalement d’une distance y, alors il faut se déplacer horizontalement d’une distance y pour revenir sur cette droite.series_geometrique_demonstration_par_les_distances_fig_6_propriete_2

Voilà, avec tout cela, nous sommes prêts à démontrer la formule sur la somme de la série géométrique de raison x.

La démonstration tant attendue…

Pour démontrer la formule à partir de cette figure, nous allons faire une petite balade… nous allons partir du point O pour arriver au point P de la façon suivante:

Étape 1: On part de O et on se déplace horizontalement de 1 unité.series_geometrique_demonstration_par_les_distances_fig_7_deplacement_etape1

Étape 2: On se déplace ensuite verticalement jusqu’à revenir sur la droite (OP). Puisqu’on était parti de cette droite à l’étape précédente et qu’on s’était déplacé de 1 unité, la propriété 1 précédente nous dit qu’il faut se déplacer de 1 \times x = x unités pour retomber sur la droite.series_geometrique_demonstration_par_les_distances_fig_8_deplacement_etape2

Etape 3: On se déplace ensuite horizontalement jusqu’à atteindre la droite (AP). Mais puisqu’à l’étape précédente nous étions partis de cette même droite (AP) et que nous nous étions déplacés de x unités verticalement, alors la propriété 2 nous dit que pour rejoindre (AP), il faut se déplacer de x unités horizontalement également.series_geometrique_demonstration_par_les_distances_fig_9_deplacement_etape3

Etape 4: On se déplace verticalement jusqu’à rejoindre la droite (OP). Puisqu’à l’étape précédente on s’était déplacé horizontalement de x unités horizontalement, la propriété 1 nous dit que pour rejoindre (OP), il faut se déplacer de x\times x = x^2 unités verticalement.series_geometrique_demonstration_par_les_distances_fig_10_deplacement_etape4

Etape 5: On se déplace horizontalement de façon à rejoindre la droite (AP). Comme à l’étape précédente on s’était déplacé de x^2 verticalement en partant de (AP), la propriété 2 nous dit qu’il faut aussi se déplacer horizontalement de x^2 pour rejoindre cette droite:series_geometrique_demonstration_par_les_distances_fig_11_deplacement_etape5

Bon, inutile de faire plus d’étapes, je pense que vous avez compris le principe. Voici la belle figure obtenue lorsqu’on répète indéfiniment ces déplacements:series_geometrique_demonstration_par_les_distances_fig_12_figure_finale

Intéressons-nous à présent à la distance totale parcourue horizontalement: lorsqu’on s’est déplacé de O à P, la distance qu’on a balayée horizontalement est

1+x+x^2+x^3 + \cdots + x^n + \cdots

Il s’agit de la somme des distances de tous les segments en rouge sur la figure précédente. Mais, le déplacement horizontal total effectué quand on va de O à P est aussi égal à la longueur du segment [ON], d’où:

1+x+x^2+x^3 + \cdots + x^n + \cdots = ON

Il nous faut donc déterminer la distance ON. Pour cela, reprenons notre configuration de départ:series_geometrique_demonstration_par_les_distances_fig_1_figure_de_baseD’après le théorème de Thalès, on a:

\dfrac{OA}{ON} = \dfrac{AB}{PN} \Rightarrow \dfrac{1}{ON} = \dfrac{x}{PN}

mais comme PN = AN = ON-OA= ON-1, on en déduit que:

\dfrac{1}{ON} = \dfrac{x}{ON-1}

donc: ON \times x = ON-1, c’est-à-dire 1 = ON (1-x) d’où:

\boxed{ON = \dfrac{1}{1-x}}

ce qui prouve bien que 1+x+x^2+x^3 + \cdots + x^n + \cdots = \dfrac{1}{1-x}.

Source:

Cette image dont je ne sais même pas de quel bouquin elle est extraite ! N’hésitez pas à me le dire si vous le savez…

(Finalement, la référence a été trouvée et elle a été donnée par « none » dans les commentaires)

Ajout:

Il y a quand même une chose que l’on a affirmée dans cette démonstration et qui mérite qu’on s’y attarde un peu: c’est l’égalité 1+x+x^2+\cdots+x^n+\cdots=ON (qui signifie que quand on part du point O, on arrive bien au point P et on ne s’arrête pas avant). Pour la prouver, nous allons évaluer la différence ON- (1+x+x^2+\cdots+x^n), qu’on appelle reste partiel:series_geometrique_demonstration_par_les_distances_fig_13_reste_partielCe reste partiel correspond à la distance RE sur la figure. D’après le théorème de Thalès appliqué au triangle PAN, on a:

\dfrac{PE}{PA}=\dfrac{RE}{AN}

Mais d’après le théorème de Thalès appliqué cette fois-ci au triangle POA, on a:

\dfrac{PE}{PA}=\dfrac{EF}{OA} \Rightarrow \dfrac{PE}{PA}=\dfrac{x^n}{1}

On en déduit que \dfrac{RE}{AN} = \dfrac{x^n}{1}, et donc, le reste partiel de cette série vaut : RE = x^n \times AN. Comme la suite (x^n) tend vers 0, cela veut bien dire que 1+x+x^2+\cdots+x^n+\cdots=ON.

Bonus (quand y en a plus, ben y en a encore): Comme ON- (1+x+x^2+\cdots+x^n) =RE on en déduit que:

1+x+x^2+\cdots+x^n = ON - RE = ON -  x^n\times AN  = ON - x^n (ON-1)

donc:

1+x+x^2+\cdots+x^n = ON (1-x^n) + x^n

Or, on a vu que ON = \dfrac{1}{1-x}, donc

1+x+x^2+\cdots+x^n = \dfrac{1-x^n}{1-x} + x^n

ce qui donne la formule bien connue de la somme partielle d’une série géométrique:

\boxed{ 1+x+x^2+\cdots+x^n = \dfrac{1-x^{n+1}}{1-x} }

Publié dans Géométrie | Tagué , , , , , , | 18 commentaires