Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 31

Problème d'arrangements



  1. #1
    moebius2

    Problème d'arrangements


    ------

    Bonjour,

    Voici un problème que je n'arrive pas à résoudre:

    Je dispose de 589 DVD. J'ai l'intention de distribuer ces DVD à 53 personnes. Mais je m'impose de donner au moins 2 DVD à chaque personne.
    Je cherche le nombre de possibilités pour distribuer ces DVD.

    Je n'ai pas vraiment le début d'une idée, si ce n'est d'essayer d'établir une relation par récurrence:
    - si DVD = 106 à 53personnes -> 1 possibilité
    - si DVD = 107 -> 53 possibilités
    - si DVD= 108 -> ?


    Merci

    -----

  2. Publicité
  3. #2
    joel_5632

    Re : Problème d'arrangements

    bonjour

    Sans la contrainte des 2 DVD minimum par personne, il y aurait sauf erreur 53!*S(589, 53) façons de distribuer les DVD.


    Où S(n, k) est le nombre de Stirling de seconde espèce qui donne le nombre de partitions en k parties d'un ensemble de n éléments.

    Mais avec la contrainte des 2 DVD, hum .. je ne vois pas.

    Il faudrait dénombrer les partitions dont une partie au moins contient un seul élémént et retrancher.

  4. #3
    moebius2

    Re : Problème d'arrangements

    C'est là le problème. Comment dénombrer les partitions dont une partie au moins contient un seul élément à retrancher dans ce cas ?

  5. #4
    danyvio

    Re : Problème d'arrangements

    Déjà, je distribuerais 2 DVD à chacune des 53 personnes, et le problème se simplifierait un peu : distribuer 483 DVD entre 53 personnes sans contraintes de distribution minimale pour chacun...
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  6. A voir en vidéo sur Futura
  7. #5
    moebius2

    Re : Problème d'arrangements

    Pourquoi 483 DVD ?

  8. #6
    Médiat

    Re : Problème d'arrangements

    Bonjour,

    Citation Envoyé par danyvio Voir le message
    Déjà, je distribuerais 2 DVD à chacune des 53 personnes, et le problème se simplifierait un peu : distribuer 483 DVD entre 53 personnes sans contraintes de distribution minimale pour chacun...
    Avec un problème de non disjonction des cas.

    @moebius2 : 483 = 589 - 106
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  9. Publicité
  10. #7
    joel_5632

    Re : Problème d'arrangements

    @danyvio

    Ce ne sont pas 2 DVD qu'il faudrait commencer à distribuer à chacun, mais un, car pour la suite de la distribution, on sait dénombrer les partitions en k sous-ensembles d'un ensemble à n éléments avec les nombres de Stirling et dans sous-ensemble d'une partition il y a toujours au moins un élément. Ensuite cette voie conduit à un échec car des distributions identiques sont comptées 2 fois.

    Par exemple, on commence par distribuer un DVD à chacun, et Pierre reçoit le DVD Avatar. Dans la deuxième phase de la distribution, celle ou chaque personne reçoit 1, 2 ou plus de DVD, Pierre reçoit encore un unique DVD disons Gravity.

    Dans une autre distribution, Pierre commence par recevoir Gravity, puis dans la deuxième phase il reçoit uniquement Avatar.

    Ces 2 distributions sont donc identiques mais elles ont été comptées 2 fois.
    Dernière modification par joel_5632 ; 09/09/2014 à 15h45.

  11. #8
    moebius2

    Re : Problème d'arrangements

    Du coup pour 483 DVD, on revient à la formule de joel, non ? 53!*S(483, 53) possibilités.

    Est-il possible d'en savoir plus sur la non disjonction des cas ? Les probas et cie ne sont pas mon point fort.

    Merci

  12. #9
    joel_5632

    Re : Problème d'arrangements

    Soit S(n, k) le nombre de partition en k sous-ensembles d'un ensemble de n éléments (Stirling 2 ème espèce)
    Soit S'(n, k) le nombre de partition en k sous-ensembles d'un ensemble de n éléments avec au moins 2 éléments par sous ensemble.

    Il me semble que S'(n+1, k) = k * S(n, k)

    Qu'en pensez vous ?

    D'ou le nombre de distributions possibles:

    N= 53! * S'(589, 53) = 53! * 53 * S(588, 53)

  13. #10
    Médiat

    Re : Problème d'arrangements

    Il me semble que dans des cas simples, cette formule ne marche pas (5 DVD pour 3 personnes par exemple)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  14. #11
    joel_5632

    Re : Problème d'arrangements

    Effectivement, ma formule S'(n+1, k) = k * S(n, k) est complètement fausse ...
    Dernière modification par joel_5632 ; 09/09/2014 à 16h48.

  15. #12
    joel_5632

    Re : Problème d'arrangements

    Bon, en cherchant avec google, j'ai trouvé ce que l'on cherche sur la page wiki en anglais des nombres de Stirling de la 2 ème espèce.

    Associated Stirling numbers of the second kind ici:

    http://en.wikipedia.org/wiki/Stirlin...he_second_kind


    Voila, il n'y a plus qu'à écrire un programme qui calcule 53! * S_2(589, 53) à partir de la formule de récurrence donnée.
    Dernière modification par joel_5632 ; 09/09/2014 à 17h09.

  16. Publicité
  17. #13
    moebius2

    Re : Problème d'arrangements

    Il me semble que l'on peut utiliser directement la forme explicite de la formule de Stirling, ce qui permet d'enlever les 53! et de calculer la somme.
    Wolframalpha le fait très bien : http://www.wolframalpha.com/input/?i=sum%28%28-1%29^%2853-j%29*C%2853%2Cj%29*j^589%2C+j% 3D1..53%29

    On a donc tout ça comme possibilités ? Ca fait beaucoup

  18. #14
    joel_5632

    Re : Problème d'arrangements

    Tu abandonnes la contrainte des 2 DVD minimum par personne ?

    et dans ton lien vers Wolframalpha il faut supprimer l'espace avant le 3D1..53%29

  19. #15
    moebius2

    Re : Problème d'arrangements

    Oui, pardon pour l'espace.

    Ah, là c'est seulement le résultat sans la contrainte, c'est vrai. Maintenant il faut dénombrer les partitions dont une partie au moins contient un seul élémént et retrancher ?
    Euh... comment faire ?

    Je crois que je vais encore avoir besoin d'aide

  20. #16
    joel_5632

    Re : Problème d'arrangements

    Tu n'as pas vu mon message #13 ?

    La formule de récurrence est là, pour r=2:


    http://en.wikipedia.org/wiki/Stirlin...he_second_kind

    mais mieux vaut prendre celle là

    T(n,k) = sum_{i=0..k} (-1)^i*binomial(n, i)*[sum_{j=0..k-i} (-1)^j*(k -i -j)^(n-i)/(j!*(k-i-j)!)]

    trouvée ici

    http://oeis.org/A008299
    Dernière modification par joel_5632 ; 09/09/2014 à 17h52.

  21. #17
    moebius2

    Re : Problème d'arrangements

    Je ne comprends pas bien la remarque.

    Pourquoi ne pourrait-on pas utiliser la formule explicite ? Le calcul est direct.



    Non ?

  22. #18
    joel_5632

    Re : Problème d'arrangements

    je ne comprends pas.

    Si tu acceptes qu'une (ou plusieurs) personne n'ait qu'un seul DVD alors c'est bien la formule des nombres de Stirling de 2ème espèce qui convient, celle que tu cites dans le message #17, en multipliant le résultat par 56!

    sinon, si tu veux que chacun ait au moins 2 DVD, et bien relis le message #16

    An r-associated Stirling number of the second kind is the number of ways to partition a set of n objects into k subsets, with each subset containing at least r elements

    Dans ton cas, r=2, càd au moins 2 éléments (DVD) dans chacun des sous ensembles

    et bien sur on multiplie par 56!
    Dernière modification par joel_5632 ; 09/09/2014 à 18h17.

  23. Publicité
  24. #19
    moebius2

    Re : Problème d'arrangements

    Ok, j'ai compris. Mais pourquoi multiplier par 56! ?

    En tout cas merci pour toutes ces explication.

    Je vais essayer de sortir un résultat numérique (qui ne sera pas beau )pour voir si on est d'accord au final.

  25. #20
    joel_5632

    Re : Problème d'arrangements

    Admettons que l'on ait une partition des 589 DVD en 53 parties.

    Il va valoir attribuer chacune des 53 parties à chacune des 53 personnes.

    Il y a 53 possibilités pour attribuer la 1ere partie
    Il y a 52 possibilités pour attribuer la 2ème partie
    ...
    et une seule possibilité pour attribuer la 53 ème partie

    ça fait donc une multiplication par 53*52* ... *1 = 53!

  26. #21
    moebius2

    Re : Problème d'arrangements

    Pour 53 personnes et 589 DVD, je trouve 7,764110618.10^104347 possibilités...

  27. #22
    moebius2

    Re : Problème d'arrangements

    En appliquant:



    Avec k = 589 et n=53

  28. #23
    moebius2

    Re : Problème d'arrangements

    Multiplié par 53!

  29. #24
    joel_5632

    Re : Problème d'arrangements

    Hum c'est beaucoup plus que ton précédent résultat avec wolframalpha.
    Il n'y a pas de raison puisque tu ajoutes une contrainte (les 2 DVD minimum). On devrait trouver moins.

    T'aurais pas inversé n et k ?
    Dans ton message tu mets "Avec k = 589 et n=53"
    Dernière modification par joel_5632 ; 09/09/2014 à 20h13.

  30. Publicité
  31. #25
    moebius2

    Re : Problème d'arrangements

    Pardon, avec n=589 et k=53, je trouve le résultat que j'ai donnée. En effet, ça parait grand.

  32. #26
    danyvio

    Re : Problème d'arrangements

    Citation Envoyé par moebius2 Voir le message
    Pourquoi 483 DVD ?
    Parce que 589 - (2 x 53) = 483
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  33. #27
    moebius2

    Re : Problème d'arrangements

    @danyvio Merci

    @ tous

    J'ai refait le calcul.

    Je trouve 3,964409129*10^1015 possibilités de distribuer 589 DVD à 53 personnes en tenant compte de la contraintes de 2DVD.

    Quelqu'un peut-il me confirmer ce résultat ?

    Je ne suis pas sur que ce soit tout à fait exact... :@
    Si on prend le cas où l'on distribue 4 DVD (que l'on appelle A,B,C,D) à 2 personnes par exemple (avec la contrainte).
    Si l'on dénombre les possibilité, il me semble que la première personne pourra avoir AB, AC, AD, BC ou BD. Et la deuxième son complémentaire.
    Il y aurait donc 5 possibilités, non ?
    Et avec la formule, on aurait 2 ! * S_2(4,2) = 2*7 = 14.

    Qu'en pensez vous ? Je me demande s'il ne manque pas quelque chose pour que la formule soit juste.

    Merci

  34. #28
    joel_5632

    Re : Problème d'arrangements

    bonjour

    pour moi, si on a 4 DVD notés ABCD à distribuer à 2 personnes appelées P1 et P2, les possibilités sont.

    P1 P2

    AB CD
    AC BD
    AD BC
    CD AB
    BD AC
    BC AD

    soit 6 possibilités.

    J'avais écrit en Python la fonction T(n, k) qui donne le nombre de partitions d'un ensemble de n éléments en k sous ensembles avec 2 éléments min par sous ensemble

    Code:
    def T(n, k):
    	
    	if n <= 0 or k <= 0 or 2*k > n:
    		return 0
    	
    	return sum( (-1)**i * Binomial(n, i) * sum( (-1)**j * (k-i-j)**(n-i) / (fact(j)*fact(k-i-j)) \
    	for j in range(k-i+1)) for i in range(k+1))
    je calcule
    >>> fact(2) * T(4, 2)
    6.0
    je trouve le bon résultat

    Mais je ne peux pas atteindre T(589, 53) il y a overflow ...

    et puis pour certaines valeurs par ex T(100, 50) je trouve un résultat négatif,
    >>> T(100, 50)
    -9.389159009997717e+94

    je ne comprends pas ...
    Dernière modification par joel_5632 ; 11/09/2014 à 12h53.

  35. #29
    Médiat

    Re : Problème d'arrangements

    Citation Envoyé par joel_5632 Voir le message
    et puis pour certaines valeurs par ex T(100, 50) je trouve un résultat négatif,
    >>> T(100, 50)
    -9.389159009997717e+94

    je ne comprends pas ...
    Bonjour,

    Peut-être une variable qui dépasse ses capacités en tant que nombre positif et devient négatif (un overflow caché).

    Je ne connais pas Python, mais avec un langage bien typé, il suffit de déclarer ses variables "unsigned".
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  36. #30
    joel_5632

    Re : Problème d'arrangements

    oui c'est possible

    On peut tester les programmes avec T(2n, n) car le résultat peut être vérifié avec la formule:



    où T(2n, n) est le nombre de partitions d'un ensemble de 2n éléments en n sous ensembles de 2 éléments.

    >>> T(10, 5)
    945

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. Arrangements, combinaisons
    Par Serena2095 dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 23/03/2013, 18h41
  2. question délicate sur les arrangements
    Par boisdevincennes dans le forum Mathématiques du collège et du lycée
    Réponses: 11
    Dernier message: 21/11/2012, 20h04
  3. Arrangements, combinaisons ?
    Par ricco2 dans le forum Mathématiques du supérieur
    Réponses: 14
    Dernier message: 01/01/2012, 21h08
  4. Dénombrement, p-arrangements
    Par Claire333 dans le forum Mathématiques du collège et du lycée
    Réponses: 3
    Dernier message: 02/09/2011, 20h27
  5. Défi (problème d'arrangements)
    Par einstein0707 dans le forum Mathématiques du supérieur
    Réponses: 9
    Dernier message: 14/03/2009, 21h19