К содержанию
Quantoros

Сколько бинарных строк, у которых длина плюс число единиц равны n? Длины могут различаться.

Quant ResearchУровень: ПрактикаWeighted binary strings

Сколько бинарных строк, у которых длина плюс число единиц равны n? Длины могут различаться.

Подсказки
  • Выразите вклад каждого символа в n.
  • Разделите случаи по последнему символу.

Ответ

Ноль имеет вес 1, единица — 2. По последнему символу a_n=a_(n-1)+a_(n-2), a0=a1=1, значит a_n=F_(n+1). Это композиции n из 1 и 2, а не строки фиксированной длины.

Источник и лицензия: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · ответ: редакция Quantoros · перевод: Quantoros

Похожие вопросы