Nombre de partitions

fderwelt · 28/02/2006, 09h43

Bonjour,

J'aurais besoin d'une forme "commode" pour le nombre de partitions d'un entier. Je sais qu'il n'y a pas d'expression "fermée" (p.ex. avec des factorielles), mais toute expression maniable sera la bienvenue...

Rappel: Une partition d'un entier naturel n est un m-uple (n_1, ..., n_m) avec n_1 > ... > n_m > 0, tel que n_1 + ... + n_m = n.

Il ya a pas mal de propriétés, de récurrence entre autres, et je sais que ça a directement à voir avec les nombres de Strirling de deuxième espèce (cf. Wikipedia p.ex.). Mais à part ça...

En fait, mon vrai problème est de savoir de combien de manières je peux exprimer un vecteur comme C.L. à coefficients positifs d'autres vecteurs donnés. Mais c'est encore autre chose.

-- françois

**matthias** · 28/02/2006, 11h38

Citation:

Posté par fderwelt

En fait, mon vrai problème est de savoir de combien de manières je peux exprimer un vecteur comme C.L. à coefficients positifs d'autres vecteurs donnés.

Avec des coefficients entiers positifs dont la somme est fixée ?
En ce cas ce ne serait pas plus facile de considérer le nombre k-uplets d'entiers positifs ou nuls dont la somme est n (sans se soucier de l'ordre croissant) ? Je n'ai pas regardé pour l'autre, mais ça on sait le calculer facilement.

fderwelt · 28/02/2006, 11h45

Citation:

Posté par matthias

Avec des coefficients entiers positifs dont la somme est fixée ?
En ce cas ce ne serait pas plus facile de considérer le nombre k-uplets d'entiers positifs ou nuls dont la somme est n (sans se soucier de l'ordre croissant) ? Je n'ai pas regardé pour l'autre, mais ça on sait le calculer facilement.

Ce n'est pas tout à fait mon problème... c'est pour ça que je disais que "c'est encore autre chose". Mais l'énoncé complet serait assez compliqué en l'état actuel des choses, je crois qu'en fait je m'attaque à un problème mal posé. Je veux dire, que j'ai mal posé.

En revanche, j'ai vraiment besoin du nombre de partitions -- en fait, de pouvoir le manipuler autrement que par des récurrences. A moins, évidemment, de le considérer comme une fonction "primitive", finalement pas pire que l'indicateur d'Euler ou la fonction de Möbius...

-- françois

brixx · 28/02/2006, 13h24

Les nombre de partitions de l'ensemble [|1,n|] sont appelés nombres de Bell (et notés B_n).
En convenant que B₀=1, ils verifient la formule de récurrence B_n+1 = sigma(C(n,k)B_k)pour k variant de 0 à n.
Si on pose f(z)=sigma(B_n*z^n/n!) pour n de 0 à l'infini (la fonction génératrice des B_n), alors on a f(z)=1/e * exp(exp(z)) sur ]-R,R[ avec R>=1 le rayon de convergence de la série.
On a alors B_k=1/e * sigma(n^k/n!) pour n variant de 0 à l'infini.

fderwelt · 28/02/2006, 13h50

Merci à brixx!

J'avais bien repéré (entre autres sur Wikipedia) la parenté avec les nombres de Stirling, mais bizarrement pas avec ceux de Bell. Peut-être que j'avais lu trop vite (on ne lit pas pareil sur écran que sur papier (comment, toutes les excuses sont bonnes?

))

Ça ne m'aide que très modérément, mais j'y vois un peu plus clair. Et, quoi qu'il en soit, la fonction génératrice en exp(exp(...)) est impressionnante...

-- françois

**matthias** · 28/02/2006, 14h08

Le nombre de partitions de l'ensemble [[1;n]] et le nombre de partitions de l'entier n ne sont pas égaux, à moins que j'ai zappé quelque chose.

Il y a 5 partitions de [[1;3]] et seulement 3 partitions de l'entier 3.

fderwelt · 28/02/2006, 14h17

Citation:

Posté par matthias

