Problemă de întâlnire

În matematică , problema întâlnirii , sau problema lui Montmort , sau chiar problema pălăriei , constă în determinarea probabilității ca, n jetoane numerotate de la 1 la n să fi fost puse la întâmplare în casete însele numerotate de la 1 la n , niciun jeton nu este în locul (sau cel al evenimentului opus). Într-un mod mai științific, este căutarea probabilității ca o permutare luată la întâmplare să fie o perturbare , adică nu are o „întâlnire”, cu alte cuvinte un punct fix .

Problema întâlnirilor a fost pusă pentru prima dată de Pierre Rémond de Montmort în 1708, care a rezolvat-o în 1713, în același timp cu Nicolas Bernoulli .

Diverse formulări ale problemei

Montmort scria în 1708: „Pierre are un anumit număr de cărți care nu se repetă și care sunt amestecate după bunul plac ; pariază împotriva lui Pavel că, dacă le atrage succesiv și că le numește în ordinea cărților, începând, fie cu cel mai mare, fie cu cel mai mic, se va întâmpla cel puțin o dată să tragă cel pe care îl va numi . Întrebăm care este soarta sau speranța lui Petru, pentru orice număr de cărți, de la două la treisprezece ” .

Acesta este jocul numit la acea vreme „joc de treisprezece”.

Leonhard Euler scria în 1753: „Jocul de întâlnire este un joc de noroc în care oamenii, fiecare având câte un pachet întreg de cărți, trag câte o carte după alta, până când se întâmplă să întâlnească aceeași carte: și apoi una dintre câștigă doi oameni. Cu toate acestea, atunci când o astfel de întâlnire nu se întâmplă deloc, atunci cealaltă dintre cele două persoane câștigă. Acestea fiind spuse, cerem probabilitatea ca una dintre aceste două persoane să câștige. "
Pierre Tédenat scria în 1821: „Cineva ține în mâini un pachet de cărți, numerotate n , care poartă numerele 1, 2, 3, …… n ale secvenței naturale, amestecate la întâmplare. El dă jos, la rândul său, aceste cărți pe o masă, pronunțând în același timp cuvintele unu, două, trei, în ordinea lor succesivă; care este probabilitatea ca cel puțin o dată să se întâmple, atunci când trageți în jos un card, să pronunțați în același timp numele numărului pe care îl poartă? "
Eugène Catalan pune problema în 1837 într-o formă similară cu cea a lui Euler și rezolvă o generalizare.
Formularea ca problemă cu pălării: „ n oameni își lasă pălăriile în vestiar; când vin să-i ridice, fiecare dintre ei ia o pălărie la întâmplare; care este probabilitatea ca niciunul dintre ei să nu poarte pălăria la ieșire? "

Vom folosi această piele mai târziu.

Deoarece Édouard Lucas , ne dăm o permutare printr - o poziție saturată cu spire pe un n x n tablă de șah ( n transformă, nici una dintre care este în angrenare cu o alta); este vorba de calcularea proporției pozițiilor saturate care nu au viraj pe o diagonală dată. În mod echivalent, putem lua în considerare cuvinte încrucișate cu o singură casetă neagră pe rând și pe coloană sau matrici cu doar una pe rând și pe coloană și în alte părți . $1$ ${\ displaystyle 0}$

Valorile numerice

Defecțiunile parțiale sunt suita A008290 a OEIS . Rândul corespunde numărului de elemente implicate (numărul de cărți din jocul de treisprezece, numărul deținătorilor de pălării sau numărul de ture pe tabla de șah a lui Edward Lucas). Linia corespunde tabloului clasic de șah; linia ar corespunde jocului modelat de Pierre de Montfort, dar la care a renunțat să calculeze și să publice: aproximarea este suficientă. Coloana corespunde numărului de elemente la locul lor: permutarea luată în considerare este o perturbare pentru . $nu$ ${\ displaystyle n = 8}$ ${\ displaystyle n = 13}$ ${\ displaystyle d_ {13,0} / 13! \ approx e ^ {- 1}}$ $k$ $k = 0$

