Skip to content
Quantoros

Count binary strings for which length plus number of ones equals n. Different lengths are allowed.

Quant ResearchLevel: IntermediateWeighted binary strings

Count binary strings for which length plus number of ones equals n. Different lengths are allowed.

Hints
  • Translate each symbol into a contribution to n.
  • Split by the last symbol.

Answer

A zero consumes weight 1 and a one weight 2. The final symbol gives a_n=a_(n-1)+a_(n-2), with a0=1 and a1=1. Thus a_n=F_(n+1). This is counting compositions of n into 1s and 2s, not fixed-length bit strings.

Source and licence: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · answer: Quantoros editorial

Related questions