NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 07/07/2014

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Partitions

 

Débutants

Algèbre

Fonctions GÉNÉRATRICES

 

Glossaire

Partition

 

 

INDEX

 

Partition

 

Introduction

Nombres entiers

Diviseurs

Principales FG

Partitions

 

Sommaire de cette page

>>> PARTITIONS formées de nombres différents - Pd

>>> Quantité de Pd

>>> Généralisation

>>> La complète

 

 

 

 

FONCTIONS GÉNÉRATRICES

des QUANTITÉS de PARTITIONS des NOMBRES

 

Nous savons qu'une fraction simple engendre tous les nombres entiers

 

Existe-t-il une fraction qui donne des renseignements sur les partitions des nombres?

 

OUI, mais la formule se complique juste un petit peu

Voyons cela pas à pas…

 

 

 

-Ý-   PARTITIONS formées de nombres différents

 

§  Nous nous intéressons aux partitions des nombres et

Ø  plus particulièrement aux partitions formées de nombres tous différents.

 

n

Partitions

PartDif

 

1

1

1

Une partition avec 1 nombre

2

2

1 + 1

1

Une partition avec 1 nombre

Deux fois le même nombre

3

3

2 + 1

1 + 1 + 1

1

1

Une partition avec 1 nombre

Une partition avec 2 nombres différents

Trois fois le même nombre

4

4

3 + 1

2 + 2

2 + 1 + 1

1 + 1 + 1 + 1

1

1

etc.

5

5

4 + 1

3 + 2

3 + 1 + 1

2 + 2 + 1

2 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1

1

1

1

 

6

6

5 + 1

4 + 2

4 + 1 + 1

3 + 3

3 + 2 + 1

3 + 1 + 1 + 1

2 + 2 + 2

1

1

1

 

 

1

 

 

 

 

 

Première partition

avec 3 nombres différents

7

7

6 + 1

5 + 2

5 + 1 + 1

4 + 3

4 + 2 + 1

4 + 1 + 1 + 1

3 + 3 + 1

3 + 2 + 2

1

1

1

 

1

1

 

 

 

§  Comptons la quantité de partitions de nombres différents

§  Nous venons de constituer une table qui donne la quantité de partitions en nombres différents des nombres de 1 à 7

Par exemple 6 se décompose en

Ø  1 partition avec 1 chiffre

Ø  2 partitions ayant chacune deux nombres différents

Ø  1 partition ayant trois nombres différents

Ø  Soit Pd(6) = 4
 

n

Total

Notation

1

1

Pd(1)

2

1

Pd(2)

3

2

Pd(3)

4

2

Pd(4)

5

3

Pd(5)

6

4

Pd(6)

7

5

Pd(7)

 

 

§  Prenons le polynôme suivant:

(1 + x) (1 + x2) (1 + x3) … (1 + x8)

 

§  Développons en ordonnant les monômes selon le degré de x ®

Comparez les coefficients obtenus aux nombres du tableau des partitions ci-dessus

Identique!

 

§  C'est Euler qui a découvert cette relation

1 

    + 1 x1

    + 1 x2

    + 2 x3

    + 2 x4

    + 3 x5

    + 4 x6

    + 5 x7

Tableau limité à x7

 

 Formule pour des partitions formées de nombres différents

Il existe un polynôme qui, une fois développé,

donne la quantité des partitions formées de nombres différents

 

 Pd (n) = Õn=1¥ (1 + xn)

                = (1 + x) (1 + x2) (1 + x3) …

 

Généralisation

 

Pdifférents et pairs (n) = Õn=1¥ (1 + x2n)

Pdifférents et impairs (n) = Õn=1¥ (1 + x2n+1)

Pdifférents et carrés (n) = Õn=1¥ (1 + x)

 

 

 

-Ý-   QUANTITÉ de PARTITIONS

 

§  Reprenons le tableau des partitions

Ø  en distinguant la quantité de nombre utilisé pour chaque partition.

 

n

Partitions

1 nbdif

2 nbdif

3 nbdif

 

1

1

1

 

 

 

2

2

1 + 1

1

 

 

Une partition avec 1 nombre

3

3

2 + 1

1 + 1 + 1

1

 

1

 

Une partition avec 1 nombre

Une partition avec 2 nombres différents

 

4

4

3 + 1