${\ displaystyle _ {n} \! \! \ diagdown \! \! ^ {k}}$	0	1	2	3	4	5	6	7	8
0	1
1	0	1
2	1	0	1
3	2	3	0	1
4	9	8	6	0	1
5	44	45	20	10	0	1
6	265	264	135	40	15	0	1
7	1854	1855	924	315	70	21	0	1
8	14833	14832	7420	2464	630	112	28	0	1

Primul calcul utilizând formula Poincaré

Formula de Poincare : dă răspunsul, luând evenimentul „ a i pălăria - lea este în locul ei.“ ${\ displaystyle P \ left (\, \ bigcup _ {i = 1} ^ {n} A_ {i} \, \ right) = \ sum _ {k = 1} ^ {n} \ left ((- 1) ^ {k-1} \ sum _ {1 \ leq i_ {1} <i_ {2} <\ ldots <i_ {k} \ leq n} P (A_ {i_ {1}} \ cap A_ {i_ {2 }} \ cap \ ldots \ cap A_ {i_ {k}}) \ right)}$ $Avea}$

Într-adevăr este evenimentul (contrar celui căutat): „una dintre pălării este la locul său” și este evident valabilă astfel încât . ${\ displaystyle \ bigcup _ {i = 1} ^ {n} A_ {i}}$ ${\ displaystyle P (A_ {i_ {1}} \ cap A_ {i_ {2}} \ cap \ ldots \ cap A_ {i_ {k}})}$ ${\ displaystyle (nk)! / n!}$ ${\ displaystyle P \ left (\, \ bigcup _ {i = 1} ^ {n} A_ {i} \, \ right) = \ sum _ {k = 1} ^ {n} \ left ((- 1) ^ {k-1} {n \ alege k} {\ frac {(nk)!} {n!}} \ right) = \ sum _ {k = 1} ^ {n} {\ frac {(-1) ^ {k-1}} {k!}}}$

Și probabilitatea ca nici o pălărie să nu fie la locul său merită, prin urmare . ${\ displaystyle p_ {n} = \ sum _ {k = 0} ^ {n} {\ frac {(-1) ^ {k}} {k!}}}$

Această probabilitate tinde foarte repede și alternativ spre 1 / $e$ . Din n = 3 există deci aproximativ o șansă din trei ca nici o pălărie să nu fie deplasată. Și Petru are dreptate să parieze împotriva lui Pavel că va exista cel puțin o coincidență.

Noțiunea de sub-factorial

Numărul perturbațiilor n obiectelor merită, așadar, unde [ x ] denotă numărul întreg cel mai apropiat de x . Acest număr se numește sub-factorial de n și notat! n . ${\ displaystyle d_ {n} = n! p_ {n} = n! \ sum _ {k = 0} ^ {n} {\ frac {(-1) ^ {k}} {k!}} = \ left [{\ frac {n!} {e}} \ right]}$ $d_ {n}$

Primele valori sunt: după A000166 din OEIS . ${\ displaystyle d_ {n} =! n}$ ${\ displaystyle d_ {1} = 0, d_ {2} = 1, d_ {3} = 2, d_ {4} = 9, d_ {5} = 44, d_ {6} = 265, d_ {7} = 1854, d_ {8} = 14833}$

Putem exprima acest număr în formă integrală: . ${\ displaystyle d_ {n} = n! p_ {n} = \ sum _ {k = 1} ^ {n} (- 1) ^ {k} (nk)! {n \ alege k} = \ sum _ { k = 1} ^ {n} (- 1) ^ {k} {n \ alege k} \ int _ {0} ^ {+ \ infty} \ mathrm {e} ^ {- t} t ^ {nk} \ , \ mathrm {d} t = \ int _ {0} ^ {+ \ infty} \ mathrm {e} ^ {- t} (t-1) ^ {n} \, \ mathrm {d} t}$

Prin modificarea variabilelor , se obține cu formula exactă: . ${\ displaystyle p_ {n} = {\ frac {1} {\ mathrm {e}}} + {\ frac {(-1) ^ {n}} {\ mathrm {e} .n!}} \ int _ {0} ^ {1} \ mathrm {e} ^ {t} t ^ {n} \, \ mathrm {d} t}$

