Probabilitas string yang berisi semua karakter

Aug 20 2020

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

1 leonbloy Aug 20 2020 at 21:11

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} $$