Infinite Products Associated with Counting Blocks in Binary Strings
Jean‐Paul Allouche, Jeffrey O. Shallit · Journal of the London Mathematical Society · 1989
Let w be a string of zeros and ones, and let aw(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 bw) such that ∑ n ⩾ 0 log 2 ( b w ( n ) ) X a w ( n ) = − 1 1 − X By 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 ) = 2 2 Our work is a generalization of previous results of D. Woods, D. Robbins, H. Cohen, M. Mendes France, and the authors.