Al doilea calcul prin rezolvarea unui sistem triunghiular

Rețineți că orice permutare de n obiecte cu k puncte fixe se face dintr-o perturbare a complementului setului de puncte fixe ale acestuia; deoarece există modalități de a alege acest set, obținem: ${\ displaystyle {n \ alege k}}$

{\ displaystyle n! = \ sum _ {k = 0} ^ {n} {n \ alege k} d_ {k} \ qquad (1)}

Prin urmare, putem scrie sistemul liniar în : pentru p = 0, 1, ..., n a cărui așa-numită matrice „Pascal” este inversată clasic și dă ${\ displaystyle d_ {0}, \ dots, d_ {n}}$ ${\ displaystyle p! = \ sum _ {k = 0} ^ {p} {p \ alege k} d_ {k}}$

{\ displaystyle d_ {p} = \ sum _ {k = 0} ^ {p} (- 1) ^ {pk} {p \ choose k} k! = \ sum _ {k = 0} ^ {p} ( -1) ^ {k} {p \ alege k} (pk)! = P! \ Sum _ {k = 0} ^ {p} {\ frac {(-1) ^ {k}} {k!}} }

;

găsim valoarea de mai sus.

Varianta folosind funcția generator : relația face posibilă obținerea seriei pe produse ; și începând de la, valoarea așteptată este obținută invers . ${\ displaystyle f (x) = \ sum _ {n = 0} ^ {\ infty} p_ {n} x ^ {n} = \ sum _ {n = 0} ^ {\ infty} {\ frac {d_ { n}} {n!}} x ^ {n}}$ ${\ displaystyle n! = \ sum _ {k = 0} ^ {n} {n \ alege k} d_ {k}}$ ${\ displaystyle \ mathrm {e} ^ {x} f (x) = {\ frac {1} {1-x}}}$ ${\ displaystyle f (x) = \ mathrm {e} ^ {- x}. {\ frac {1} {1-x}}}$ ${\ displaystyle p_ {n} = \ sum _ {k = 0} ^ {n} {\ frac {(-1) ^ {k}} {k!}}}$

Al treilea calcul prin relație de recurență

Formula (1) de mai sus oferă o relație de recurență puternică :, let ${\ displaystyle d_ {n} = n! - \ sum _ {k = 0} ^ {n-1} {n \ alege k} d_ {k}}$

{\ displaystyle p_ {n} = 1- \ sum _ {k = 0} ^ {n-1} {\ frac {p_ {k}} {(nk)!}} = 1- \ left ({\ frac { p_ {0}} {n!}} + {\ frac {p_ {1}} {(n-1)!}} + ... + {\ frac {p_ {n-1}} {1!}} \ dreapta)}

Dar un raționament combinatoriu face posibilă obținerea relației de recurență dublă: din care deducem relația de recurență simplă: ${\ displaystyle d_ {n} = (n-1) (d_ {n-1} + d_ {n-2})}$

{\ displaystyle d_ {n} = nd_ {n-1} + (- 1) ^ {n}}

, este

{\ displaystyle p_ {n} = p_ {n-1} + {\ frac {(-1) ^ {n}} {n!}}}

ceea ce duce direct la formula de dare . $p_ {n}$

Dovada relației dublei recurențe

Să presupunem că cei n oameni sunt numerotați de la 1 la n, precum și n pălării.

Trebuie să găsim numărul de configurații în care nimeni nu ia pălăria cu același număr ca a lor. Să presupunem că prima persoană ia pălăria i . Există apoi două posibilități:

oricare persoană i nu ia pălăria 1. Acest caz este echivalent cu rezolvarea problemei cu persoane și pălării numerotate de la 2 la n ; $n-1$ $n-1$
sau persoana i ia pălăria 1. Acest caz este echivalent cu rezolvarea problemei cu restul de oameni și pălării. $n-2$ $n-2$

Deoarece există posibilități pentru i , obținem . $n-1$ ${\ displaystyle d_ {n} = (n-1) (d_ {n-1} + d_ {n-2})}$

Dovada trecerii la recidiva simplă

