No label defined (Q3324028)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3855207
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3855207 |
Statements
1984
0 references
enumeration problems
0 references
number of binary numbers
0 references
modified Fibonacci sequence
0 references
Pascal-T triangle
0 references
failure probability
0 references
0.7203112
0 references
0.7147014
0 references
0.7124107
0 references
0.7047394
0 references
0.6998443
0 references
0.6997662
0 references
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.
0 references