×

On the distribution of the number of ones in a Boolean Pascal’s triangle. (English. Russian original) Zbl 1128.60010

Discrete Math. Appl. 16, No. 3, 271-279 (2006); translation from Diskretn. Mat. 18, No. 2, 123-131 (2006).
Summary: This research is devoted to estimating the number of Boolean Pascal’s triangles of large enough size \(s\) containing a given number of ones \(\xi \leq ks\), \(k > 0\). We demonstrate that any such Pascal’s triangle contains a zero triangle whose size differs from \(s\) by at most a constant depending only on \(k\). We prove that there is a monotone unbounded sequence of rational numbers \(0 = k_{0} < k_{1} < \cdots\) such that the distribution of the number of triangles is concentrated in some neighbourhoods of the points \(k_{i}s\). The form of the distribution in each neighbourhood depends not on \(s\) but on the remainders of \(s\) modulo \(2^{\rho_i}\) for some \(i \geq 0\).

MSC:

60C05 Combinatorial probability
05A05 Permutations, words, matrices
05A15 Exact enumeration problems, generating functions
60F05 Central limit and other weak theorems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Malyshev E. V, Review Industrial and Appl. Math. 11 pp 245– (2004)
[2] Discrete Appl. Math. 105 pp 1– (2000)
[3] Crespo Ch., Chaos Solitons Fractals 6 pp 105– (1995)
[4] G. A. Maraon, L. H. Encinas, and A. M. del Rey, Sharing secret color images using cellular automata with memory. http://arxiv.org/abs/cs/0312034, 2003.
[5] S. Wolfram, Cellular automata as simple self-organizing systems. Caltech preprint CALT-68-938, 1982.
[6] S. Wolfram, Cellular automata. Los Alamos Sci. (1983) 9, 2-21.
[7] Rev. Mod. Phys. 55 pp 601– (1983)
[8] Physica 10 pp 1– (1984)
[9] Wolfram O., Comm. Math. Phys. 93 pp 219– (1984)
[10] Comm. Math. Phys. 96 pp 15– (1984)
[11] Physica Scripta 9 pp 170– (1985)
[12] S. Wolfram, Theory and Applications of Cellular Automata. World Scientific, Singapore, 1986. · Zbl 0609.68043
[13] Lecture Notes Comput. Sci. 218 pp 429– (1986)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.