Prin pozare , relația este scrisă ; ${\ displaystyle u_ {n} = d_ {n} -nd_ {n-1}}$ ${\ displaystyle d_ {n} = (n-1) (d_ {n-1} + d_ {n-2})}$ ${\ displaystyle u_ {n} = - u_ {n-1}}$

prin urmare , de unde . ${\ displaystyle u_ {n} = (- 1) ^ {n-2} u_ {2} = (- 1) ^ {n}}$ ${\ displaystyle d_ {n} = nd_ {n-1} + (- 1) ^ {n}}$

Al patrulea calcul folosind defecțiuni parțiale

Fie numărul de configurații în care primii k oameni nu își poartă pălăria (sau numărul de permutări ale căror k primele elemente nu sunt fixate); prin urmare avem și . ${\ displaystyle d_ {n, k}}$ ${\ displaystyle d_ {n, 0} = n!}$ ${\ displaystyle d_ {n, n} = d_ {n}}$

Dintre aceste configurații, să distingem două categorii: aceea unde k + 1 nu are capacul său, care conține configurații; iar cea în care k + 1 are propria pălărie, care conține unele . ${\ displaystyle d_ {n, k}}$ ${\ displaystyle d_ {n, k + 1}}$ ${\ displaystyle d_ {n-1, k}}$

Atunci deducem . ${\ displaystyle d_ {n, k} = d_ {n, k + 1} + d_ {n-1, k}}$ ${\ displaystyle d_ {n, k} = d_ {n, k-1} -d_ {n-1, k-1}}$

Prin urmare, secvența este imaginea secvenței de către operator cu diferențe finite . ${\ displaystyle (d_ {n, k}) _ {n}}$ ${\ displaystyle (d_ {n, k-1}) _ {n}}$ ${\ displaystyle \ Delta (u_ {n}) = u_ {n} -u_ {n-1}}$

Deducem din aceasta . ${\ displaystyle d_ {n, k} = \ Delta ^ {k} (n!) = \ sum _ {q = 0} ^ {k} (- 1) ^ {q} {k \ alege q} (nq) !}$

Și din nou . ${\ displaystyle d_ {n} = \ Delta ^ {n} (n!) = \ sum _ {k = 0} ^ {n} (- 1) ^ {k} {n \ alege k} (nk)! = n! \ sum _ {k = 0} ^ {n} {\ frac {(-1) ^ {k}} {k!}}}$

Aplicarea legii, așteptarea și varianța numărului de puncte fixe ale unei permutări

Să X să fie variabila aleatoare dă numărul de oameni care poartă pălării proprii (sau numărul de puncte fixe ale unei permutări aleatoare de n obiecte).

Dacă există modalități de a alege acest set de puncte fixe, așa și bineînțeles . ${\ displaystyle X = k}$ ${\ displaystyle n \ alege k}$ ${\ displaystyle P (X = k) = {\ frac {n \ choose k} {n!}} d_ {nk} = {\ frac {1} {k!}} \ sum _ {q = 0} ^ { nk} {\ frac {(-1) ^ {q}} {q!}}}$ ${\ displaystyle P (X = 0) = p_ {n} = {\ frac {d_ {n}} {n!}}}$

Rețineți că pentru n mare în fața lui k și , prin urmare, X urmează aproximativ o distribuție Poisson cu parametru . ${\ displaystyle P (X = k) \ approx {\ frac {1} {\ mathrm {e} .k!}}}$ $1$

Pentru a obține așteptarea și varianța lui X , este mult mai rapid să observăm că X este suma , fiind egal cu dacă persoana a- i -a poartă pălăria, altfel. $X_ {i}$ $X_ {i}$ $1$ ${\ displaystyle 0}$

Variabila urmează o lege Bernoulli a parametrului 1 / n , prin urmare : există în medie o singură persoană care poartă propria pălărie. $X_ {i}$ ${\ displaystyle E (X) = 1}$

Pentru calculul variației dă: . ${\ displaystyle V (X) = 1}$

Generalizare: problema întâlnirilor cu obiecte tastate

