Dénombrement

Table des matières

1.Calculs de dénombrement 1

2.Calculs par dénombrement 2

3.Le triangle de Pascal 3

3.1.Somme des diagonales montantes 3

3.2.Somme des diagonales descendantes 3

3.3.Somme d'une ligne, un terme sur deux 3

3.3.1.Par combinaison entre la somme et la somme alternée 3

3.3.2.Par dénombrement 3

3.4.Somme verticale 3

3.5.Interversion d'un k=0n( n k )xk 3

3.6.Démontrer que ( 2n n )=k=0n( n k )2 4

3.6.1.Par le dénombrement 4

3.6.2.Par le polynôme (1+x)2n 4

4.Jeux de cartes 4

5.Géométrie 4

6.Applications 5

1.Calculs de dénombrement

  1. Nombre de parties d'un ensemble #E=n contenant un seul élément d'une partie de E donnée #A=p (avec donc pn).

    Réponse : p×2n-p

  2. Anagrammes de MATHEMATIQUES (sans les accents).

    Réponse : 13!(2!)4 ou ( 13 2 )×( 11 2 )×( 9 2 )×( 7 2 )×5!

  3. Soit A l'ensemble des nombres s'écrivant usuellement avec exactement 4 chiffres.

    1. cardinal de A :

    2. nombre d'éléments de A ayant une et une seule occurence du chiffre 1 ;

    3. nombre d'éléments de A ayant une et une seule occurence du chiffre 0 ;

    4. nombre d'éléments de A ayant quatre chiffres distincts ;

    5. nombre d'éléments de A ayant au moins un 0 mais aucun chiffre 1 en double.

  4. Nombre de chemins

    a) On pose A(0;0) et B(4;3), on demande le nombre de chemins de A vers B qui suivent le quadrillage (constitué des x=k et des y=kk décrit ) et qui ne descendent ni ne reculent jamais vers la gauche.

    b) Recommencer ensuite avec B(n,p).

    Réponse :

    ( n+p n )

  5. Vous êtes directeur du tournoi de Roland Garros. Il y a 2n joueurs inscrits en simple. De combien de façons f(n) pouvez-vous organiser le premier tour?

    Réponse 1 :

    ( 2n 2 )×( 2n-2 2 )××( 2 2 )=(2n)!2n,

    mais il faudra diviser par n! sinon par exemple (AB)(CD) et (CD)(AB) sont comptés comme deux donc f(n)=(2n)2n×n!.

    Réponse 2 : le premier joueur sur la liste peut avoir (2n-1) adversaires, une fois ces deux rayés de la liste le premier joueur de la liste restante peut avair (2n-3) adversaires donc :

    f(n)=(2n-1)(2n-3)××3×1=(2n)2n×n!.

  6. Pour deux entiers k0 et n1, on pose an,k le nombre de n-uplets (x1,,xn) d'entiers naturels vérifiant x1++xn=k donné. Montrer que :

    an,k=( n+k-1 k ).

    Réponse : On vérifie pour n=1 puis on a tout de suite an+1,k=j=0kan,k-j (on somme sur la valeur possible de xn+1, si elle vaut j alors x1++xn=k-j).

    Ensuite, on écrit qu'il faut, pour l'hérédité, calculer j=0k( n+k-j-1 k-j ) :

    on remarque alors que ( n+k-j-1 k-j )=( n+k-j k-j )-( n+k-j-1 k-j-1 ) et la somme est télescopique et vaut ( n+k k )-0 cqfd.

  7. Nombre de couples (A,B)P(E)2 tels que AB=, avec E={1,,n}.

    Réponse : on somme suivant k=taille de A, alors on trouve :

    k=0n( n k )2n-k=3n,

    qu'on pouvait trouver directement : chaque élément de E est soit dans A, soit dans B, soit dans aucun des deux.

    Variante : nombre de couples (A,B)P(E)2 tels que AB

    C'est pareil, c'est égal au nombre de couples (A,B) avec (A,B) tels que précédemment ; autrement dit, chaque eE est soit dans A, soit dans B\A, soit dans aucun des deux.

2.Calculs par dénombrement

  1. Récurrence du triangle de Pascal

    Démontrer que ( n p )+( n p+1 )=( n+1 p+1 ) par le calcul, puis par dénombrement.

  2. Formule du pion

    Démontrer par le dénombrement que k( n k )=n( n-1 k-1 ).

    Réponse : On dénombre le nombre de parties à k élément de {x1;;xn} contenant x1, il y en a ( n-1 k-1 ).

    On ajoute cela pour tous les xi, on obtient n( n-1 k-1 ) on a comptabilisé toutes les parties à k éléments, sauf que chaque élément a été comptabilisé k fois d'où n( n-1 k-1 )=k( n k ).

    Cette formule se démontre aussi, directement, et facilement.

3.Le triangle de Pascal

3.1.Somme des diagonales montantes

Démontrer que pour tout k0 :

i=0k( k-i i )=uk,

