|
This article is cited in 1 scientific paper (total in 1 paper)
Distribution of the extreme values of the number of ones in Boolean analogues of the Pascal triangle
F. M. Malyshev Steklov Mathematical Institute of Russian Academy of Sciences
Abstract:
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<k_1<k_2<\,...$ 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$.
Keywords:
Pascal triangle, (0-1)-matrix, extreme combinatorial configuration.
Received: 17.03.2016
Citation:
F. M. Malyshev, “Distribution of the extreme values of the number of ones in Boolean analogues of the Pascal triangle”, Diskr. Mat., 28:3 (2016), 59–96; Discrete Math. Appl., 27:3 (2017), 149–176
Linking options:
https://www.mathnet.ru/eng/dm1384https://doi.org/10.4213/dm1384 https://www.mathnet.ru/eng/dm/v28/i3/p59
|
Statistics & downloads: |
Abstract page: | 359 | Full-text PDF : | 59 | References: | 42 | First page: | 25 |
|