Geodesic
Distribution of the extreme values of the number of ones in Boolean analogues of the Pascal triangle
Diskretnaya Matematika, Tome 28 (2016) no. 3, pp. 59-96

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper is concerned with estimating the number $\xi$ of ones in triangular arrays consisting of elements of the field $GF(2)$ which are defined by the bottom row of $s$ elements. The elements of each higher row are obtained (as in Pascal triangles) by the summation of pairs of elements from the corresponding lower row. It is shown that there exists a monotone unbounded sequence $0=k_0$ of rational numbers such that, for any $k>0$, for sufficiently large $s$ the admissible values of $\xi$ which are smaller than $ks$ or larger than $s(s+1)/3-sk/3$ are concentrated in neighbourhoods of points $k_is$ and $s(s+1)/3-sk_i/3$, $i\geqslant0$. The resulting estimates of the neighbourhoods are functions of $i$ for each $i\geqslant0$ and do not depend on $s$. The distributions of the numbers of triangles with values $\xi$ in these neighbourhoods depend only on the residues of $s$ with respect to moduli that depend on $i\geqslant0$.
Mots-clés : Pascal triangle, (0-1)-matrix
Keywords: extreme combinatorial configuration. 
F. M. Malyshev. Distribution of the extreme values of the number of ones in Boolean analogues of the Pascal triangle. Diskretnaya Matematika, Tome 28 (2016) no. 3, pp. 59-96. http://geodesic.mathdoc.fr/item/DM_2016_28_3_a5/
@article{DM_2016_28_3_a5,
     author = {F. M. Malyshev},
     title = {Distribution of the extreme values of the number of ones in {Boolean} analogues of the {Pascal} triangle},
     journal = {Diskretnaya Matematika},
     pages = {59--96},
     year = {2016},
     volume = {28},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2016_28_3_a5/}
}
TY  - JOUR
AU  - F. M. Malyshev
TI  - Distribution of the extreme values of the number of ones in Boolean analogues of the Pascal triangle
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 59
EP  - 96
VL  - 28
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_3_a5/
LA  - ru
ID  - DM_2016_28_3_a5
ER  - 
%0 Journal Article
%A F. M. Malyshev
%T Distribution of the extreme values of the number of ones in Boolean analogues of the Pascal triangle
%J Diskretnaya Matematika
%D 2016
%P 59-96
%V 28
%N 3
%U http://geodesic.mathdoc.fr/item/DM_2016_28_3_a5/
%G ru
%F DM_2016_28_3_a5

[1] Malyshev F. M., “Bazisy mnozhestva tselykh chisel otnositelno mnogomestnykh operatsii sdviga”, Matematicheskie voprosy kriptografii, 2:1 (2011), 29–73 | MR

[2] Wolfram S., “Cellular automaton supercomputing”, High-Speed Computing, Univ. of Illinois Press, 1988, 40–48

[3] Malyshev F. M., Kutyreva E. V., “On the distribution of the number of ones in a Boolean Pascal's triangle”, Discrete Math. Appl., 16:3 (2006), 271–279 | DOI | DOI | MR | Zbl

[4] Malyshev F. M., “Bazisy rekurrentnykh posledovatelnostei”, Chebyshevskii sbornik, 16:2 (2015), 155–185

[5] Berlekamp E. R., Algebraic Coding Theory, McGraw Hill, 1968, 466 pp. | MR | MR | Zbl