Problème sur un ensemble fini

[Phil]

Bonjour,
Voici un problème réel que je me suis posé il y a quelques jours:
1) J'ai 6 imprimantes et 6 certificats de garantie
2) A chaque imprimante est associé un certificat
3) Problème : j'ai perdu la table de correspondance entre imprimante et certificat
4) Question: Si X est le nombre d'associations correctes, quelle est la probabilité d'avoir X=0,1,2,3,4,5 ou 6 associations correctes?

:) La réponse est facile pour p(X=6) puisqu'il n'y a qu'une seule permutation qui convient : p(X=6) =1/6!
:confused: La réponse est un peu surprenante pour X=5 puisque p(X=5)
:rolleyes: Et les autres probabilités ???
Et que se passe-t-il si on généralise à un ensemble n avec n tendant vers l'infini ? (notamment au niveau de l'espérance mathématique)
(PS: je crois avoir trouver, mais je souhaiterais avoir votre point de vue car il y a plusieurs façons de voir les choses...)

Merci d'avance pour vos réponses
Cordialement
Phil

[tristan]

Bonjour, je crois que tu fais une erreur. Il serait quand même étrange qu'en faisant confiance au hasard tu ais une chance sur 6 de tomber pile sur la bonne combinaison ;).

[krou]

Bonjour,
:confused: La réponse est un peu surprenante pour X=5 puisque p(X=5)
Phil

????? tu n'as pas fini ta phrase lol :p

bon je la finis pour toi, p(X=6) = 1/6!, supposons qu'on ait p(X=5) alors 5 certificats sont rattachés à 5 imprimantes donc le dernier certificat est obligatoirement rattaché à la dernière imprimante, donc p(X=5) => p(X=6) donc p(X=5) = 0

Edit : je viens de voir le message de tristan : phil ne dit pas : 1/6 mais 1/6! (factorielle) en effet il n'y a qu'une seule possibilité pour assossier le certificdat à la bonne imprimante, et il y a en tout 6*5*4*3*2*1 soit 6! possibilités d'associations

[tristan]

oui mauvaise lecture désolé ;)

[quinto]

Salut,
l'idée est de considérer les fonctions d'un ensemble de 6 éléments vers lui même.
(X=0) c'est le nombre de fonctions qui ne laisse fixe aucun des éléments (ie il n'existe aucun n tel que f(n)=n)

(X=1) c'est le nombre de fonctions qui ne laisse fixe qu'un seul élément (ie il existe un seul n tel que f(n)=n)
etc

(X=6) c'est le nombre de fonctions qui laisse tous les éléments fixes, donc f(1)=1 f(2)=2 ... f(6)=6
Notamment c'est la fonction identité et c'est la seule.
Donc (X=6)=1
On suppose que la proba est uniforme et donc l'ensemble des fonctions d'un ensemble de 6 éléments dans lui même est de cardinal 6!=720.
Donc on a bien p(X=6)=1/6!

Voilà un début de modélisation, maintenant om faut généraliser un peu tout ça.
Je crois que lorsque n tend vers l'infini, la proba demandée est de 1/e, mais je peux me tromper.
Amicalement,
Quinto

[tristan]

Cette question me paraît assez difficile. Par exemple imaginons que je veuille obtenir le nombre de fonctions qui ne laissent qu'un élément fixe. Je peux choisir entre 6 éléments fixes différents. Une fois que c'est fait il me reste donc 5 imprimantes avec leurs 5 bons de garantie correspondants. De combien de façon puis-je arranger ces 5 imprimantes avec leurs bons de garantie, sachant qu'aucune d'elles ne doit se trouver avec son propre bon ?

De quelle probabilité parle tu Quinto ?

[Phil]

Bonjour,
D'abord merci pour vos réponses.
Voici, un peu tardivement, en quelque lignes et sans faire de démonstration, ma façon de voir les choses au niveau combinatoire :
1) J'appelle C(i,n) : le nombre de combinaison d'un ensemble n avec i, le nombre d'éléments bien placés
ainsi: pour n=1 : C(0,1) = 0 et C(1,1) = 1
pour n= 2 : C(0,2) = 1, C(1,2) = 0, C(2,2) = 1
2) D'une façon générale
2-1) pour i> 0 et pour n éléments, on s'aperçoit (et ça se démontre...) que le nombre de combinaisons C(i,n) est égal au nombre de combinaisons de rang (i-1) dans un ensemble de n-1 éléments multiplé par n (car factorielle n = n! = n(n-1)!) et divisé par i (car il y a i doublons)
d'où la relation de récurrence C(i,n) = C(i-1,n-1)*n/i
2-2) pour i = 0: C(0,n) = le complément par rapport au nombre de combinaison de n éléments (n!)
d'où: C(0,n) = n! - Somme (C(i,n)) pour i = 1 à n

