Skip to main content
2 of 2
Fixed minor typos and notation
Gordon Royle
  • 12.7k
  • 1
  • 51
  • 73

Here is a small visualisation of the values of this function.

I have taken $n \in \{1,2,\ldots,512\}$ and calculated the proportion of the numbers $0 \leqslant x < 2^n$ that have a maximum 1-run of even length.

enter image description here

Obviously I can't compute directly the longest run for each of the integers smaller than $2^{512}$ but luckily the values can be computed symbolically.

The number of compositions (i.e., ordered partitions) of $n$ with largest part odd is equal to the number of integers in the range $0 \leqslant x < 2^{n-1}$ with largest 1-run of even length (via the "McMahon Graph" of a composition).

These values are listed in the OEIS at https://oeis.org/A103421 along with a generating function that can be computed symbolically by Mathematica for a reasonable range of values.

Gordon Royle
  • 12.7k
  • 1
  • 51
  • 73