Nombre de partitions

[invite6de5f0ac]

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
-----

[invitec314d025]

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.

[invite6de5f0ac]

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

[invite2f4d9e53]

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.

[A voir en vidéo sur Futura]

[invite6de5f0ac]

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

[invitec314d025]

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.

[invite6de5f0ac]

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

[invitec314d025]

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 ?

[invite6de5f0ac]

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

[invitec314d025]

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

[invite2f4d9e53]

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)

[invite4793db90]

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.

[invite6de5f0ac]

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

[invite4793db90]

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

Oui c'est sûr...

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!

[invite6de5f0ac]

À 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 , et des générateurs , avec les relations "classiques":




mais aussi et surtout:



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 sont habituellement des entiers , 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

[invite4793db90]

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.

[invite6de5f0ac]

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]

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

[invite8b04eba7]

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.

Si tu as le temps, je veux bien que tu m'expliques ce que cela signifie exactement.

[invite9c4d9878]

Bonjour,

Mon niveau en math et trop modeste pour aider fderwelt, j'ai juste une question:
Sur la page wiki citée précédemment, on retrouve la fonction asymptotique du nombre de partition de n, due à Hardy et Ramanujan .La page se termine par "Plus tard, ils obtinrent une égalité stricte pour calculer p(n)". ???
Quelqu'un connait-il cette egalite ?
J'ai bien lu la page de mathworld et je ne crois pas que la reponse y soit.

Merci à Opi pour son résumé
HS:quelqu'un sait il ou trouver les carnets de Ramanujan (en ligne ou sur papier)?

[invite4793db90]

Salut,

Plus tard, ils obtinrent une égalité stricte pour calculer p(n)

Cette phrase est pour le moins confuse : qu'est ce qu'une égalité qui ne serait pas stricte ? Peut-être l'auteur pense-t-il à une inégalité ?

J'ai bien lu la page de mathworld et je ne crois pas que la reponse y soit.

La formule (24) est une formule fermée.

Sinon, pour les carnets de Ramanujan, ils ont été publiés par Berndt chez Springer (et ils sont chers).

Cordialement.

[invite9c4d9878]

Merci de tes réponses martini_bird.

En fait, je revais d'une formule plus facile à manier, sans somme infinie...Celle la me plaisait bien :



(cf doc OPi)

pour les carnets, merci pour le lien mais 120€ le volume avec 12 volumes...ouch.Puis c'est retravaillé par des profs...
Pour noel peut-être.
J'aimerais bien trouvé la reproduction des originaux.

Merci encore et bravo pour votre site et son forum.

[OPi]

Bonjour,
En ce qui concerne mon résumé, plus ça avance et plus il faut prendre garde à vérifier les résultats !

Dans la partie 9. "Comportement limite", la première formule est tirée de l'Encyclopaedia Universalis. La seconde (celle que tu cites diskor) provient de la page de Wikipédia Fonction partage d'un entier. Si elle est correcte sont comportement asymptotique est le même que celui de la fonction P(n). Mais alors qu'il est indiqué qu'elle devrait être exacte pour n = 200, Maple me donne les résultats suivants :
P(200) = 3 972 999 029 388
"1re formule approximative"(200) = 57 986 311 845 397
"2de formule approximative"(200) = 919 016 238 379
Donc je ne sais pas très bien à quoi elles correspondent...

[invitee51aa8e9]

Tiens, c'est marrant je suis en train de lire ça:
http://algo.inria.fr/flajolet/Publications/books.html
et je suis justement P37 et suivantes du pré-print (ou P47 et suivantes du PDF) et les auteurs évoquent votre problème de partition d'entiers.

[invite6de5f0ac]

Tiens, c'est marrant je suis en train de lire ça:
http://algo.inria.fr/flajolet/Publications/books.html
et je suis justement P37 et suivantes du pré-print (ou P47 et suivantes du PDF) et les auteurs évoquent votre problème de partition d'entiers.

Bonjour et merci,

Génial ce bouquin! C'est exactement le genre de choses qui manquent cruellement à ma bibliothèque!

-- françois