On a paper of Agur, Fraenkel and Klein (Q1182978)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On a paper of Agur, Fraenkel and Klein
scientific article

    Statements

    On a paper of Agur, Fraenkel and Klein (English)
    0 references
    0 references
    28 June 1992
    0 references
    For given sets \(A\) and \(B\) of positive integers and each \(n\geq 1\), define \(S(A,B;n)\) to be the set of vectors \((x_ 1,x_ 2,\dots,x_ n)\) in \(\{0,1\}^ n\) which do not contain a subvector \((x_ j,x_{j+1},\dots,x_{j+c+1})\) of the form \((1,0,0,\dots,0,0,1)\) (with \(c\) zeros) for any \(c\notin A\) or the form \((0,1,1,\dots,1,1,0)\) (with \(c\) ones) for any \(c\notin B\) (here the indices of the \(x_ i\)'s are taken \(\text{mod} n\)). The author establishes the following theorem. For any given sets \(A\) and \(B\) of positive integers, \[ \sum_{n\geq 1}\Psi(A,B;n)x^ n=-x{d\over dx}\log(1-f(x)g(x)), \] where \(f(x)=\sum_{a\in A}x^ a\) and \(g(x)=\sum_{b\in B}x^ b\). \textit{Z. Agur}, \textit{A. S. Fraenkel} and \textit{S. T. Klein} [Discrete Math. 70, No. 3, 295-302 (1988; Zbl 0659.05004)] considered the two cases \(A=B=\{\text{integers } n\geq 2\}\) and \(A=B=\{1,2\}\) and derived an equivalent result by a different method.
    0 references
    0 references
    counting binary strings
    0 references
    0 references