2 + 2

1

 

1

 

 

5

5

4 + 1

3 + 2

3 + 1 + 1

1

 

1

1

 

 

6

6

5 + 1

4 + 2

4 + 1 + 1

3 + 3

3 + 2 + 1

3 + 1 + 1 + 1

1

 

1

1

 

 

 

 

 

1

 

 

 

 

 

Première partition

avec 3 nombres différents

7

7

6 + 1

5 + 2

5 + 1 + 1

4 + 3

4 + 2 + 1

4 + 1 + 1 + 1

3 + 2 + 2

1

 

1

1

 

1

 

 

 

 

 

1

 

 

 

§  Comptons la quantité de partitions de nombres différents

§  Nous venons de constituer une table qui donne la quantité de partitions en nombres différents des nombres de 1 à 7

Par exemple 6 se décompose en

Ø  1 partition avec 1 chiffre

Ø  2 partitions ayant chacune deux nombres différents

Ø  1 partition ayant trois nombres différents
 

n

1 nbdif

2 nbdif

3 nbdif

Total

1

1

 

 

1

2

1

 

 

1

3

1

1

 

2

4

1

1

 

2

5

1

2

 

3

6

1

2

1

4

7

1

3

1

5

 

 

§  Prenons le polynôme suivant:

(1 + xz) (1 + x2z) (1 + x3z) … (1 + x8z)

 

§  Développons en ordonnant les monômes selon le degré

Ø  de x en ligne

Ø  de z en colonne

§  Comparez les coefficients obtenus aux nombres du tableau des partitions ci-dessus

Identique!

 

§  C'est encore Euler qui a découvert cette relation

1                                            

      + 1 x1 . z1                          

      + 1 x2 . z1                        

      + 1 x3 . z1    + 1 x3 . z2   

      + 1 x4 . z1    + 1 x4 . z2   

      + 1 x5 . z1    + 2 x5 . z2   

      + 1 x6 . z1    + 2 x6 . z2    + 1 x6 . z3

      + 1 x7 . z1    + 3 x7 . z2    + 1 x7 . z3

Tableau limité à x7

 

 Formule pour les quantités de partitions formées de nombres différents

Il existe un polynôme qui, une fois développé,

donne la quantité des partitions formées de nombres différents

 

 Pdq (n) = Õn=1¥ (1 + xnz)

                = (1 + xz) (1 + x2z) (1 + x3z) …
                =  1 + xz + …  + j . xk rh + …  

 

Le coefficient j indique la quantité de partitions du nombre k

en exactement h nombres différents

 

 

 

 

 

-Ý-   GÉNÉRALISATION

 

§  Voyons maintenant la totalité des partitions

n

Partitions

Total

1

1

1

2

2

1 + 1

2

3

3

2 + 1

1 + 1 + 1

3

4

4

3 + 1

2 + 2

2 + 1 + 1

1 + 1 + 1 + 1

5

5

5

4 + 1

3 + 2

3 + 1 + 1

2 + 2 + 1

2 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1

7

6

6

5 + 1

4 + 2

4 + 1 + 1

3 + 3

3 + 2 + 1

3 + 1 + 1 + 1

2 + 2 + 2

11

7

7

6 + 1

5 + 2

5 + 1 + 1

4 + 3

4 + 2 + 1

4 + 1 + 1 + 1

3 + 2 + 2

3 + 2 + 1 + 1

15

En résumé

n

Total

Notation

1

1

P(1)

2

2

P(2)

3

3

P(3)

4

5

P(4)

5

7

P(5)

6

11

P(6)

7

15

P(7)

 

 

§  Prenons le polynôme suivant:

