[<] Dénombrements élémentaires [>] Partition d'un entier

 
Exercice 1  4436  

En écriture binaire, combien de fois utilise-t-on le chiffre «  1  » pour énumérer tous les entiers compris entre 1 et 1 024?

 
Exercice 2  4445  

Soit une relation d’équivalence sur un ensemble E de cardinal n. On suppose que  possède p classes d’équivalence et l’on note q le nombre de couples (x,y)E2 vérifiant xy. Établir n2pq.

 
Exercice 3  4439   

Soit E un ensemble fini à n éléments. Combien existe-t-il

  • (a)

    de relations binaires sur E?

  • (b)

    de relations binaires réflexives et symétriques11 1 Le nombre de relations d’équivalence sur E est l’objet du sujet 4443. sur E?

  • (c)

    de relations binaires réflexives et antisymétriques sur E?

 
Exercice 4  1534   

(Nombre de surjections)

Soient E et F deux ensembles finis non vides de cardinaux respectifs p et n. On note Sp,n le nombre de surjections de E sur F.

  • (a)

    Déterminer Sp,1, Sn,n et Sp,n lorsque p<n.

  • (b)

    On suppose p>1, n>1 et l’on introduit a un élément arbitraire de E. En étudiant la restriction d’une surjection au départ de E{a}, établir

    Sp,n=n(Sp-1,n+Sp-1,n-1).
  • (c)

    En déduire que pour tout entier n1 et tout entier p1,

    Sp,n=k=0n(-1)n-k(nk)kp.
 
Exercice 5  3985   Correction  

On note 𝒮n l’ensemble des permutations de 1;n et 𝒮n(k) le sous-ensemble de 𝒮n constitué des permutations possédant exactement k0;n points fixes. Enfin, on pose

sn(k)=Card(𝒮n(k)).
  • (a)

    Calculer

    k=0nsn(k).
  • (b)

    Soient n,k1. En calculant de deux façons le nombre de couples (s,x) constitués de s𝒮n(k) et x point fixe de s, établir

    ksn(k)=nsn-1(k-1).
  • (c)

    En déduire

    sn(k)=(nk)sn-k(0).
  • (d)

    Retrouver directement le résultat précédent.

Solution

  • (a)

    La somme étudiée dénombre les permutations de 1;n selon leur nombre de points fixes

    k=0nsn(k)=Card(𝒮n)=n!
  • (b)

    Pour chaque permutation de s de 𝒮n(k) il y a k points fixes x possibles. Le nombre de couples cherché est donc ksn(k).
    Pour chaque x1;n, une permutation possédant k points fixes (dont x) est entièrement déterminée par sa restriction à 1;n{x} qui est une permutation à k-1 points fixes. Ainsi, le nombre de couples cherché est aussi nsn-1(k-1).

  • (c)

    En itérant la formule ci-dessus obtenue

    sn(k)=n(n-1)(n-k+1)k(k-1)1sn-k(0)=(nk)sn-k(0).
  • (d)

    Pour déterminer une permutation élément de 𝒮n(k), on choisit l’ensemble de ses k points fixes (il y a (nk) possibilités) et l’on construit ses valeurs sur le complémentaire de l’ensemble des points fixes à partir d’une permutation de n-k éléments sans points fixes (il y a sn-k(0) possibilités). Au total, il y a

    (nk)sn-k(0)

    applications de la forme voulue.

 
Exercice 6  4156     CCP (MP)Correction  

On considère une matrice 3×3 composée de 9 jetons numérotés de 1 à 9.

On cherche à déterminer la probabilité p pour que le déterminant de la matrice soit un entier impair.

  • (a)

    Soit A=(ai,j)n(). Montrer que la classe de congruence du déterminant de A modulo 2 est égale à la classe du déterminant de la matrice dont les coefficients sont les restes ri,j de la division euclidienne de ai,j par 2.

  • (b)

    On note l’ensemble des matrices carrées d’ordre 3 composées des 9 jetons. Déterminer Card().

On définit Ω={M|det(M) impair} et Δ l’ensemble des matrices carrées d’ordre 3 dont cinq coefficients sont égaux à 1, quatre sont nuls et de déterminant impair.

  • (c)

    Donner une relation entre Card(Ω) et Card(Δ).

  • (d)

    On considère une matrice de Δ dont une colonne possède trois coefficients égaux à 1.

    Donner le nombre K1 de ces matrices.

    On considère une matrice de Δ dont deux colonnes possèdent exactement un coefficient nul.

    Déterminer le nombre K2 de ces matrices.

  • (e)

    Calculer Card(Δ) et en déduire Card(Ω).

  • (f)

    Déterminer la probabilité p.

