Fonction Partition

Fonction partition

En mathématiques, la fonction partition p(n) représente le nombre de partitions possibles d'un entier naturel n, ce qui veut dire le nombre de manières distinctes (et d'ordre indépendant) de représenter n comme une somme d'entiers. Par convention p(0) = 1, p(n) = 0 pour n négatif.

Utilisation

Une manière pour obtenir une prise sur la fonction partition implique une fonction intermédiaire p(k,n) qui représente le nombre de partitions de n utilisant seulement les entiers au moins aussi grands que k. Pour n'importe quelle valeur de k donnée, les partitions comptée par p(k,n) se placent exactement dans une des catégories suivantes :

le plus petit ajouté est k
le plus petit ajouté est strictement plus grand que k

Le nombre de partitions rencontrant la première condition est p(k,n-k). Pour voir cela, imaginons une liste de toutes les partitions du nombre n-k dans les nombres d'une taille au moins de k, puis imaginons que l'on annexe « +k » à chaque dans la liste. Maintenant, qu'est-ce qu'une liste de ceci ?

Le nombre de partitions rencontrant la deuxième condition est p(k+1,n) comme une partition en partie d'un moins k qui ne contient pas de partie d'exactement k doit avoir toutes ses parties au moins à k+1.

Comme les deux conditions sont mutuellement exclusives, le nombre de partitions rencontrant n'importe quelle condition est p(k+1,n)+p(k,n-k). Les cas de base de cette fonction récursive sont les suivants :

p(k,n) = 0 si k > n

p(k,n) = 1 si k = n

Cette fonction tend à exhiber un comportement décevant.

p(1,4) = 5

p(2,8) = 7

p(3,12) = 9

p(4,16) = 11

p(5,20) = 13

p(6,24) = 16

Notre fonction originale p(n) est simplement p(1,n).

Un calcul alternatif de la fonction partition implique les fonctions génératrices. Considérons le produit infini

$\prod_{k=1}^\infty \left(\frac {1}{1-x^k} \right)$

Développons chaque terme comme une série géométrique, nous pouvons réécrire cela comme

$(1 + x + x^2 + x^3 + ...)(1 + x^2 + x^4 + x^6 + ...)(1 + x^3 + x^6 + x^9 +...)...\,\!$

Le terme $x^m\,\!$ dans ce produit compte le nombre de manière d'écrire

$n = a_1 + 2a_2 + 3a_3 + ... = (1 + 1 + 1 + 1 + ...) + (2 + 2 + 2 + 2 + ...) + (3 + 3 + 3 ...) + ...\,\!$

où chaque nombre i apparaît a_i fois. C'est précisément la définition d'une partition de n, donc notre produit est la fonction génératrice désirée. Plus généralement, la fonction génératrice pour les partitions de n en nombres à partir d'un ensemble A peut être trouvée en prenant seulement ces termes dans le produit où k est un élément de A. Ce résultat est dû à Euler.

La formulation de la fonction génératrice est similaire à la formulation du produit de plusieurs formes modulaires, en donnant une certaine idée de la connexion entre les deux. Elle peut aussi être utilisée en conjonction avec le théorème du nombre pentagonal pour en déduire une récurrence pour la fonction partition établissant que

$p(k)-p(k-1)-p(k-2)+p(k-5)+p(k-7)-p(k-12)-... = 0\,\!$

où la somme est prise sur tous les nombres pentagonaux de la forme

$\frac{n(3n-1)}{2}$ , incluant ceux où n < 0, et les termes continuent en alternance de signe +, +, -, -, +, +, ...

Quelques valeurs de la fonction partition :

p(1) = 1
p(2) = 2
p(3) = 3
p(4) = 5
p(5) = 7
p(6) = 11
p(7) = 15
p(8) = 22
p(9) = 30
p(10) = 42
p(100) = 190 569 292
p(1 000) = 24061467864032622473692149727991
p(10 000) = 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144

Voir aussi théorie des nombres.

Liens externes

Portail des mathématiques

Ce document provient de « Fonction partition ».

Catégorie : Fonction arithmétique

Wikimedia Foundation. 2010.

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

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

Fonction partition — En mathématiques, la fonction partition p(n) représente le nombre de partitions possibles d un entier naturel n, ce qui veut dire le nombre de manières distinctes (et d ordre indépendant) de représenter n comme une somme d entiers. Par convention … 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
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
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 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… … Wikipédia en Français
Fonction Partage D'un Entier — En théorie des nombres, la fonction partage d un entier, notée p(n), est une fonction qui, pour n entier, donne le nombre de toutes les façons possibles de partager l entier naturel n, en entiers supérieurs ou égaux à 1, autrement dit le nombre… … Wikipédia en Français
Fonction partage d'un entier — En théorie des nombres, la fonction partage d un entier, notée p(n), est une fonction qui, pour n entier, donne le nombre de toutes les façons possibles de partager l entier naturel n, en entiers supérieurs ou égaux à 1, autrement dit le nombre… … Wikipédia en Français
Partition de piano mécanique — Traduction à relire Piano roll → … Wikipédia en Français
Partition d'un entier — Pour les articles homonymes, voir Partition. En particulier en mathématiques, ne pas confondre avec la notion de partition de l unité ni celle de partition d un ensemble … 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

Dictionnaires et Encyclopédies sur 'Academic'

Fonction Partition