Умова

На внутрішній стороні обгортки кожної шоколадки серії «Великий Математик» зображений один із \(n\) видатних математиків, причому портрети кожного з них зустрічаються з однаковою ймовірністю \(1/n.\) Яка ймовірність того, що саме після придбання \(k\)-ої шоколадки \((k \ge n)\) матимемо повну колекцію з цієї серії?

Розв’язок

Нехай елементи простору елементарних подій \(\Omega=\{n, n+1, n+2, . . . \}\) відповідають кількості придбаних шоколадок до моменту, коли вперше було отримано повну колекцію портретів видатних математиків. Ми шукаємо ймовірність події \(A=\{k\}\), але для пошуку \(P(A)\) зручніше буде роглянути інший простір елементарних подій (скінченний), елементами якого будуть усі варіанти отримання портретів при придбанні лише перших \(k\) шоколадок. Потужність такого (нового скінченного) простору елементарних подій, очевидно, буде дорінювати \(n^k,\) бо кожна із \(k\) шоколадок може містити один із \(n\) портретів. Скільки ж є варіантів таких послідовно придбаних \(k\) шоколадок, коли вперше саме після придбання \(k\)-ої шоколадки \((k \ge n)\) матимемо повну колекцію з цієї серії? За комбінаторним правилом добутку кількість таких варіантів є добутком \(S(k-1, n-1)\cdot (n-1)! \cdot n\), де множник \(n\) відповідає за те, портрет якого з математичків був отриманий на \(k\)-му кроці (а до цього його не було), множник \(S(k-1, n-1)\) є кількістю розкладів послідовності перших \(k-1\) покупок (шоколадок) на \(n-1\) групу (портрети решти математиків), а множник \((n-1)!\) є кількістю способів приписування портретів обраним підгрупам. Здається, що все не так і складно, але нажаль величини \(S(k-1, n-1)\) не мають простого аналітичного представлення. Це так звані числа Стірлінга 2-го роду і один із способів їхнього подання є така сума з біноміальними коефіцієнтами: \[ S(a, b) = \frac{1}{b!} \sum_{i=0}^{b} (-1)^{b - i} \binom{b}{i} i^a \]

Відповідь: \( \dfrac{S(k-1, n-1)n!}{n^k}. \)

Перевірка Для перевірки отриманого результату напишемо програму мовою Javascript. Спочатку напишемо функцію \(probability(n, k)\), яка дозволить обчислювати знайдену нами ймовірність безпосередньо:

function factorial(n) {
    return n === 0 ? 1 : n * factorial(n - 1);
}

function comb(n, k) {
    return factorial(n) / (factorial(k) * factorial(n - k));
}

function probability(n, k) {
    if (k < n) {
        return 0; // Якщо кількість шоколадок менша ніж кількість портретів, то ймовірність дорівнює 0
    }
    let total_prob = 0;
    for (let i = 0; i < n; i++) {
        total_prob += Math.pow(-1, n - 1 - i) * comb(n - 1, i) * Math.pow(i, k - 1);
    }
    return (total_prob * n) / Math.pow(n, k);
}

// Приклад використання
const n = 4;
const k = 5;
console.log("Probability:", probability(n, k));

Тепер проведемо імітаційне моделювання нашого експерименту:

const n = 4;
const k = 5;

const N = 10000000;
let M = 0;

function experiment() {
    let a = new Array(n).fill(0);
    let s = 0;
    let count = 0;
    while (s < n) {
        count++;
        let t = Math.floor(Math.random() * n) % n;
        if (a[t] === 0) {
            s++;
            a[t] = 1;
        }
    }
    return count;
}

for (let i = 0; i < N; i++) {
    if (experiment() === k) {
        M++;
    }
}

console.log("Prob =", probability(n,k));
console.log("Freq =", M / N);

Результат роботи цієї програми:

Prob = 0.140625
Freq = 0.1407175

підтверджує правильність отриманого результату.