Presupunem că n pălării sunt de p diferite tipuri: de tip 1, ..., de tip p ( ) și că există categorii p în rândul oamenilor: de categoria 1, ..., de categoria p ( ; pot exista persoane fără categorie); există o întâlnire dacă o persoană dintr-o anumită categorie ia o pălărie de un tip care are același număr: care este probabilitatea ca să nu existe o întâlnire? $n_1$ $n_p$ ${\ displaystyle n = n_ {1} + .. + n_ {p}}$ $m_1$ $m_p$ ${\ displaystyle n \ geqslant m_ {1} + .. + m_ {p}}$

Răspunsul complet este . ${\ displaystyle \ int _ {0} ^ {+ \ infty} {\ frac {\ mathrm {e} ^ {- t}} {n!}} \ prod _ {i = 1} ^ {p} \ left ( \ sum _ {k = 0} ^ {\ min (n_ {i}, m_ {i})} {\ left (-1 \ right) ^ {k} k! {n_ {i} \ choose k} {m_ {i} \ choose k}} t ^ {nk} \ right) \, \ mathrm {d} t}$

Probabilitatea ca o persoană să ia o pălărie de tip i merită , așteptarea numărului de întâlniri merită . ${\ displaystyle n_ {i} / n}$ ${\ displaystyle {\ frac {\ sum _ {i = 1} ^ {p} n_ {i} m_ {i}} {n}}}$

Problema simplă se obține atunci când sunt egale cu unde găsim și o așteptare de 1. $sau$ $1$ ${\ displaystyle \ int _ {0} ^ {+ \ infty} {\ frac {\ mathrm {e} ^ {- t}} {n!}} (t-1) ^ {n} \, \ mathrm {d } t}$

Următoarea problemă: „Afișarea succesivă a cărților unui pachet de 52 de cărți și anunțarea, înainte de a le privi: As, Rege, Regină etc., ce probabilitate am ca toate aceste anunțuri să fie false? » Revine la cazul în care și oferă o probabilitate și o așteptare a numărului de întâlniri de 4; pentru un pachet de 32 de cărți, găsim o probabilitate de aproximativ și întotdeauna o așteptare de 4. ${\ displaystyle n = 52, p = 13, n_ {i} = m_ {i} = 4}$ ${\ displaystyle \ int _ {0} ^ {+ \ infty} {\ frac {\ mathrm {e} ^ {- t}} {52!}} (t ^ {4} -16t ^ {3} + 72t ^ {2} -96t + 24) ^ {13} \, \ mathrm {d} t \ approx 1,6 \%}$ ${\ displaystyle 13.5 \%}$

Vezi și tu

Aplicații ale principiului includere-excludere

linkuri externe

Analiza textului lui Montmort
Suită în enciclopedia întregilor suitednu=LA000166(nu){\ displaystyle d_ {n} = A000166 (n)}
Suită în enciclopedia întregilor suitednu,k=LA047920(nu,k){\ displaystyle d_ {n, k} = A047920 (n, k)}
Suită în enciclopedia întregilor suitenu!P(X=k)=LA008290(nu,k){\ displaystyle n! P (X = k) = A008290 (n, k)}
Articol despre tulburări din aceeași enciclopedie

Note și referințe

Pierre Rémond de Montmort, Eseu de analiză a jocurilor de noroc , Paris,1708( citiți online ) , p. 54, Pierre Rémond de Montmort, Eseu de analiză a jocurilor de noroc , Paris,1713( citiți online ) , p. 130.
Euler, „ Calculating Probability in the Match Game ”, Memoriile Academiei de Științe din Berlin , vol. 7,1753, p. 255-270 ( prezentare online , citire online )( prezentat în 1751 ).
Tédenat, „ Soluția problemei întâlnirilor ”, Annales de Gergonne , vol. 12, 1821-1822, p. 120-134 ( citește online ).
E. Catalană, „ Soluția unei probleme de probabilitate în ceea ce privește jocul de dating ,“ JMPA , 1 st serie, voi. 2,1837, p. 469-482 ( citiți online ).
Louis Comtet , Analiza combinatorie , t. 2, Paris, PUF ,1970, p. 9-12 și 32.
J. Moreau de Saint-Martin, " Problema întâlnirilor ", Quadrature , vol. 61,2006, p. 14-19.
Calcul pe mathcpge.org.