[<] Ensemble fini [>] Dénombrements élémentaires

 
Exercice 1  1529  Correction  

Soient E et F deux ensembles finis de cardinaux respectifs n et p.
Combien y a-t-il d’injections de E dans F?

Solution

Si n>p, il n’y a pas d’injections possibles.
Si n=0, il y a une injection: l’application vide.
Si 0<np alors on peut écrire E={x1,,xn} avec les xi deux à deux distincts.
Pour former une injection de E dans F:
On choisit f(x1) dans F: p choix.
On choisit f(x2) dans F{f(x1)}: p-1 choix.

On choisit f(xn) dans F{f(x1),,f(xn-1)}: p-n+1 choix.
Au total, il y a p×(p-1)××(p-n+1)=p!(p-n)! choix.

 
Exercice 2  1531  Correction  

Combien existe-t-il de relation d’ordre total sur un ensemble E à n éléments?

Solution

Une relation d’ordre total sur E permet de définir par numérotation des éléments, une bijection de {1,,n} vers E et inversement.

Par suite, il y a exactement n! relations d’ordre total possibles.

 
Exercice 3  1530  Correction  

Soient E={1,,n} et F={1,,p} avec np.
Combien y a-t-il d’applications strictement croissantes de E vers F?

Solution

Une application f:EF strictement croissante est entièrement déterminée par son image qui est une partie formée de n éléments de F. Il y a (pn) parties à n éléments dans F et donc autant d’applications strictement croissantes de E vers F.

 
Exercice 4  4437   

Soient n, p* et E=1;n.

  • (a)

    Dénombrer les familles strictement croissantes (x1,,xp) d’éléments de E.

  • (b)

    Dénombrer les familles croissantes (x1,,xp) d’éléments de E.

 
Exercice 5  3933   Correction  
  • (a)

    Quel est le coefficient de a2b5c3 dans le développement de (a+b+c)10?

  • (b)

    Même question avec a1k1a2k2apkp dans (a1+a2++ap)n.

Solution

  • (a)

    Dans le développement de

    (a+b+c)10=(a+b+c)(a+b+c)(a+b+c)

    on obtient un terme a2b5c3 en choisissant deux a, cinq b et trois c.
    Il y a (102) choix possibles pour les facteurs dont seront issus les a.
    Une fois ceux-ci choisis, il y a (85) choix possibles pour les facteurs fournissant les b.
    Une fois ces choix faits, les trois facteurs restant fournissent les c.
    Au total, il y a

    (102)(85)=10!2! 5! 3!=2520

    termes a2b5c3 apparaissant lors du développement de (a+b+c)10.

  • (b)

    On reprend le même protocole, pour obtenir

    n!k1!k2!kp!

    si k1+k2++kp=n et 0 sinon.

 
Exercice 6  4438   

(Anagrammes)

Un mot M long de n lettres est constitué de r lettres différentes. La j-ème lettre apparaît pj fois dans le mot M et donc p1++pr=n.

  • (a)

    Combien d’anagrammes différentes du mot M peut-on écrire?

  • (b)

    Dans le développement de (a1+a2++ar)n, quel est le coefficient du terme a1p1a2p2arpr?

 
Exercice 7  4440   

(Nombres de combinaisons avec répétition)

On appelle combinaison avec répétition de longueur p formée d’éléments d’un ensemble E, le choix non ordonné de p éléments dans E avec possibilité de répétitions de ceux-ci11 1 Par exemple, les choix de 1,1,2 ou de 1,2,1 définissent la même combinaison avec répétition de longueur 3 formée d’éléments de {1,2,3,4}.. Combien peut-on former de combinaisons avec répétition de longueur p sur un ensemble à n1 éléments?

 
Exercice 8  1536   Correction  

Soit E un ensemble à n éléments.

  • (a)

    Soit X une partie à p éléments de E.
    Combien y a-t-il de parties Y de E disjointes de X?

  • (b)

    Combien y a-t-il de couples (X,Y) formés de parties disjointes de E?

Solution

  • (a)

    Autant que de parties de EX: 2n-p

  • (b)

    p=0n(np)2n-p=(1+2)n=3n.

 
Exercice 9  1538   Correction  

Soit A une partie d’un ensemble E à n éléments. On pose p=Card(A).

  • (a)

    Combien y a-t-il de parties X de E contenant A?

  • (b)

    Combien y a-t-il de parties X de E à m{p,,n} éléments contenant A?

  • (c)

    Combien y a-t-il de couples (X,Y) de parties de E tels que XY=A?

Solution

  • (a)

    Autant que de parties de EA: 2n-p

  • (b)

    Autant que de parties de EA à m-p éléments: (n-pm-p).

  • (c)

    Une fois X à m éléments contenant A déterminé il y a 2n-m choix de Y possibles et donc
    m=pn(n-pm-p)2n-m=k=0n-p(n-pk)2n-p-k=(1+2)n-p=3n-p.

 
Exercice 10  1537   

Soit E un ensemble à n éléments. Combien existe-t-il de couples (X,Y) constitués de parties de E vérifiant XY?

 
Exercice 11  1532   Correction  

On trace dans un plan n droites en position générale (c’est-à-dire deux d’entre elles ne sont jamais parallèles ni trois d’entre elles concourantes). Combien forme-t-on ainsi de triangles?

Solution

Notons tn le nombre de triangles formés.

t0=t1=t2=0.

Pour n3, former un triangle revient à choisir les trois droites définissant ses côtés:

il y a (n3) possibilités.

Chacune de ses possibilités définit un véritable triangle (car il y a ni concourance, ni parallélisme) et les triangles obtenus sont deux à deux distincts.

Finalement,

tn=(n3).
 
Exercice 12  1540   Correction  

Combien y a-t-il de p-cycles dans le groupe (𝒮n,)?

Solution

Une injection f de p dans n permet de définir le p-cycle (f(1)f(p)).
Inversement, un p-cycle de n peut être définis par exactement p injections différentes.
En vertu du principe des bergers, il y a exactement n!p(n-p)! p-cycles dans 𝒮n.

[<] Ensemble fini [>] Dénombrements élémentaires



Édité le 08-11-2019

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