Partition entière

Partition entière

Partition d'un entier

Une partition d'un entier strictement positif n est une façon d'écrire n comme une somme d'entiers strictement positifs. Deux sommes qui diffèrent seulement de l'ordre de leurs opérandes sont considérées comme étant la même partition. Un opérande dans une partition est aussi appelé une partie.

Une partition est aussi parfois appelé partage d'un entier.

Sommaire

Définitions

Partition d'un entier

Soit \ n un entier strictement positif, une partition de \ n est une suite d’entiers \ (s_1, ..., s_m ) vérifiant

  • \ m \ge 1 ;
  • tous les entiers \ s_i sont non nuls ;
  • \sum_{i=1}^m s_i = n.

k-partition d'un entier

Une k-partition de l'entier n est une partition de n possédant k éléments.

Exemples

Les partitions de 4 sont listés ci-dessous :

  • 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1

Voici les partitions de 8 :

  • 8
  • 7 + 1
  • 6 + 2
  • 6 + 1 + 1
  • 5 + 3
  • 5 + 2 + 1
  • 5 + 1 + 1 + 1
  • 4 + 4
  • 4 + 3 + 1
  • 4 + 2 + 2
  • 4 + 2 + 1 + 1
  • 4 + 1 + 1 + 1 + 1
  • 3 + 3 + 2
  • 3 + 3 + 1 + 1
  • 3 + 2 + 2 + 1
  • 3 + 2 + 1 + 1 + 1
  • 3 + 1 + 1 + 1 + 1 + 1
  • 2 + 2 + 2 + 2
  • 2 + 2 + 2 + 1 + 1
  • 2 + 2 + 1 + 1 + 1 + 1
  • 2 + 1 + 1 + 1 + 1 + 1 + 1
  • 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Parmi les 22 partitions du nombre 8, 6 d'entre eux contiennent seulement des parties impaires :

  • 7 + 1
  • 5 + 3
  • 5 + 1 + 1 + 1
  • 3 + 3 + 1 + 1
  • 3 + 1 + 1 + 1 + 1 + 1
  • 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Curieusement, si nous comptons les partitions de 8 en « parties distinctes », nous obtenons aussi le nombre 6 :

  • 8
  • 7 + 1
  • 6 + 2
  • 5 + 3
  • 5 + 2 + 1
  • 4 + 3 + 1

Est-ce seulement une coïncidence, ou est-il vrai que pour tout entier strictement positif, le nombre de partitions en parties impaires est toujours égal au nombre de partitions ayant des parties distinctes ? Ce type de résultats et d'autres peuvent être obtenus à l'aide d'un outil visuel, le graphe de Ferrer.

Graphe de Ferrer

La partition 6 + 4 + 3 + 1 de l'entier strictement positif 14 peut être représenté par le graphe suivant :

o o o o
o o o
o o o
o o
o
o

6+4+3+1 

Les 14 cercles sont alignés sur 4 colonnes, chacune ayant la grandeur d'une partie de la partition. Les graphes pour les 5 partitions du nombre 4 sont listés ci-dessous :

o   o o   o o   o o o   o o o o
o   o     o o   o
o   o
o

4   3+1   2+2   2+1+1   1+1+1+1

Maintenant, si nous effectuons une symétrie du graphe de la partitions de 6 + 4 + 3 + 1, par rapport à la diagonale principale :

o o o o         o o o o o o
o o o           o o o o
o o o     -->   o o o
o o             o
o
o

6+4+3+1         4+3+3+2+1+1

En transformant les lignes en colonnes, nous obtenons la partition 4 + 3 + 3 + 2 + 1 + 1 du nombre 14. De telles partitions sont dits conjuguées l'une de l'autre. Dans le cas du nombre 4, les partitions 4 et 1 + 1 + 1 + 1 sont conjugués, ainsi que les partitions 3 + 1 et 2 + 1 + 1. La partition 2 + 2 présente un certain intérêt, puisqu'elle est sa propre conjuguée. Un tel partage est dit auto-conjugué.