(

1

) (

1

) (

1

) (

1 – x

1 – x2

1 – x3

§  Développons en sachant que le calcul peut se faire en se souvenant que:

1 / (1 – x )  = 1 + x + x2 + x3 + x4 + …

1 / (1 – x2) = 1 + x2 + x4 + x6 + x8 +…

1 / (1 – x3) = 1 + x3 + x6 + x9 + x12 +…
etc.

§  Conservons les premiers monômes en les ordonnant selon le degré de x ®

Comparez les coefficients obtenus aux nombres du tableau des partitions ci-dessus

Identique!

 

§  C'est toujours Euler qui a découvert cette relation

1 

    +   1 x1

    +   2 x2

    +   3 x3

    +   5 x4

    +   7 x5

    + 11 x6

    + 15 x7

    + 22 x8

    + 30 x9

    + 42 x10

    etc.

 

 

 

 Formule des partitions

Il existe un polynôme qui, une fois développé,

donne la quantité totale des partitions des nombres

 

 P (n) = Õn=1¥ 1 / (1 - xn)

                = 1 / { (1 + x) (1 + x2) (1 + x3) … }

 

Généralisation

 

Ppairs (n)    = Õn=1¥ 1 / (1 - x2n)

Pimpairs (n) = Õn=1¥ 1 / (1 - x2n+1)

Pcarrés (n)  = Õn=1¥ 1 / (1 - x)

 

 

 

-Ý-   LA COMPLÈTE

 

Combien de partitions formées d'une quantité donnée de nombres

Pselon quantité (n)  = Õn=1¥ 1 / (1 - xn . z)

                                  =  1 + xz + …  + j . xk rh + …  

 

Le coefficient j indique la quantité de partitions du nombre k

en exactement h nombres

 

Voici la table donnant les développements jusqu'à 10

1

 

 

 

 

 

 

 

 

 

+ 1 x1 . z1

 

 

 

 

 

 

 

 

 

+ 1 x2 . z1

+ 1 x2 . z2

 

 

 

 

 

 

 

 

+ 1 x3 . z1

+ 1 x3 . z2

+ 1 x3 . z3

 

 

 

 

 

 

 

+ 1 x4 . z1

+ 2 x4 . z2

+ 1 x4 . z3

+ 1 x4 . z4

 

 

 

 

 

 

+ 1 x5 . z1

+ 2 x5 . z2

+ 2 x5 . z3

+ 1 x5 . z4

+ 1 x5 . z5

 

 

 

 

 

+ 1 x6 . z1

+ 3 x6 . z2

+ 3 x6 . z3

+ 2 x6 . z4

+ 1 x6 . z5

+ 1 x6 . z6

 

 

 

 

+ 1 x7 . z1

+ 3 x7 . z2

+ 4 x7 . z3

+ 3 x7 . z4

+ 2 x7 . z5

+ 1 x7 . z6

+ 1 x7 . z7

 

 

 

+ 1 x8 . z1

+ 4 x8 . z2

+ 5 x8 . z3

+ 5 x8 . z4

+ 3 x8 . z5

+ 2 x8 . z6

+ 1 x8 . z7

+ 1 x8 . z8

 

 

+ 1 x9 . z1

+ 4 x9 . z2

+ 7 x9 . z3

+ 6 x9 . z4

+ 5 x9 . z5

+ 3 x9 . z6

+ 2 x9 . z7

+ 1 x9 . z8

+ 1 x9 . z9

 

+ 1 x10.z1

+ 5 x10.z2

+ 8 x10.z3

+ 10 x10.z4

+ 6 x10.z5

+ 5 x10.z6

+ 3 x10.z7

+ 2 x10.z8

+ 1 x10.z9

+ 1 x10.z10

 

Exemple

n = 6

Prendre la ligne x6

Le nombre 6 peut être partitionné en

1 somme de 1 nombre

3 sommes de 2 nombres

3 sommes de 3 nombres

2 sommes de 4 nombres

etc.

§  Note pour ceux qui voudraient effectuer le développement:

1 / (1 – xz )  = 1 + xz + x2z2 + x3 z3 + x4 z4 + …

1 / (1 – x2 z) = 1 + x2 z + x4 z2 + x6 z3 + x8 z4 +…

1 / (1 – x3 z) = 1 + x3 z + x6 z2 + x9 z3 + x12 z4 +…
etc.

 

 

 

Conclusion

§  Nous avons mis en correspondance des fractions qui développées donnent les quantités de partitions des nombres

ü  Ces formules sont intéressantes sur le plan des mathématiques

§  Mais le calcul pour un nombre n, surtout s'il est grand, est fastidieux

ü  Hélas, il n'existe pas de formule donnant immédiatement le résultat

 

 

Pour continuer, voir: Table des fonctions génératrices


 

-Ý-

Voir

§ Suites

§ Fractales

§ Diviseurs – Introduction

§ Diviseurs - Théorie

§ Suites

§ Fractales