Предложу вариант решения задачи "вероятность выпадения минимум 2
орлов подряд из n
попыток".
Будем обозначать орла и решку o
и p
, последовательность выпадений орла и решки за n
попыток словом длины n
(например, opoop
— подходящее слово длины 5).
Рассмотрим:
a_n
— количество слов длины n
, в которых нет 2
подряд орлов И которые оканчиваются на o
(для n = 3
имеем a_n = 2
: opo
, ppo
)
b_n
— количество слов длины n
, в которых нет 2
подряд орлов И которые оканчиваются на p
(для n = 3
имеем b_n = 3
: opp
, pop
, ppp
)
Тогда заметим:
a_n+1 = b_n
, потому что получить количество слов длины n+1
, в которых нет 2
подряд орлов И которые оканчиваются на o
, можно только добавлением o
к словам длины n
. Добавить o
, не получив 2
подряд o
, можно только к словам, оканчивающимся на p
b_n+1 = a_n + b_n
, потому что получить количество слов длины n+1
, в которых нет 2
подряд орлов И которые оканчиваются на p
, можно только добавлением p
к словам длины n
. Добавить p
, не получив 2
подряд o
, можно как к оканчивающимся на o
словам, так и к оканчивающимся на p
словам
Рассмотрим сумму:
a_n + b_n = <используем 1> = b_n-1 + b_n = <используем 2> = b_n-1 + a_n-1 + b_n-1 = <ещё раз используем 2> = (a_n-2 + b_n-2) + (a_n-1 + b_n-1)
Внезапно, получили, что последовательность сумм является последовательностью Фибоначчи. Рассмотрев базовые случаи (F_1
и F_2
), по индукции получаем, что a_n + b_n = F_n+2
.
Тогда слова длины n
, содержащие минимум 2
орла, находятся как все возможные слова (их 2^n
) минус слова, в которых нет 2
подряд o
(a_n + b_n = F_n+2
).
Итоговая вероятность: (2^n - F_n+2) / 2^n
.
Аналитически: (2^n - round(phi^n / sqrt(5)) / 2^n
, где phi = (1 + sqrt(5)) / 2
Примеры:
Для k
орлов можно использовать последовательности Фибоначчи k
-ого порядка, как указал участник @MBo в своём ответе. На Википедии как раз сказано, что "Последователь количеств строк из 0 и 1 длины m, содержащих не более n последовательных нулей, также является последовательностью Фибоначчи порядка n." и приводятся аналитические формулы для подсчёта членов таких последовательностей.
