Répondre à la discussion
Affichage des résultats 1 à 25 sur 25

Nombre de partitions



  1. #1
    fderwelt

    Nombre de partitions


    ------

    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

    -----

  2. Publicité
  3. #2
    matthias

    Re : Nombre de partitions

    Citation Envoyé 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.

  4. #3
    fderwelt

    Re : Nombre de partitions

    Citation Envoyé 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

  5. #4
    brixx

    Re : Nombre de partitions

    Les nombre de partitions de l'ensemble [|1,n|] sont appelés nombres de Bell (et notés Bn).
    En convenant que B0=1, ils verifient la formule de récurrence Bn+1 = sigma(C(n,k)Bk)pour k variant de 0 à n.
    Si on pose f(z)=sigma(Bn*z^n/n!) pour n de 0 à l'infini (la fonction génératrice des Bn), 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 Bk=1/e * sigma(n^k/n!) pour n variant de 0 à l'infini.

  6. #5
    fderwelt

    Re : Nombre de partitions

    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

  7. A voir en vidéo sur Futura
  8. #6
    matthias

    Re : Nombre de partitions

    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.

  9. Publicité
  10. #7
    fderwelt

    Re : Nombre de partitions

    Citation Envoyé 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

  11. #8
    matthias

    Re : Nombre de partitions

    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 ?

  12. #9
    fderwelt

    Re : Nombre de partitions

    Citation Envoyé 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

  13. #10
    matthias

    Re : Nombre de partitions

    Citation Envoyé 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

  14. #11
    brixx

    Re : Nombre de partitions

    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)

  15. #12
    martini_bird

    Re : Nombre de partitions

    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.
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  16. Publicité
  17. #13
    fderwelt

    Re : Nombre de partitions

    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

  18. #14
    martini_bird

    Re : Nombre de partitions

    Citation Envoyé 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...

    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!
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  19. #15
    fderwelt

    Re : Nombre de partitions

    À 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

  20. #16
    martini_bird

    Re : Nombre de partitions

    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 cij 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.
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  21. #17
    fderwelt

    Re : Nombre de partitions

    Citation Envoyé 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 cij 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

  22. #18
    OPi

    Re : Nombre de partitions

    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

  23. Publicité
  24. #19
    doudache

    Re : Nombre de partitions

    Citation Envoyé par fderwelt
    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.

  25. #20
    diskor

    Re : Nombre de partitions

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

  26. #21
    martini_bird

    Re : Nombre de partitions

    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.
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  27. #22
    diskor

    Re : Nombre de partitions

    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.
    Dernière modification par diskor ; 27/07/2006 à 23h41.

  28. #23
    OPi

    Re : Nombre de partitions

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

  29. #24
    ExtatiK Design

    Re : Nombre de partitions

    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.
    "Have a ball, and get involved" - Beastie Boys.

  30. Publicité
  31. #25
    fderwelt

    Re : Nombre de partitions

    Citation Envoyé par ExtatiK Design Voir le message
    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
    Les optimistes croient que ce monde est le meilleur possible. Les pessimistes savent que c'est vrai.

Discussions similaires

  1. Partitions sur Debian
    Par Momobulle dans le forum Logiciel - Software - Open Source
    Réponses: 4
    Dernier message: 26/06/2007, 10h42
  2. Partitions
    Par Znomjo dans le forum Internet - Réseau - Sécurité générale
    Réponses: 6
    Dernier message: 11/04/2007, 23h12
  3. virus et partitions
    Par Fistos dans le forum Internet - Réseau - Sécurité générale
    Réponses: 3
    Dernier message: 03/04/2007, 13h31
  4. transfert de partitions
    Par christophe_de_Berlin dans le forum Logiciel - Software - Open Source
    Réponses: 3
    Dernier message: 27/01/2007, 16h29
  5. Partitions & sécurité
    Par Europa73 dans le forum Internet - Réseau - Sécurité générale
    Réponses: 3
    Dernier message: 11/01/2007, 17h22