Numery Rencontres - Rencontres numbers

W kombinatorycznych matematycznych , że numery rencontres są trójkątne tablica z liczb całkowitych , że Wyliczanie permutacji z zestawu {1, ...,  N  } z określonej liczby stałych punktów : innymi słowy, częściowych zaburzeniami . ( Rencontre to po francusku „ spotkanie” . Według niektórych źródeł problem nosi nazwę pasjansa .) Dla n  ≥ 0 i 0 ≤ k  ≤  n , liczba rencontres D _{n ,  k} jest liczbą permutacji { 1, .. .,  n  }, które mają dokładnie k stałych punktów.

Na przykład, jeśli siedem prezentów zostanie przekazanych siedmiu różnym osobom, ale tylko dwa mają otrzymać właściwy prezent, istnieje D _{7, 2}  = 924 sposoby, w jakie może się to wydarzyć. Innym często przytaczanym przykładem jest szkoła tańca z 7 parami, gdzie po przerwie na herbatę uczestnikom każe się losowo znaleźć partnera, aby kontynuować, po czym ponownie D _{7, 2}  = 924 możliwości, że 2 poprzednie pary spotykają się ponownie przez przypadek.

Wartości liczbowe

Oto początek tej tablicy (sekwencja A008290 w OEIS ):

k n	0	1	2	3	4	5	6	7
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

Formuły

Liczby w  kolumnie k = 0 wyliczają odchylenia . Zatem

${\ Displaystyle D_ {0,0} = 1, \!}$

${\ Displaystyle D_ {1,0} = 0, \!}$

${\ Displaystyle D_ {n + 2,0} = (n + 1) (D_ {n + 1,0} + D_ {n, 0}) \!}$

dla nieujemnych n . Okazało się, że

${\ Displaystyle D_ {n, 0} = \ lewo \ lceil {\ Frac {n!} {e}} \ prawo \ r podłoga,}$

gdzie stosunek jest zaokrąglany w górę dla parzystego n i zaokrąglany w dół dla nieparzystego n . Dla n  ≥ 1 daje to najbliższą liczbę całkowitą.

Ogólnie rzecz biorąc, dla każdego mamy ${\displaystyle k\geq 0}$

${\ Displaystyle D_ {n, k} = {n \ wybierz k} \ cdot D_ {nk, 0}.}$

Dowód jest prosty, gdy umie się wyliczać odchylenia: wybierz k punktów stałych spośród n ; następnie wybierz obłąkanie pozostałych n  −  k punktów.

Liczby D _{n ,0} /( n !) są generowane przez szereg potęgowy e ^{− z} /(1 − z ) ; w związku z tym wyraźny wzór na D _{n ,  m} można wyprowadzić w następujący sposób:

${\ Displaystyle D_ {n, m} = {\ Frac {n!} {m!}} [z ^ {nm}] {\ Frac {e ^ {-z}} {1-z}} = {\ Frac {n!}{m!}}\sum _{k=0}^{nm}{\frac {(-1)^{k}}{k!}}.}$

To od razu sugeruje, że

${\ Displaystyle D_ {n, m} = {n \ wybierz m} D_ {nm, 0} \; \; {\ mbox {i}} \; \; {\ Frac {D_ {n, m}} {n !}}\ok {\frac {e^{-1}}{m!}}}$

dla n duże, m stałe.

Rozkład prawdopodobieństwa

Suma wpisów w każdym wierszu dla tabeli w „ Wartościach liczbowych ” jest całkowitą liczbą permutacji { 1, ...,  n  }, a zatem n !. Jeśli podzielimy wszystkie wpisy w n- tym wierszu przez n !, otrzymamy rozkład prawdopodobieństwa liczby stałych punktów jednolicie rozłożonej losowej permutacji { 1, ...,  n  }. Prawdopodobieństwo, że liczba punktów stałych wynosi k wynosi

${\ Displaystyle {D_ {n, k} \ ponad n!}.}$

Dla n  ≥ 1 oczekiwana liczba punktów stałych wynosi 1 (fakt wynikający z liniowości oczekiwań).

Mówiąc bardziej ogólnie, dla I  ≤  n , I th chwila tego rozkładu prawdopodobieństwa jest I th moment rozkładu Poissona z wartością oczekiwaną 1. Dla I  >  n , I th moment jest mniejszy od tego rozkładu Poissona. W szczególności, dla i  ≤  n , i- ty moment jest i- tą liczbą Bella , tj. liczbą partycji zbioru o rozmiarze i .

Ograniczenie rozkładu prawdopodobieństwa

Wraz ze wzrostem rozmiaru zestawu permutowanego otrzymujemy

${\ Displaystyle \ lim _ {n \ do \ infty} {D_ {n, k} \ nad n!} = {e ^ {-1} \ nad k!}.}$

Jest to tylko prawdopodobieństwo, że zmienna losowa o rozkładzie Poissona o wartości oczekiwanej 1 jest równa k . Innymi słowy, gdy n rośnie, rozkład prawdopodobieństwa liczby stałych punktów losowej permutacji zbioru o rozmiarze n zbliża się do rozkładu Poissona o wartości oczekiwanej 1.

Zobacz też

• Problem Oberwolfach , inny problem matematyczny polegający na rozmieszczeniu gości przy stołach
• Problème des ménages , podobny problem dotyczący częściowych zaburzeń

Bibliografia

• Riordan, John , An Introduction to Combinatorial Analysis , Nowy Jork, Wiley, 1958, strony 57, 58 i 65.
• Weisstein, Eric W. „Częściowe zaburzenia” . MatematykaŚwiat .