Solution

  • (a)

    Le déterminant de A se calcule par une formule compatible avec le calcul en congruence modulo 2.

  • (b)

    Répartir les jetons dans la matrice revient à déterminer une bijection de 1;9 vers lui-même. On en déduit Card()=9!=362 880.

  • (c)

    À chaque matrice de Ω on fait correspondre une matrice de Δ par calcul des restes ri,j des divisions euclidiennes modulo 2. Pour une matrice de Ω, si l’on permute les jetons impairs d’une part, et les jetons pairs d’autre part, la matrice de Δ obtenue à la fin est la même. On en déduit

    Card(Ω)=5! 4!Card(Δ).
  • (d)

    Formons une matrice de Δ dont une colonne possède trois coefficients égaux à 1. On choisit cette colonne et il reste deux 1 à positionner. Ceux-ci ne peuvent figurer sur la même colonne car on obtient sinon un déterminant nul. Ils ne peuvent figurer sur la même ligne pour la même raison. S’ils ne figurent ni sur la même ligne, ni sur la même colonne, la matrice est convenable. On en déduit

    K1=3×3×2.

    On choisit la colonne comportant un 1 et deux 0, les deux autres colonnes comportant un 0 et deux 1, puis on positionne le 1 dans la première colonne et les deux zéros dans les deux autres. Pour que la matrice obtenue soit de déterminant impair, il faut et il suffit que ces deux derniers zéros ne soient pas choisis sur la même ligne. On en déduit

    K2=3×3×3×2.
  • (e)

    Si une matrice de Δ possède une colonne dont trois coefficients sont égaux à 1, elle ne possède pas deux colonnes possédant exactement un coefficient nul. Aussi, si une matrice de Δ ne possède pas de colonne dont trois coefficients sont égaux à 1, elle possède deux colonnes possédant exactement un coefficient nul.

    Card(Δ)=K1+K2=72 et Card(Ω)=207 360.
  • (f)

    p=4/7.

 
Exercice 7  4442   

(Nombres de Catalan)

Soient n et p deux entiers naturels non nuls.

On appelle chemin monotone, tout déplacement sur une grille de coordonnées entières obtenu en partant de la case (0,0) et en se déplaçant successivement d’une unité vers la droite ou d’une unité vers le haut.

  • (a)

    Combien existe-t-il de chemins monotones rejoignant la case (n,p)?

On s’intéresse désormais aux chemins monotones rejoignant la case (n,n). On dit qu’un tel chemin est sous-diagonal si les cases (x,y) qu’il emprunte vérifient la condition yx.

  • (b)

    On considère un chemin qui n’est pas sous-diagonal et on lui associe un nouveau chemin déterminé en changeant les mouvements vers la droite par des mouvements vers le haut, et inversement, dès son premier franchissement11 1 Ce premier franchissement est nécessairement dirigé vers le haut et peut éventuellement avoir lieu dès le premier déplacement. de la diagonale.

    Quelle nouvelle case rejoint ce chemin?

  • (c)

    Combien existe-t-il de chemins sous-diagonaux rejoignant la case (n,n)?

 
Exercice 8  4443    

(Nombres de Bell)

On appelle partition d’un ensemble E, tout ensemble constitué de parties deux à deux disjointes, non vides et de réunion égale à E. On note Bn le nombre de partitions11 1 Une relation d’équivalence est caractérisée pas ses classes d’équivalences qui constituent une partition de l’ensemble: Bn détermine le nombre de relations d’équivalence sur un ensemble à n éléments. d’un ensemble fini à n* éléments et l’on pose B0=1. Établir que pour tout entier naturel n,

Bn+1=k=0n(nk)Bk.
 
Exercice 9  4444    

(Nombre de dérangements)

Un dérangement sur un ensemble E est une permutation σ de E vérifiant σ(x)x pour tout xE. On note Dn le nombre de dérangements existant sur un ensemble à n* éléments.

  • (a)

    Établir Dn+1=n(Dn+Dn-1) pour tout n2.

  • (b)

    En déduire Dn=nDn-1+(-1)n pour tout n2.

  • (c)

    Conclure

    Dn=n!k=0n(-1)kk!pour tout n1.
 
Exercice 10  5418      MINES (MP)Correction  

Soit n*. Déterminer le nombre moyen de points fixes d’une permutation de l’ensemble 1;n.

Solution

Notons 𝒮n l’ensemble des permutations de 1;n. On sait

Card𝒮n=n!.

Pour σ𝒮n, notons N(σ) le nombre de points fixes de σ

N(σ)=Card{i1;n|σ(i)=i}.

Le nombre moyen de points fixes d’une permutation de 1;n est

