Binary vectors with prescribed subsets of consecutive ones
Let \(A_ k^{(m)}(n)\) denote the number of binary vectors of length n containing exactly k isolated m-tuples of consecutive ones. It is shown that, for \(k\geq 2\), \(m\geq 1\) and \(n\geq km+k-1\), \[ A_ k^{(m)}(n+1)=2A_ k^{(m)}(n)-A_ k^{(m)}(n-m)+2A^{(m)}_{k- 1}(n-m)-A^{(m)}_{k-2}(n-m). \] Tables of values for \(1\leq m\leq 5\), \(k\leq 5\), \(n\leq 25\) are given. Generating functions are also obtained: if \(F_ k^{(m)}(x)=\sum^{\infty}_{n=1}A_ k^{(m)}(n)x^ n\) and \(Q(x)=1-2x+x^{m+1}-x^{m+2}\) then, for \(k\geq 1\) and \(m\geq 2\), \[ F_ k^{(m)}(x)=x^{km+k-1}(1-x)^{k+1}Q(x)^{-k-1}. \] It is noted that this generating function can be extracted from a general class given by \textit{L. Guibas} and \textit{A. Odlyzko} [J. Comb. Theory, Ser. A 30, 183-208 (1981; Zbl 0454.68109)], although the present approach is more elementary and direct.
scientific article; zbMATH DE number 4047727