Le nombre de partitions de l'ensemble [[1;n]] et le nombre de partitions de l'entier n ne sont pas égaux, à moins que j'ai zappé quelque chose.

Pas grave... Le mot "partition" est comme le mot "normal", utilisé avec des tas de significations différentes, et souvent sans rapport entre elles.

-- françois

**matthias** · 28/02/2006, 14h26

Tu fais comme tu veux, mais si c'est le nombre de partitions d'un entier que tu cherches, les nombres de Bell ne vont pas convenir.

Au fait avais-tu lu cette page sur Wikipedia ?

fderwelt · 28/02/2006, 15h08

Citation:

Posté par matthias

Tu fais comme tu veux, mais si c'est le nombre de partitions d'un entier que tu cherches, les nombres de Bell ne vont pas convenir.
Au fait avais-tu lu cette page sur Wikipedia ?

Merci. Oui, j'avais bien cette page. Et les nombres de Bell ne répondent pas directement à mon problème. Mais il y a tellement de relations tordues dans toutes ces question de dénombrement... voir le fil "Combinatoire" lancé par Herbiti sur ce forum.

En fait, je craque. Je suis en train de me rédiger un aide-mémoire de tous ces trucs, et des relations entre eux, en compilant un peu toutes les sources que je peux trouver. J'en ai marre de redécouvrir la roue à chaque raisonnement. C'est un peu fastidieux, même en sucrant les démonstrations détaillées, mais au final ça me fera gagner du temps.

-- françois

**matthias** · 28/02/2006, 15h29

Citation:

Posté par fderwelt

Et les nombres de Bell ne répondent pas directement à mon problème. Mais il y a tellement de relations tordues dans toutes ces question de dénombrement...

Oui on est d'accord. Et il y a encore plus de démonstrations complètement différentes que de relations.
Ca fait beaucoup de pistes à explorer

brixx · 28/02/2006, 19h42

autant pour moi, j'ai lu trop vite.
Pour les partitions d'un entier n la formule est
p(n)=p(n - 1) + p(n - 2) - p(n - 5) - p(n - 7) + p(n - 12) + ... , où 1,2,5,7,12... sont les nombres d'euler :

Nombre d'Euler. – Entier naturel provenant de la formule qui donne le énième nombre pentagonal, soit (3n - 1)n/2, dans laquelle n est un entier positif ou négatif. Les 10 plus petits nombres non nuls d'Euler sont : 1, 2, 5, 7, 12, 15, 22, 26, 35 et 40. Les nombres d'Euler apparaissent dans le développement du produit infini (1 - x) (1 - x2) (1 - x3) ( 1 - x4) ..., soit 1 - x - x2 + x5 + x7 - x12 - x15 + ... Ils sont aussi utilisés pour trouver la somme des diviseurs d'un entier naturel et les partitions d'un nombre.

Je ne pense pas qu'il y ait de formule plus "commode" pour p(n)

martini_bird · 28/02/2006, 19h47

Salut,

je pense que tu as déjà du lire cette page, mais je la mets au cas où.

A ma connaissance, quasiment tous les résultats sur le nombre de partitions d'un entier découlent de fonctions génératrices (identité d'Euler, Ramanujan, Hardy, etc.).

Cordialement.

fderwelt · 28/02/2006, 20h16

Merci à brixx et martini_bird.

Pour les nombres d'Euler, j'étais au courant, mais faute d'avoir regardé d'assez près... il semble que ce soit plus maniable que ça en a l'air a priori.

S'il y avait une formule "fermée", elle serait sûrement sur Wikipedia, MathWorld ou autres PlanetMath, non?

Je cherche seulement une expression qui se prête (de bonne grâce) aux manipulations algébriques les plus courantes (changements de variables linéaires, peut-être même quadratiques). A défaut d'accepter les derniers outrages.

-- françois

martini_bird · 28/02/2006, 20h27

Citation:

Posté par fderwelt

S'il y avait une formule "fermée", elle serait sûrement sur Wikipedia, MathWorld ou autres PlanetMath, non?

Oui c'est sûr...