Proposition Le nombre de partitions auto-conjugués est le même que le nombre de partages en parties impaires distinctes.

Schéma de la démonstration: Le fait essentiel est que toutes les parties impaires peuvent être « pliées » en leur milieu pour former un graphe auto-conjugué :

o
o
o   -->   o o o
o         o
o         o

Nous pouvons alors construire une bijection entre l'ensemble des partitions en parties impaires distinctes et l'ensemble des partitions auto-conjugués, comme l'illustre très bien l'exemple suivant:

    o * x          o o o o o   
    o * x          o * * * *   
    o * x   <-->   o * x x     
    o *            o * x       
    o *            o *         
    o *                        
    o *                        
    o                          
    o                          
 
    9+7+3          5+5+4+3+2   

impair distinct auto-conjugué

Des techniques similaires peuvent être employées pour établir, par exemple, les égalités suivantes :

  • Le nombre de partitions de n en au plus k parties est égal au nombre de partitions de n en parties inférieures à k.
  • Le nombre de partitions de n en moins de k parties est égal au nombre de partitions de n+k en exactement k parties.

Nombre de partages

Le nombre de partages d'un entier strictement positif n est donné par la fonction partage p. Le nombre de partages de n en exactement k parties est noté pk(n).

Les techniques des graphes de Ferrer nous permettent aussi de prouver des résultats comme le suivant :

  • Il y a p(n) - p(n-1) partages de n dans lesquels chaque partie est supérieure à 2.
  • p(1) + p(2) + ... + p(n) < p(2n)

Voir aussi

Liens internes

Référence bibliographiques

Une introduction élémentaire à la notion de partition d'un entier, incluant les graphes de Ferrer, peut être trouvée dans l'ouvrage suivant :

Miklós Bóna, A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific Publishing, 2002. ISBN 981-02-4900-4.
  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Partition d%27un entier ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Partition entière de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Partition de Chypre — Partition de l’île de Chypre La rue Ledra à Nicosie, symbole des prémices d ouverture entre les deux parties de l île. Les drapeaux hissés représentent respectivement certaines des parties présentes dans le cadre de l hypothétique résolution du… …   Wikipédia en Français

  • Partition de l'unité — En première approche, on peut dire qu une partition de l unité est une famille de fonctions positives telles que, en chaque point, la somme sur toutes les fonctions des valeurs prises par chacune d elle vaille 1 : . Plus précisément, si X… …   Wikipédia en Français

  • Partition of Belgium — The partition of Belgium, or the dissolution of the Belgian State through the separation of the Dutch speaking peoples of the Flanders region from the French speaking peoples of the Walloon Region, granting them either independence or respective… …   Wikipedia

  • Fonction De Partition — En physique statistique, la fonction de partition Z est une grandeur fondamentale qui englobe les propriétés statistiques d un système à l équilibre thermodynamique. C est une fonction de la température et d autres paramètres, tels que le volume… …   Wikipédia en Français

  • Fonction de partition — En physique statistique, la fonction de partition Z est une grandeur fondamentale qui englobe les propriétés statistiques d un système à l équilibre thermodynamique. C est une fonction de la température et d autres paramètres, tels que le volume… …   Wikipédia en Français

  • Liste Des Matières De La Théorie Des Nombres — Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 …   Wikipédia en Français

  • Liste des matieres de la theorie des nombres — Liste des matières de la théorie des nombres Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 …   Wikipédia en Français

  • Liste des matières de la théorie des nombres — Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 Test de primalité e …   Wikipédia en Français

  • Formule de Faà di Bruno — En mathématiques, et plus précisément en analyse, la formule de Faà di Bruno est une identité généralisant la règle de dérivation des fonctions composées au cas des dérivées d ordre supérieur. Elle a été le plus souvent attribué au mathématicien… …   Wikipédia en Français

  • George Gerschwin — George Gershwin George Gershwin George Gershwin en 1937. Naissance 26 septembre 1898 …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”