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

Combinatoire et comptage difficile




  1. #1
    josedamato

    Combinatoire et comptage difficile

    Bonjour à tous, je cherche une equation générale à un problème de combinatoire.

    Supposons que j'aie un tableau de longueur L. On le lit toujours de gauche à droite. C'est important. Tous les nombres de ce tableau sont des nombres entiers positifs.
    Toute valeur située à la gauche d'une valeur peut être supérieure ou égale à celle-ci.

    Par exemple:

    [6,6,5,4,3,3] est ok

    mais

    [6,5,6,4,3,3] pas ok. le 2nd 6 est plus grand que 5.

    Quelle formule mathématique me permet de compter toutes les possibilités que la somme des valeurs d'un tableau soit égale à k, tout en prenant en compte les valeurs maximales qu'on peut trouver dans ce tableau et sa longueur?

    Deux exemples pour mettre tout cela au clair.

    Longueur:6, somme des valeurs:19, valeur max:5. On doit trouver 16 résultats.

    4,3,3,3,3,3
    4,4,3,3,3,2
    4,4,4,3,2,2
    4,4,4,3,3,1
    4,4,4,4,2,1
    5,3,3,3,3,2
    5,4,3,3,2,2
    5,4,3,3,3,1
    5,4,4,2,2,2
    5,4,4,3,2,1
    5,4,4,4,1,1
    5,5,3,2,2,2
    5,5,3,3,2,1
    5,5,4,2,2,1
    5,5,4,3,1,1
    5,5,5,2,1,1

    Longueur:4, somme des valeurs:8, valeur max:5. On doit trouver 5 résultats.

    2,2,2,2
    3,2,2,1
    3,3,1,1
    4,2,1,1
    5,1,1,1


    Quelle est la formule mathématique me permettant de compter le nombre de possibilités, en fonction des paramètres exprimés plus haut?

    Là, je bloque. Je ne sais même pas si on peut.

    Merci tout le monde,

    -----


  2. Publicité
  3. #2
    Médiat

    Re : Combinatoire et comptage difficile

    Bonjour,

    Regardez "partion d'un entier", il est facile de mettre en place des relations de récurrence.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  4. #3
    josedamato

    Re : Combinatoire et comptage difficile

    Bonjour,
    Merci à vous.
    Moi qui ne suis pas mathématicien, j'en bave.

    La formule de récurrence a l'air de prendre les nombres dans le désordre, ajoutant, de fait des solutions qui ne correspondent pas à mon problème.

    En réalité, il n'existe pas de formule toute prête et je ne me sens pas capable d'aller plus loin là dessus. Moi qui aime les énigmes et bientôt à la retraite, c'est un problème insoluble là.


  5. #4
    josedamato

    Re : Combinatoire et comptage difficile

    Erreur de ma part, merci ne pas tenir compte du message ci dessus!

  6. #5
    josedamato

    Re : Combinatoire et comptage difficile

    Je crois par contre comprendre qu'on est obligé de faire une récursion et donc de calculer toute valeur au préalable. Moi je pensais qu'il existait un moyen de dire en un calcul "voilà combien il y en a pour tel ordre".

    Or, là il faut faire des itérations des valeurs précédentes.. trop long..
    Dernière modification par josedamato ; 03/10/2018 à 09h13.

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

    Re : Combinatoire et comptage difficile

    Il y a une formule générale, mais elle est compliquée.

    Sinon, il y a aussi des formules asymptotiques :



    En particulier, on se rend compte que ça grimpe vite ( p(1000) est de l'ordre de )

  9. #7
    josedamato

    Re : Combinatoire et comptage difficile

    Oui exact, j'ai vu cette formule d'approximation par la suite! Merci de votre retour 😀

  10. Publicité
  11. #8
    ansset

    Re : Combinatoire et comptage difficile

    Le soucis est que tu as 3 récurrences en //
    la longueur L
    la somme S
    la valeur max M,
    avec des contraintes entre les 3.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  12. #9
    josedamato

    Re : Combinatoire et comptage difficile

    C'est sûrement pour cela que j'ai eu un problème pour trouver une généralisation. Entre temps, mon petit fils s'est proposé de m'aider avec son ordinateur, alors je n'aurai pas de formule générale, mais au moins j'aurais mon résultat avec les 3 contraintes.. c'est déjà ça.. merci infiniment à vous tous, les amis

  13. #10
    ansset

    Re : Combinatoire et comptage difficile

    ceci dit, analytiquement, se serait un très bon sujet en "science ludique".
    but: chercher l'expression la plus courte et/ou élégante.
    en commençant par prendre les variables dans le bon ordre.
    Cdt
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

Discussions similaires

  1. comptage d un parking
    Par machioukh7 dans le forum Électronique
    Réponses: 3
    Dernier message: 19/06/2011, 14h07
  2. Pic et comptage rb4..
    Par pyrosigma dans le forum Électronique
    Réponses: 6
    Dernier message: 17/09/2010, 08h37
  3. Comptage et ejp...
    Par leaderschip dans le forum Électronique
    Réponses: 2
    Dernier message: 27/01/2010, 12h24
  4. comptage sur un API
    Par fomes dans le forum Électronique
    Réponses: 0
    Dernier message: 17/04/2008, 00h02
  5. Comptage bactéries
    Par titi45 dans le forum TPE / TIPE et autres travaux
    Réponses: 1
    Dernier message: 03/04/2008, 13h32