|
Булевы аналоги треугольника Паскаля с максимально возможным числом единиц
Ф. М. Малышев Математический институт им. В.А. Стеклова Российской академии наук
Аннотация:
Работа посвящена определению максимально возможного числа единиц $\xi$ в треугольных массивах $T_s$ из $\frac{s(s+1)}{2}$ элементов поля $GF(2)$, задаваемых верхней строкой из $s$ элементов. Элементы каждой ниже стоящей строки получаются суммированием (как в треугольнике Паскаля) пар соседних элементов выше стоящей строки. Доказано, что $\xi\leqslant\left\lceil\frac{s(s+1)}{3}\right\rceil$ и эта оценка достигается только на треугольниках $T_s$ с верхней строкой в виде последовательности Фибоначчи по mod 2.
Ключевые слова:
треугольники Паскаля, (0,1)-матрицы, экстремальные комбинаторные конфигурации, последовательности Фибоначчи.
Статья поступила: 19.12.2019
Образец цитирования:
Ф. М. Малышев, “Булевы аналоги треугольника Паскаля с максимально возможным числом единиц”, Дискрет. матем., 32:1 (2020), 51–59; Discrete Math. Appl., 31:5 (2021), 319–325
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1606https://doi.org/10.4213/dm1606 https://www.mathnet.ru/rus/dm/v32/i1/p51
|
Статистика просмотров: |
Страница аннотации: | 330 | PDF полного текста: | 121 | Список литературы: | 26 | Первая страница: | 9 |
|