Citation:

Je cherche seulement une expression qui se prête (de bonne grâce) aux manipulations algébriques les plus courantes

Je ne sais pas ce que tu fais exactement, mais précisément les fonctions génératrices permettent de passer de l'arithmétique à l'analytique, qui est plus souple. Mais bon, je n'ai pas vraiment l'impression que cette remarque va t'aider...

Sinon, si tu as déjà bossé avec les nombres de Bernoulli, les nombres d'Euler sont proches (et là aussi des fonctions génératrices facilitent grandement la tâche).

Bon courage en tout cas!

fderwelt · 28/02/2006, 21h10

À martini_bird:

C'est un peu compliqué d'expliquer ce que je fais, mais je vais résumer tant bien que mal.

En fait, j'étudie un genre d'algèbre de Lie généralisée, définie par sa matrice de Cartan $\left( c_{ij} \right)$ , et des générateurs $\left{ h_i,e_i,f_i \right}$ , avec les relations "classiques":
$\left[ h,e_i \right] \, = \, (h,h_i)e_i$
$\left[ h,f_i \right] \, = \, -(h,h_i)f_i$
$\left[ e_i,f_i] \, = \, h_i$
$\left[ e_i,f_j \right] \, = \, 0$
mais aussi et surtout:
$\left( ad \, e_i \right)^{1 - c_{ij}} \, e_j \, = \, 0$
$\left( ad \, f_i \right)^{1 - c_{ij}} \, f_j \, = \, 0$

Autrement dit, c'est le même départ que les algèbres de Kac-Moody ou de Borcherds. Mais, alors qu'en général, les $c_{ij}$ sont habituellement des entiers $\leq 0$ , dans mon cas ce sont des rationnels quelconques.

J'ai d'excellentes raisons de penser que l'algèbre correspondante pourrait être associée à des opérateurs différentiels d'ordre non entier. Il y a une sorte de structure "imbriquée" du groupe de Weyl, qui est clairement liée à une topologie p-adique sur l'espace des poids.

Mais de là à conclure définitivement...

En tout cas, je préfère l'Algèbre à l'Analyse. Parce que je suis moins nul en Algèbre.

Mais quand il faut être efficace, on ne chipote pas trop sur les méthodes...

-- françois

martini_bird · 28/02/2006, 21h37

Oki oki. C'est un peu too hot pour moi tout ça.

Je viens grâce à toi de découvrir les matrices de Cartan, donc pour le reste (quelle idée aussi de remplacer les c_ij par des rationnels !)...

Et là je ne vois pas du tout le lien avec les partitions, mais bon, je m'y mets et je te donne des nouvelles dans 10 ans.

Cordialement.

fderwelt · 28/02/2006, 21h56

Citation:

Posté par martini_bird

Je viens grâce à toi de découvrir les matrices de Cartan, donc pour le reste (quelle idée aussi de remplacer les c_ij par des rationnels !)...

Comment, quelle idée? Dans le bouquin de V.G.Kac (Infinite Dimensional Lie Algebras) il prend des complexes quelconques... au moins au chapitre 1. Parce qu'au chapitre 2, il s'empresse de préciser qu'on nepeut faire de théorie valable qu'avec des entiers < 0.

Les partitions, c'est parce qu'un poids de l'algèbre est un vecteur à composantes entières dans une base correctement choisie, mais que les transformations envisagées disent que cette base n'est pas forcément invariante.

Mais bon, je sens que redeviens "too hot", je te laisse le temps de refroidir...

-- françois

OPi · 11/06/2006, 01h03

Bonjour (soir, nuit

),

Je joue un peu avec les partitions en ce moment et réalise un petit résumé :
http://geocities.com/olivier_pirson_opi/partitions/.

C'est probablement pas le niveau recherché par fderwelt mais il contient la formule de Hardy - Ramanujan - Rademacher. Pas très maniable mais close tout de même. Je la tiens de l'Encyclopaedia Universalis.

fderwelt, si l'aide-mémoire que tu te réalisais est disponible ça m'intéresse.

Bon amusement