scientific article; zbMATH DE number 3855207

From MaRDI portal
Publication:3324028





The author employs a modified version of the Fibonacci sequence of order \(k\) of the reviewer and \textit{A. A. Muwafi} [ibid. 20, 28--32 (1982; Zbl 0476.60008)] and the Pascal-\(T\) triangle of order \(k\) of \textit{S. J. Turner} [ibid. 17, 23--28 (1979; Zbl 0424.60010)] to solve a number of enumeration problems involving the number of binary numbers of length \(n\) which have (or do not have) a string of \(k\) consecutive ones, subject to various auxiliary conditions. More precisely, the sequence \(\{f_k(n)\}^{\infty}_{n=0}\), \(k\geq 0\) is defined by the author to be the modified Fibonacci sequence of order \(k\) if \(f_0(n)=0\), \(f_1(n)=1\), and for \(k\geq 2\), \(f_k(n)=2^n\) if 0\(\leq n\leq k-1\), and \(f_k(n)=\sum^{n-1}_{i=n-k}f_k(i)\) if \(n\geq k\). Furthermore, he denotes by \(C_k(m,n)\) the entry of row \(m\) and column \(n\) in the Pascal-\(T\) triangle of order \(k\) \((k,m,n\geq 0).\) The author then derives the following results: Theorem 3.1. The number of binary numbers of length \(n\) which have no \(k\) consecutive ones is given by \(f_ k(n)\), \(n\geq 0\). Corollary 3.1. The number of binary numbers of length \(n\) which end with \(k\) consecutive ones but have no other string of \(k\) consecutive ones is given by \(f_k(n-k-1)\), \(n\geq k\), where \(f_k(- 1)=1\). Theorem 3.2. The number of binary numbers of length \(n\) which have a longest string of exactly \(k\) consecutive ones is given by \(f_{k+1}(n)- f_k(n)\), \(n\geq 1\). Theorem 3.3. The number of binary numbers of length \(n\) that have a total of \(j\) ones, no \(k\) consecutive, is given by \(C_k(n-j+1,j)\). Corollary 3.3. The number of binary numbers of length \(n\) that have a total of \(j\) ones and a string of ones of length at least \(k\) is given by \(\binom{n}{j} - C_ k(n-j+1,j)\equiv r_j^{(k)}.\) This last result implies that the failure probability \(P_f(n,k)\) of a ``consecutive-\(k\)-out-of-\(n\):\(F\) system [see the author and \textit{A. A. Salvia}, IEEE Trans. Reliab. R-31, 53--56 (1982; Zbl 0482.90032)] is given by \(P_f(n,k)=\sum^{n}_{j=k}r_j^{(k)}p^{n-j}q^j.\) The author notes that Theorem 3.1 and Corollary 3.1 have also been derived (implicitly and explicitly) by the reviewer and Muwafi [loc. cit.]. Reviewer's remark: In a forthcoming paper by the reviewer and \textit{Makri} [ibid. 23, 338--346 (1985; Zbl 0575.60022)], the present Theorems 3.1 and 3.2 are obtained as simple corollaries of a theorem on longest success runs and Fibonacci-type polynomials.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3324028)