This site is supported by donations to The OEIS Foundation.



Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A298072 Number of binary strings of length n that are "prefix heavy", meaning that the fraction of "1" bits in any nonempty prefix is at least as great as the fraction of "1" bits in the entire string. 2
1, 2, 3, 4, 6, 8, 15, 20, 40, 64, 126, 188, 434, 632, 1391, 2428, 4826, 7712, 17744, 27596, 62468, 106934, 220288, 364724, 834200, 1384470, 2954760, 5187588, 11085712, 18512792, 42379925, 69273668, 152600856, 268881898, 570336966, 1023023000, 2205306276 (list; graph; refs; listen; history; text; internal format)



If each "1" is interpreted as a unit step to the north and each "0" is interpreted as a unit step to the east, then a prefix heavy string is any string for which the path taken as the bits of the string are examined from left to right has the property that the path does not go southeast of the line segment connecting the start of the path to the end of the path.

Every Dyck word, that is, every balanced string of parentheses, with "(" identified as "1" and ")" identified as "0", is prefix heavy because the fraction of "1" bits in the entire string is necessarily 0.5 and each prefix of nonzero length has at least half of its positions with a "1" bit.  That is, each prefix has at least as many "(" characters as it has ")" characters.

Provably, a(n) is even if n is odd because there is a one-to-one relationship between a prefix heavy string with fewer than n/2 "1" bits and its reverse complement with more than n/2 "1" bits.

Provably, a(n) is odd if and only if n+2 is an integer power of 2.  That is, a(n) is odd if and only if there are strings with exactly n/2 "1" bits (n is even) and there are an odd number of them that are prefix heavy (A000108(n/2) is odd).


Lee A. Newberg, R code and Table of n, a(n) for n = 0..1024


a(n) = 2 + Sum_{k=1..n-1} A071201(n-k,k) for n>0.

a(2n) >= A000108(n) because Dyck words are prefix heavy.


For n=2, the a(2)=3 prefix heavy strings of length 2 are 00, 10, and 11, because each prefix of nonzero length is constituted of at least 0%, 50%, or 100% "1" bits, respectively.

For n=6, the a(6)=15 prefix heavy strings of length 6 are 000000, 100000, 100100, 101000, 101010, 101100, 110000, 110010, 110100, 110110, 111000, 111010, 111100, 111110, and 111111.


Cf. A000108, A071201.

Sequence in context: A219186 A049708 A000031 * A111023 A261751 A294679

Adjacent sequences:  A298069 A298070 A298071 * A298073 A298074 A298075




Lee A. Newberg, Jan 11 2018


a(28)-a(36) from Alois P. Heinz, Jan 11 2018



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 10:53 EST 2019. Contains 319271 sequences. (Running on oeis4.)