Binary vectors with prescribed subsets of consecutive ones
type: Item
instance of: scholarly article
title: Binary vectors with prescribed subsets of consecutive ones
zbMATH Open document ID: 0643.05005
DOI: 10.1016/0097-3165(88)90017-9
author: Tom M. Apostol
published in: Journal of Combinatorial Theory. Series A
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05A15
zbMATH DE Number: 4047727
zbMATH Keywords: binary vectors
zbMATH Keywords: Generating functions
MaRDI profile type: Publication
full work available at URL: 0097-3165(88)90017-9
OpenAlex ID: W2034575894
cites work: String overlaps, pattern matching, and nontransitive games
description: scientific article; zbMATH DE number 4047727