Oto inne podejście, które nie wymaga rekurencji. Nadal jednak wykorzystuje sumy i produkty, których długości zależą od parametrów. Najpierw dam wyraz, a potem wyjaśnię.
Mamy
P(|L1∩L2∩⋯∩Lm|=k)=(nk)∏ni=1(nai)∑j=0min(a1,…,am)−k(−1)j(n−kj)∏l=1n(n−j−kal−j−k).
EDYCJA: Pod koniec pisania tego wszystkiego zdałem sobie sprawę, że możemy nieco skonsolidować powyższe wyrażenie, łącząc współczynniki dwumianowe w prawdopodobieństwa hipergeometryczne i współczynniki trójmianowe. Jeśli chodzi o wartość, zmienione wyrażenie to
Tutaj jest losową zmienną hipergeometryczną, w której losowania są pobierane z populacji o wielkości mającej stanów powodzenia.
∑j=0min(a1,…,am)−k(−1)j(nj,k,n−j−k)∏l=1nP(Hyp(n,j+k,al)=j+k).
Hyp(n,j+k,al)alnj+k
Pochodzenie
Zdobądźmy notację, aby nieco łatwiej śledzić argumenty kombinatoryczne (miejmy nadzieję). Przez cały czas uważamy i naprawione. Użyjemy do oznaczenia kolekcji uporządkowanych -tuple , gdzie każdy , spełniającySa1,…,amC(I)m(L1,…,Lm)Li⊆S
- |Li|=ai ; i
- L1∩⋯∩Lm=I .
Użyjemy również dla kolekcji identycznej, z tym że wymagamy zamiast równości.C′(I)L1∩⋯∩Lm⊇I
Kluczową obserwacją jest to, że można stosunkowo łatwo policzyć. Jest tak, ponieważ warunek jest równoważny dla wszystkich , więc w pewnym sensie usuwa interakcje między różnymi wartościami . Dla każdego liczba spełniająca wymagania wynosi , ponieważ możemy zbudować taki , wybierając podzbiór o rozmiarzea następnie unioning z . Wynika, że
C′(I)L1∩⋯∩Lm⊇ILi⊇IiiiLi(|S|−|I|ai−|I|)LiS∖Iai−|I|I
|C′(I)|=∏i=1n(|S|−|I|ai−|I|).
Teraz nasze pierwotne prawdopodobieństwo można wyrazić za pomocą w następujący sposób:
C
P(|L1∩L2∩⋯∩Lm|=k)=∑I:|I|=k|C(I)|∑all I⊆S|C(I)|.
Możemy od razu wprowadzić dwa uproszczenia. Po pierwsze, mianownik jest taki sam jak
Po drugie, argument permutacji pokazuje, żezależy tylko od poprzez liczność. Ponieważ istnieje podzbiory o liczności wynika, że
gdzie jest arbitralnym, stałym podzbiorem o liczności
|C′(∅)|=∏i=1n(|S|ai)=∏i=1n(nai).
|C(I)|I|I|(nk)Sk∑I:|I|=k|C(I)|=(nk)|C(I0)|,
I0Sk .
Cofając się o krok, zredukowaliśmy problem do pokazania, że
|C(I0)|=∑j=0min(a1,…,am)−k(−1)j(n−kj)∏l=1n(n−j−kal−j−k).
Niech będą odrębnymi podzbiorami utworzonymi przez dodanie dokładnie jednego elementu do . Następnie
(To po prostu mówi, że jeśli , to zawiera ale również nie zawiera żadnego dodatkowego elementu.) Przekształciliśmy teraz problem zliczania problem zliczania , o którym wiemy więcej, jak sobie z tym poradzić. Mówiąc dokładniej, mamy
J1,…,Jn−kSI0
C(I0)=C′(I0)∖(⋃i=1n−kC′(Ji)).
L1∩⋯∩Lm=I0L1∩⋯∩LmI0CC′|C(I0)|=|C′(I0)|−∣∣∣⋃i=1n−kC′(Ji)∣∣∣=∏l=1n(n−kal−k)−∣∣∣⋃i=1n−kC′(Ji)∣∣∣.
Możemy zastosować wykluczenie włączenia, aby obsłużyć wielkość wyrażenia unii powyżej. Kluczową zależnością jest tutaj to, że dla każdego niepustego ,
Dzieje się tak, ponieważ jeśli zawiera pewną liczbę , to również zawiera ich związek. Zauważamy również, że zestaw ma rozmiar. W związku z tym
I⊆{1,…,n−k}
⋂i∈IC′(Ji)=C′(⋃i∈IJi).
L1∩⋯∩LmJi⋃i∈IJi|I0|+|I|=k+|I|∣∣∣⋃i=1n−kC′(Ji)∣∣∣=∑∅≠I⊆{1,…,n−k}(−1)|I|−1∣∣∣⋂i∈IC′(Ji)∣∣∣=∑j=1n−k∑I:|I|=j(−1)j−1∏l=1n(n−j−kal−j−k)=∑j=1n−k(−1)j−1(n−kj)∏l=1n(n−j−kal−j−k).
(Możemy tutaj ograniczyć wartości , ponieważ iloczyn współczynników dwumianowych wynosi zero, chyba że dla wszystkich , tj. .)
jj≤al−klj≤min(a1,…,am)−k
Na koniec, podstawiając wyrażenie na końcu do równania napowyżej i konsolidując sumę, otrzymujemy
jak twierdzono.|C(I0)|
|C(I0)|=∑j=0min(a1,…,am)−k(−1)j(n−kj)∏l=1n(n−j−kal−j−k)