RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2016, том 28, выпуск 3, страницы 59–96 (Mi dm1384)

Эта публикация цитируется в 1 статье

Распределение крайних значений числа единиц в булевых аналогах треугольника Паскаля

Ф. М. Малышев

Математический институт им. В. А. Стеклова Российской академии наук

Аннотация: Работа посвящена оценке числа единиц $\xi$ в треугольных массивах элементов поля $GF(2)$, задаваемых нижней строкой из $s$ элементов. Элементы каждой выше стоящей строки получаются суммированием (как в треугольнике Паскаля) пар элементов ниже стоящей строки. Доказано существование такой монотонной неограниченной последовательности $0=k_0<k_1<k_2<\dots$ рациональных чисел, что для любого $k>0$ при достаточно больших $s$ допустимые значения $\xi$, ме́ньшие $ks$ или бо́льшие $s(s+1)/3-sk/3$, сосредоточены в окрестностях точек $k_is$ и $s(s+1)/3-sk_i/3$, $i\geqslant0$. Оценки размеров окрестностей свои для каждого $i\geqslant0$ и не зависят от $s$. Распределения чисел треугольников, имеющих значения $\xi$ в этих окрестностях, зависят только от вычетов $s$ по некоторым модулям, своим для каждого $i\geqslant0$.

Ключевые слова: треугольники Паскаля, ($0$-$1$)-матрицы, экстремальные комбинаторные конфигурации.

УДК: 519.14

Статья поступила: 17.03.2016

DOI: 10.4213/dm1384


 Англоязычная версия: Discrete Mathematics and Applications, 2017, 27:3, 149–176

Реферативные базы данных:


© МИАН, 2024