Analyse combinatoire : dérangements

[kaizokun]

Bonjour, je tente de comprendre un exemple d'un bouquin sur les probabilités, il s'agit de ce livre ci https://www.editions-ellipses.fr/pro...ducts_id=11184

Il s'agit donc d'un exemple et non d'un exercice. Je cale sur une partie de l'explication dont vous me direz ce que vous en pensez .


n machines composées de deux parties appelées respectivement émetteur et récepteur
sont transportées en mettant d'un côté les n émetteurs et de l'autre les n récepteurs.

À l'arrivée, un opérateur ré assemble les émetteurs aux récepteurs sans savoir qu'en fait
chaque couple (émetteur, récépteur) avait été réglé au départ pour fonctionner ensemble
(ils avaient été appariés). On se propose de chercher la probabilité que l'opérateur n'ait
reconstitué aucun des couples initiaux.

Pour effectuer le remontage, l'opérateur va prendre successivement les németteurs ;
numérotons ces n émetteurs de 1 a n selon l'ordre choisi par l'opérateur.

Numérotons les récepteurs pour que le numéro d'un récepteur soit le même que
celui de l'émetteur auquel il était initialement couplé. Notons une éventualité
par le n-uple (i1, i2, ...,ij, ...,in) où ij est le numéro du récepteur initialement
couplé au jème émetteur choisi par l'opérateur.

Face a cet ordre des émetteurs, l'opérateur a n! façons équiprobables d'associer
les n récepteurs. Comme il a une seule façon de choisir les n récepteurs pour reconstituer
les n matériels initiaux, notons au passage que la probabilité de reconstituer les n matériels
initiaux est égale a 1/!n.

Soit Bj l'événement « l'opérateur a couplé l'émetteur j au récepteur initial (ij = j) ».

Par symétrie, une éventualité sur n sera telle que ij = j. Comme toutes les éventualités
sont équiprobables, la probabilité de l'événement Bj est égale a 1/n.

Soit E(n) l'ensemble des éventualités correspondant a l 'événement
<< l'opérateur n'a reconstitué aucune des paires initiales ». Les éventualités étant
toutes équiprobables, il s'agit de trouver la cardinalité de E(n) et de diviser par n!
pour obtenir la probabilité cherchée.



jusqu'ici l'explication est compréhensible. Cette seconde partie "un peu" moins



Pour n > 2, notons E (n,j) l'ensemble des éventualités de E(n) telles que l'opérateur
a connecté le récepteur de l'émetteur j a l'émetteur n.
Remarquons que (E(n,j)) pour j={1,...,(n-1)} est une partition de E(n).

Notons E(n,j,I) l'ensemble des éventualités de E(n,j) telles que l'opérateur a connecté
le récepteur de l'émetteur n a l'émetteur j. Désignons par E(n,j,Î) les autres éventualités de E(n,j) :

E(n,j,Î) = E(n,j)\E(n,j,I).

Ici, on a utilisé une nouvelle notation. De façon générale, la notation A\B qui désigne
les éventualités de l'événement A non comprises dans l'évènement B.
Le nombre d'éventualités de E(n,j,I) correspond au nombre de façons de connecter les
(n-2) émetteurs restants (en écartant les numéros j et n) aux (n-2) récepteurs,
initialement réglés avec ces (n-2) émetteurs, sans reformer aucun couple initial. Ce nombre est égal à |E(n-2)|.
Pour les éventualités de E(n,j,Î), l'émetteur j peut être associé à tout récepteur sauf le récepteur de n (et de j qui par définition est associé à, l'émetteur n). Le nombre d'éventualités est égal à la cardinalité de E(n—1).

On a donc :

|E(n,j,I)| = |E(n - 2)|
|E(n,j,Î)| = |E(n - 1)|

soit

|E(n,j)| = |E(n - 2)| + |E(n - 1)|

à partir de là l'exemple continue à développer la partie récursive. Je ne l'ai pas mis car pour l'instant j'ai déjà du mal à comprendre cette première partie. Les explications sont mot pour mot ce que j'ai dans mon livre j'ai vérifié si il n'avait pas d'erreur de retranscription.

Je ne parviens pas à comprendre la deuxième partie de l'explication. J'ai fait quelques essaies simples avec 3 récepteurs et 3 emetteurs ce qui donne 3! possibilités en tout soit 6 avec 4 récepteurs ont est déjà à 24 et pour comprendre ça devient trop compliqué.

soit (e1,e2,e3) et (r1,r2,r3) , les possibilités sont :

A = (e1,r1) ; (e2,r2) ; (e3,r3)
B = (e1,r1) ; (e2,r3) ; (e3,r2)
C = (e1,r2) ; (e2,r1) ; (e3,r3)
D = (e1,r2) ; (e2,r3) ; (e3,r1)
E = (e1,r3) ; (e2,r2) ; (e3,r1)
F = (e1,r3) ; (e2,r1) ; (e3,r2)

Donc les éventualités ou il ne rassemble aucunes des pièces appariés sont : D et F soit 2/6 , toutes les pièces : A. 1/6.

Dans l'exemple je ne comprend pas à quoi correspondent concrètement les événements E(n,j) E(n,j,I) et E(n,j,Î).

Merci d'avance à ceux et celles qui prendront le temps déjà de lire l'exemple et de m'aider à comprendre si ils y parviennent.

[pascal16]

de prime abord, avec tes notations :

