Probabilitas string yang berisi semua karakter
Diberikan string yang panjangnya $n$, di $26$ huruf dalam alfabet bahasa Inggris, berapa probabilitasnya mengandung semua $26$ dari surat-surat itu?
Saya berpikir ke arah ini, (tetapi tidak dapat mencapai jawabannya).
Misalkan pertanyaan awal diberi panjang string, berapa probabilitasnya mengandung A
, dan itu akan menjadi 1 - (probabilitas tidak mengandung A
) jadi
Tapi saya tidak dapat memperluas ide ini ke banyak karakter. Bisakah seseorang membantu saya?
Jawaban
Dengan asumsi huruf-huruf tersebut dipilih dengan probabilitas yang sama, dan secara independen, maka masalahnya setara dengan: Lempar $n$ bola di dalam $m=26$ guci secara acak, berapakah probabilitas bahwa semua guci tidak kosong?
Jumlah total (jumlah string) jelas $m^n$. Peristiwa yang menguntungkan kurang mudah dihitung, Anda perlu menggunakan prinsip inklusi-pengecualian. Hasilnya diberikan oleh nomor Stirling dari jenis kedua , dan penjelasannya diberikan di sini .
Oleh karena itu hasil akhirnya adalah
$$ p = \frac{m! \, S_{n,m}}{m^n} $$