Premium
Infinite Products Associated with Counting Blocks in Binary Strings
Author(s) -
Allouche J.-P.,
Shallit J. O.
Publication year - 1989
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/s2-39.2.193
Subject(s) - combinatorics , generalization , mathematics , binary number , function (biology) , string (physics) , rational function , discrete mathematics , arithmetic , pure mathematics , mathematical analysis , evolutionary biology , mathematical physics , biology
Let w be a string of zeros and ones, and let a w ( n ) be the function which counts the number of (possibly overlapping) occurrences of w in the binary expansion of n . We show that there exists an effectively computable rational function b w ) such that∑ n ⩾ 0log 2 ( b w ( n ) )X a w ( n )= − 11 − XBy setting X = − 1 and exponentiating, we recover previous results and also obtain some new ones; for example,∏ n ⩾ 1(2 n 2 n + 1)( − 1 )a 0 ( n )=22Our work is a generalization of previous results of D. Woods, D. Robbins, H. Cohen, M. Mendes France, and the authors.