E :
A = (e1,r1) ; (e2,r2) ; (e3,r3)
B = (e1,r1) ; (e2,r3) ; (e3,r2)
C = (e1,r2) ; (e2,r1) ; (e3,r3)
D = (e1,r2) ; (e2,r3) ; (e3,r1)
E = (e1,r3) ; (e2,r2) ; (e3,r1)
F = (e1,r3) ; (e2,r1) ; (e3,r2)

E (1,2) : (deux nombres différents)
C = (e1,r2) ; (e2,r1) ; (e3,r3)
D = (e1,r2) ; (e2,r3) ; (e3,r1)

E (1,2,I) : (que des mauvaise paires)
D = (e1,r2) ; (e2,r3) ; (e3,r1)

E (1,2,î) : (il y a au moins une paire bonne dans le reste)
C = (e1,r2) ; (e2,r1) ; (e3,r3)

il faut sommer les cardinaux de E (1,X,I) : pour X allant de 2 à N pour

[LB2]

J'ai l'impression que tu es victime d'une mauvaise notation...

Si j'ai bien compris il n'y a pas de nouvel indice I, juste les variables n et j, la marque I signifiant que E(n,j, I) correspond aux éventualités où :
- l'opérateur a connecté le récepteur de l'émetteur j a l'émetteur n
ET - l'opérateur a connecté le récepteur de l'émetteur n a l'émetteur j

Autrement dit, il a fait une inversion des paires (n,n) et (j,j) en (j,n) et (n,j)

Mais il existe de multiples autres façons de mélanger : ce que l'auteur appelle les E(n,j,Î).

Ce problème est très célèbre et connu dans la littérature sous différents noms comme : problème des dérangements de Montmort, problème des rencontres, problème des chapeaux, problème du postier ivre ...
Il a plusieurs variantes et la combinatoire derrière est souvent un peu difficile.

Cordialement

[aviateur]

Bonjour
On suppose qu'aucun émetteur a reçu le bon récepteur et E(n) désigne l'ensemble des permutations qui vérifie cela.
On raisonne pour j fixé.
On suppose de plus que l'émetteur n a reçu le récepteur j. On désigne par E(n,j) l'ensemble des permutations qui vérifie cela.
Clairement E(n,j) est un sous ensemble de E(n).

Maintenant il y a deux possibilités pour un élément de E(n,j)
l'émetteur j a reçu le récepteur n ou ne la pas reçu.
Ce qui fait que l'on a une partition de E(n,j) sous la forme union
où E(n,j,l) correspond aux permutations de E(n,j) telles que j a reçu le récepteur n
et correspond aux permutations de E(n,j) telles que j n'a pas reçu le récepteur n.
Naturellement on a alors |E(n,j)|= |E(n,j,l)|+|E(n,j,\hat{l})|
Ensuite il faut comprendre les valeurs données de |E(n,j,l)| et de |E(n,j,\hat{l})|.
Mais je m'arrête là pour le moment pour savoir si c'est ok pour l'instant.
Ensuite une chose à la fois dis ce que tu ne comprend pas.

[aviateur]

J'ai pas vu la réponse de LBL2
Oui la notation est lourde mais on peut faire avec .

[kaizokun]

Merci à vous pour vos contributions, je comprend mieux l'explication désormais. Je n'avais pas compris que n était fixe et que seul j changeait entre [1, n-1].

Donc effectivement avec mon exemple le plus simple ou n vaut 3 :

Pour j valant 1 soit E(e3,r1), on retrouve le cas D = (e1, r2) ; (e2, r3) ; (e3, r1)
E(3, 1, I) est le cas ou l'on connecterait le récepteur n à l'émetteur j ( une inversion comme disait LB2 ) soit le couple (e1, r3) . Ce cas n'existe pas dans E(e3, r1) étant donné qu'il ne resterait que la paire (e2,r2) ce qui ne permettrait pas à l' éventualité de faire parti de E(n). Pour finir E(n,j,Î) est égal à E(n,j) dans ce cas ci.

Pour les cardinalités on a la correspondance entre E(n,j,I) et E(n-2) soit ici E(1) qui est un ensemble vide, vu qu'il n 'y a qu'une façon de de connecter un unique emetteur et récepteur, la bonne .

Mais pour les cas ou n > 3, j'ai fait un test avec n = 4, c'est effectivement comme si on repartait d'un cas avec 2 emetteurs et 2 récepteurs, soit pour n = 4 et j = 1 en éliminant ces indices, on obtient une base (e2,e3)(r2,r3).
Qui donne un seul cas [[e:1, r:4], [e:2, r:3], [e:3, r:2], [e:4, r:1]]

Pour E(n,j,Î) comparé à E(n - 1) soit E(2), si on démarrait avec 2 émetteurs et 2 récepteurs (e1,e2) (r1,r2) on aurait que deux cas au total soit (e1,r2)(e2,r1) ou (e1,r1)(e2,r2). Ici ce serait comme si on démarrait plutôt avec (e1,e2) (r2,r3) donc en éliminant l'émetteur n et le récepteur j, soit les possibilités (e1,r2)(e2,r3) ou (e1,r3)(e2,r2). On n'a qu'un cas ou aucun n'est correct : (e1,r2)(e2,r3) soit le seul parmi E(2).
Dans mon test avec n = 4, E(4,1,Î) correspond au cas de E(4 - 1) en partant avec (e1,e2,e3) (r2,r3,r4) ou e1 n'est pas connecté à r4 .