A Generating Function for the Distribution of Runs in Binary Words

2017/07/13 by Madden, James J.
#05A15 (Primary) #60C05 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1707.04351

Abstract

Let N(n,r,k) denote the number of binary words of length n that begin with 0 and contain exactly k runs (i.e., maximal subwords of identical consecutive symbols) of length r. We show that the generating function for the sequence N(n,r,0), n=0,1,…, is (1-x)(1-2x + x^r-x^r+1)^-1 and that the generating function for \N(n,r,k)\ is x^kr time the k+1 power of this. We extend to counts of words containing exactly k runs of 1s by using symmetries on the set of binary words.

Related

• Subsequence frequency in binary words
• Counting occurrences of a pattern in a binary word
• Universal parameterized family of distributions of runs
• Generation of binary words avoiding alternating patterns
• The total run length of a word