A partir de là, on obtient le tableau suivant:
Pour i= 0,1,2,3,4,5,6
n= 1 : C(0,1) = 0: C(1,1) = 1
n= 2 : C(0,2) =1, C(1,2) = 0, C(2,2) = 1
n= 3 : C(0,3) = 2, C(1,3) = 3, C(2,3) = 0, C(3,3) =1
n= 4 : C(0,4) = 9, C(1,4) = 8, C(2,4) = 6, C(3,4) = 0, C(4,4) = 1
n= 5 : C(0,5) = 44, C(1,5) = 45, C(2,5) = 20, C(3,5) = 0, C(4,5) = 1
n= 6 : C(0,6) = 265, C(1,6) = 264, C(2,6) = 135, C(3,6) = 40, C(4,6) = 15, C(5,6) = 0, C(6,6) = 1

C'est pour n= 6, mon problème d'imprimantes; la probabilité associée à chaque i est égal à : p(X=i) = C(i,n)/ n! avec ici n=6

Au passage, et quelque soit n, on remarque qu'il y a quasiment autant de chance de n'avoir aucun élément bien placé (i=0) que d'avoir un seul élément bien placé (i=1)

J'espère que j'ai été assez clair et que je n'ai plus fait d'erreurs de frappe, comme la première fois...
Je continue à étudier le problème pour n tendant vers l'infini...

Cordialement

Phil

[cesar]

La réponse est facile pour p(X=6) puisqu'il n'y a qu'une seule permutation qui convient : p(X=6) =1/6!
:confused: La réponse est un peu surprenante pour X=5 puisque p(X=5)

bonjour,
pour X= 5 ==> ce cas est impossible, car si l'on suppose que l'on a associé 5 certificats, alors celui qui reste est associé à la bonne imprimante lui aussi.
donc si X= 5 ==> X=6, d'où P(X=5)=0

le cas X=4 est mieux : on a inversé 2 certificats. Il faut donc prendre tous les couples possibles comme numerateur, soit : 6x5+5x4+4x3+3x2+2x1 = 70

soit P(X=4)= 70/6! = 70/720

[Phil]

bonjour,
pour X= 5 ==> ce cas est impossible, car si l'on suppose que l'on a associé 5 certificats, alors celui qui reste est associé à la bonne imprimante lui aussi.
donc si X= 5 ==> X=6, d'où P(X=5)=0

le cas X=4 est mieux : on a inversé 2 certificats. Il faut donc prendre tous les couples possibles comme numerateur, soit : 6x5+5x4+4x3+3x2+2x1 = 70

soit P(X=4)= 70/6! = 70/720

Bonjour César,
Très bonne remarque pour X= 4 et n= 6, mais dans ce cas, le nombre de couples possibles est d'après moi, le nombre de combinaisons de 2 éléments sur 6 soit 6!/2!(6-2)! = 6*5/2= 15, ce qui colle avec ce que j'ai trouvé...d'où p(X=4) = 15/720, je ne suis donc pas d'accord avec 70/720...
D'ailleurs,en vérifiant, je m'apercoit que j'ai encore fait une erreur de frappe sur la ligne n=5 de mon tableau:
n= 5 ; C(0,5) = 44, C(1,5)=45, C(2,5)=20, C(3,5)=10, C(4,5)=0, C(5,5)=1
pour le cas n= 5 et pour X=3 le nombre de couples est 5!/2!(5-2)!=5*4/2=10

PS : j'ai vérifié mes résultats de façon exhaustive sur un fichier EXCEL jusque n=5

Cordialement

Phil

[cesar]

Bonjour César,
Très bonne remarque pour X= 4 et n= 6, mais dans ce cas, le nombre de couples possibles est d'après moi, le nombre de combinaisons de 2 éléments sur 6 soit 6!/2!(6-2)! = 6*5/2= 15, ce qui colle avec ce que j'ai trouvé...d'où
Phil

vous avez raison sur ce point : numerotons les elements n1,n2,n3,n4,n5,n6

pour l'element n°1
on a 5 couples (n1,n2),(n1,n3)...(n1,n6)
pour le n°2
4 de plus : (n2,n3),(n2,n4)...(n2,n6)
pour le n°3
3 de plus (n3,n4),.....(n3,n6)
pour le n°4 : 2 de plus
pour le numero 5 : 1 de plus
soit au total : 15 = combinaisons de 6 elements deux à deux = 6!/(2!(6-2)!)

[Phil]

vous avez raison sur ce point : numerotons les elements n1,n2,n3,n4,n5,n6

pour l'element n°1
on a 5 couples (n1,n2),(n1,n3)...(n1,n6)
pour le n°2
4 de plus : (n2,n3),(n2,n4)...(n2,n6)
pour le n°3
3 de plus (n3,n4),.....(n3,n6)
pour le n°4 : 2 de plus
pour le numero 5 : 1 de plus
soit au total : 15 = combinaisons de 6 elements deux à deux = 6!/(2!(6-2)!)