M=1n!σ𝒮nN(σ).

Réorganisons le calcul de cette somme en introduisant les couples (σ,i) formés par σ𝒮n et i1;n. Pour un tel couple, posons

δ(σ,i)={1 si σ(i)=i0 si σ(i)i.

On remarque

N(σ)=i=1nδ(σ,i)

et alors

σ𝒮nN(σ)=σ𝒮n(i=1nδ(σ,i)).

On réorganise le calcul de la somme

σ𝒮nN(σ)=i=1n(σ𝒮nδ(σ,i))

avec

σ𝒮nδ(σ,i)=Card{σ𝒮n|σ(i)=i}.

Or, pour i1;n, une permutation σ qui fixe i peut s’identifier à une permutation de 1;n{i}, il y en a exactement (n-1)!. On peut alors achever le calcul

N(σ)=i=1n(n-1)!=n(n-1)!=n!

puis

M=1.
 
Exercice 11  4446    

(Formule d’inversion de Pascal)

Soient n et p des entiers naturels.

  • (a)

    Pour k, tels que kn, comparer (nk)(k) et (n)(n-k-).

  • (b)

    Soient (un)n une suite de nombres réels et (vk)k la suite déterminée par

    vk==0k(k)upour tout k.

    Établir la formule d’inversion

    un=k=0n(-1)n-k(nk)vkpour tout n.
  • (c)

    Application: On note Sp,n le nombre de surjections d’un ensemble E à p éléments sur un ensemble F à n éléments. Déterminer une expression de Sp,n en observant

    np=k=0n(nk)Sp,k.
  • (d)

    Application: On note Dn le nombre de dérangements11 1 Voir le sujet 4444. sur un ensemble à n éléments. Déterminer une expression de Dn en commençant par observer

    n!=k=0n(nk)Dk.
 
Exercice 12  3934    Correction  

Soit n*. On note X l’ensemble de suites (x1,,xn) avec

k{1,,n},xk=1 ou -1.

À chaque suite x=(x1,,xn) élément de X on associe la suite (s0,s1,,sn) avec

s0 et sk=sk-1+xk pour k{1,,n}.

Celle-ci détermine une ligne brisée déterminée par les points de coordonnées (k,sk) comme illustrée ci-dessous

Cette ligne brisée définit un chemin joignant (0,s0) à (n,sn).

  • (a)

    On note p le nombre de 1 dans la suite x=(x1,,xn)X. Exprimer en fonction de n, p et s0 la valeur de sn.

  • (b)

    Étant donnée m, combien existe-t-il de chemin sn=m?

  • (c)

    On suppose s0. En exploitant la figure ci-dessous

    expliquer pourquoi il y a autant de chemins joignant (0,-s0) à (n,m) que de chemins joignant (0,s0) à (n,m) et coupant l’axe des abscisses.

  • (d)

    En déduire le nombre de chemins joignant (0,1) à (n,m) dont tous les points sont d’ordonnées strictement positives.

Solution

  • (a)

    Le nombre de -1 est de n-p et donc sn=s0+p-(n-p)=s0+2p-n.

  • (b)

    Si m-(s0+n) n’est pas un nombre pair, il n’y a pas de chemin solutions.
    Sinon, on introduit p pour lequel m-s0+n=2p.
    Si p<0 ou p>n, on ne pourra trouver de chemin solutions.
    Si 0pn, chemins solutions correspondent aux suites x pour lesquels on positionne p termes 1 et les autres égaux à -1. Il y a (np) positions possibles pour les termes 1 et autant de chemins solutions.

  • (c)

    Tout chemin joignant (0,s0) à (n,m) et coupant l’axe des abscisses peut être associé de façon bijective à un chemin joignant (0,-s0) à (n,m), il suffit pour cela de passer à l’opposer les termes x1,x2, jusqu’au premier pour lequel s0+x1++xk=0 et ne pas modifier les autres comme dans la figure proposé (ce résultat est connu sous le nom de principe de réflexion).

  • (d)

    Si m-1+n est impair, il n’y a aucun chemins possible d’aucune sorte.
    Sinon, on peut écrire m-1+n=2p avec p et il y a alors (np) chemins possibles (ce nombre étant nul lorsque p<0 ou p>n).
    Parmi ceux-ci, on retire ceux coupant l’axe abscisse qui par l’étude au dessus sont au nombre de (np+1).
    Finalement, il y a

    (np)-(np+1)

    chemins solutions

[<] Dénombrements élémentaires [>] Partition d'un entier



Édité le 08-11-2019

Bootstrap Bootstrap 3 - LaTeXML [LOGO] - Powered by MathJax Powered by MathJax