(un) désigne la suite de Fibonacci { u0=u1=1 un+1=un+un-1 ..

3.2.Somme des diagonales descendantes

Calculer ( 15 4 )+( 14 3 )+( 13 2 )+( 12 1 )+( 11 0 ) puis ( n p )+( n-1 p-1 )+( n-2 p-2 )++( n-p 0 )

Réponse : grâce à l'écriture ( v u )=( v+1 u )-( v u-1 ) on a une somme télescopique qui donne ( n+1 p )

3.3.Somme d'une ligne, un terme sur deux

3.3.1.Par combinaison entre la somme et la somme alternée

La suite un=(1,0,1,0,1,) est la moyenne des deux suites an=Cste=1 et bn=(-1)n et donc on a Sn=i=0n[( n i )ui]=2n+02=2n-1.

3.3.2.Par dénombrement

Montrer que :

k( n 2k )=k( n 2k+1 )=2n-1.

Indication : Considérer E=[|1;n|] et e par exemple un élément fixé de E (par exemple e=1). Soit φ: P(E) P(E) qui à AE associe A\{e} ou A{e} selon si e est ou non dans A.

Réponse : Alors, φ étant clairement injective et aussi surjective, on en déduit que globalement E a autant de parties de cardinal pair que de parties de cardinal impair.

3.4.Somme verticale

  1. Montrer que k=0n-p( p+k p )=( n+1 p+1 ).

    Réponse : récurrence sur n, facile, un schéma et un exemple s'imposent :

    ( 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 )

3.5.Interversion d'un k=0n( n k )xk

Soit (xn) une suite donnée. On pose yn=k=0n( n k )xk. Démontrer que :

(-1)nxn=k=0n( n k )(-1)kyk.

Réponse : C'est un exercice de double somme :

k=0n( n k )(-1)kyk = k=0n( n k )(-1)kj=0k( k j )xj = j=0nxjk=jn( k j )( n k )(-1)k = j=0nxjk'=0n-j(-1)k'(-1)j(n-k'-j)!×(k')! = j=0nxj(-1)j1(n-j)!k'=0n-j( n-j k' )(-1)k'

et k'=0n-j( n-j k' )(-1)k' vaut 0 ssi j<n et 1 ssi j=n.

3.6.Démontrer que ( 2n n )=k=0n( n k )2

3.6.1.Par le dénombrement

Réponse : On partitionne un ensemble A à 2n éléments en deux ensembles fixes B et C à n éléments. Toute partie K à n éléments de A peut être décomposée en KB union KC. On a tout de suite :

( 2n n )=k( n k )( n n-k ).

3.6.2.Par le polynôme (1+x)2n

Réponse : (1+x)2n=(1+x)n×(1+x)n, regarder le terme en xn.

4.Jeux de cartes

  1. Dans un jeu de 52 cartes, on demande le nombre de mains de 5 cartes :

    1. total ; réponse ( 52 5 )

    2. contenant 1 et un seul as ; réponse 4×( 48 4 )

    3. contenant au moins 1 valet ; réponse ( 52 5 )-( 48 5 )

    4. contenant au moins un roi et au moins une reine ;

      réponse ( 52 5 )tout-(( 48 5 )aucun roi+( 48 5 )aucune reine-( 44 5 )ni roi ni reine)

5.Géométrie

  1. Nombre maximal An d'intersections entre les diagonales d'un polygone convexe à n sommets.

    Réponse : on ne comptabilisera pas les sommets.

    De chaque sommet partent n-3 diagonales, donc il y a n(n-3)2 diagonales.

    Le nombre d'intersections est le nombre de couples de diagonales, qui vaut a priori ( n(n-3)2 2 ) sauf que les sommets ont été comptés, et même plusieurs fois, et plus exactement ( n-3 2 ) fois. La réponse est donc :

    An = ( n(n-3)2 2 )-( n-3 2 ) = n(n-3)8×(n2-7n+14).

  2. Nombre an de régions du plan délimitées par n droites d1,,dn (on suppose aucun couple de droites parallèles, et aucun triplet de droites concourrantes).

    Réponse :

    a1=2 et dn+1 coupe 1 fois chaque di pour i{1,,n}, ce qui subdivise dn+1 en n+1 intervalles, chacun d'entre eux rajoutant exactement 1 région.

    Partant de là, on a an+1=an+(n+1), d'où :

    an=n2+n+22.

6.Applications

  1. Nombre de bijections φ sur {1,,12} :

    1. total ; Réponse : 12!

    2. vérifiant φ(pair)=pair ; Réponse : (6!)2

    3. vérifiant φ(multiple de 3)=multiple de 3 ; Réponse : 4!×8!

    4. vérifiant les deux points précédents. Réponse : 2!×2!×4!×4!

  2. Nombre d'applications φ sur {1,,12} :

    1. total ; Réponse : 1212

    2. vérifiant φ(pair)=pair ; Réponse : 66×126

    3. vérifiant φ(multiple de 3)=multiple de 3 ; Réponse : 44×128

    4. vérifiant les deux points précédents. Réponse : 22×42×64×124

  3. Nombre de surjections de A={1,,n+1} sur B={1,,n}.

    Réponse :

    nchoix du b particulier×( n+1 2 )choix des deux antécédents de b×(n-1)!le reste=n(n+1)!2

  4. Nombre de surjections de A'={1,,n+2} sur B={1,,n}.

  5. Soit un ensemble #E=n et soit Pkn le nombre de partitions de E en k classes.

    1. Montrer que Pkn=Pk-1n-1+kPkn-1.

    2. Calculer en fonction de Pkn le nombre de surjections de E sur F avec #E=n et #F=p.

    Réponses :

    1. On fixe aE. Alors Pk-1n-1 partitions contiennent {a} tout seul dans sa classe, et kPkn-1 partitions ont pour a une classe de cardinal 2 (on partitionne E\{a} en k classes et on choisit l'une d'elles pour accueillir a.

    2. Il y a p!×Pkn surjections de EF.

    Nombre de surjections de A=[|1,n+1|] vers B=[|1,n|]

    Réponse :

  6. Nombre de surjections de A=[|1,n+2|] vers B=[|1,n|]

    Réponse :

  7. Nombre d'injections de [|1,n|] dans [|1,n+p|]

    Réponse : ( n+p n )

  8. Nombre d'applications/de fonctions de [|1,n|] dans [|1,n|].

    nn applications / p( n p )nn-p fonctions.