Bonjour,
Je reprends de nouveau ce problème pour cette fois le terminer...
D'abord une notation: j'appelle a(n) le nombre de cas de désordre total pour un ensemble à n éléments, la probabilité associée étant P(X=0,n)=a(n)/n!
1) Je remercie une deuxième fois César pour sa remarque du 28/07/05 qui m'a mis sur la voie...
En effet, ce qui est valable pour 2 éléments est aussi valable pour i éléments.
Ainsi pour un ensemble de n éléments, si on désire i éléments bien rangs, cela signifie que les n-i autres sont dans le désordre, on se ramène donc au cas d'un ensemble de (n-i) éléments totalement désordonné: a(n-i) = (n-i)!*P(X=0,n-i) et comme il y a C(n,n-i) combinaisons (c'est à dire "combinaisons de n-i éléments dans un ensemble de n éléments") le résultat cherché est C(n,n-i)a(n-i)= n!/i!(n-i)!a(n-i)= C(n,i)a(n-i).
Par exemple, pour n=6 et i=2, mon tableau précédent (message du 28/7) indique que pour un ensemble à 6-2= 4 éléments, il y a 9 cas possibles d'avoir tout dans le désordre, on a donc C(6,6-2)*9 = 6!*9/2!(6-2)!= 135.

Ma conclusion est donc que pour un ensemble de n éléments, on peut en déduire toutes les combinaisons (ou les probabilités, P(X=i,n) à (n!) près ) à condition de connaitre le nombre de cas possibles lorsque tout est dans le désordre, pour les ensembles de p éléments p variant de 1 à n-1. (en terme de probabilité il faut connaitre P(X=0,p) pour p =1,2 ... n-1)

2) Après réflexion et un peu de logique, on trouve la relation suivante qui est en fait la clé du problème:
a(n) = (n-1)(a(n-1)+a(n-2))
avec a(1)=1, a(2)=0, a(3)=2, a(4)=9, a(5) = 44 etc...

La relation de récurrence associée est déduite de cette observation:
a(n) = n!P(X=0,n)=n!P(X=1,n)plus ou moins 1,
On trouve finalement la conjecture a(n) = n!(1-1+1/2!-1/3!... (-1)^n/n!) qui se démontre par récurrence (voir mon message du 12 septembre sur le forum "Supérieur").
A partir de là, on trouve toutes les solutions quelque soit n.

Quant au cas n tendant vers l'infini, cela fait l'objet du message suivant

Mes excuses pour mes fautes de frappe ou de style, mais ce n'est pas facile à expliquer...

Cordialement

Phil

[Phil]

Salut,
l'idée est de considérer les fonctions d'un ensemble de 6 éléments vers lui même.
(X=0) c'est le nombre de fonctions qui ne laisse fixe aucun des éléments (ie il n'existe aucun n tel que f(n)=n)

(X=1) c'est le nombre de fonctions qui ne laisse fixe qu'un seul élément (ie il existe un seul n tel que f(n)=n)
etc

(X=6) c'est le nombre de fonctions qui laisse tous les éléments fixes, donc f(1)=1 f(2)=2 ... f(6)=6
Notamment c'est la fonction identité et c'est la seule.
Donc (X=6)=1
On suppose que la proba est uniforme et donc l'ensemble des fonctions d'un ensemble de 6 éléments dans lui même est de cardinal 6!=720.
Donc on a bien p(X=6)=1/6!

Voilà un début de modélisation, maintenant om faut généraliser un peu tout ça.
Je crois que lorsque n tend vers l'infini, la proba demandée est de 1/e, mais je peux me tromper.
Amicalement,
Quinto

Bonjour,
Voici la suite et la fin du problème : on fait tendre n vers l'infini et c'est La remarque de Quinto qui confirme mes résultats.
1) Je rappelle le dernier résultat de mon message précédent:
dans un ensemble à n éléments, si a(n) est le nombre de cas de désordre total (en terme de probabilité P(X=0,n) = a(n)/n!) alors
a(n) = n! (1-1+1/2!-1/3!.... (-1)^n)
Quand n tend vers l'infini (ou en pratique assez grand car çà converge très vite) , a(n) est équivalent à n!*1/e, ce qui rejoint la remarque de Quinto!!!! car P(X=0, n=infini) = 1/e
Même chose pour P(X=1,n=infini), mais attention, ce n'est plus vrai pour P(X=i,n=infini) avec X=i proche de n: on retrouve P(X=n-1,n= infini)=0, P(X=n,infini=1)

2) L'espérance mathématique est sauf erreur, E= 1.
Ce qui donne par exemple le résultat suivant quand n est grand (en approximant 1/e par 1/3)
Si on désire ranger par hauteur et par couleur un jeu de 52 cartes mélangées, on a à peu près 1 chance sur 3 d'avoir aucune carte dans l'ordre, 1 chance sur 3 d'avoir 1 seule carte dans l'ordre, 1 chance sur 3 d'avoir 2 cartes ou plus dans l'ordre.

Voilà, j'ai fini. Tout ceci est bien difficle à expliquer, Mais ce problème à l'origine tout simple, est à mon sens riche en réflexion et surprenant en résultats.
Encore merci à César, Quinto et à tous ceux qui se sont intéressés à mon problème.

Cordialement

Phil