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
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.
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 ?
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 !
Pourquoi 483 DVD ?
Bonjour,
Avec un problème de non disjonction des cas.Envoyé par danyvio
@moebius2 : 483 = 589 - 106
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
@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 à 14h45.
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
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)
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
Effectivement, ma formule S'(n+1, k) = k * S(n, k) est complètement fausse ...
Dernière modification par joel_5632 ; 09/09/2014 à 15h48.
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 à 16h09.
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
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
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
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 à 16h52.
Je ne comprends pas bien la remarque.
Pourquoi ne pourrait-on pas utiliser la formule explicite ? Le calcul est direct.
Non ?
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 à 17h17.
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
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!
Pour 53 personnes et 589 DVD, je trouve 7,764110618.10^104347 possibilités...
En appliquant:
Avec k = 589 et n=53
Multiplié par 53!
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 à 19h13.
Pardon, avec n=589 et k=53, je trouve le résultat que j'ai donnée. En effet, ça parait grand.
Parce que 589 - (2 x 53) = 483
On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !
@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
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
je calculeCode: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))
>>> 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 à 11h53.
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
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
