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

Дискрет. матем., 2020, том 32, выпуск 1, страницы 51–59 (Mi dm1606)

Булевы аналоги треугольника Паскаля с максимально возможным числом единиц

Ф. М. Малышев

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

Аннотация: Работа посвящена определению максимально возможного числа единиц $\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)-матрицы, экстремальные комбинаторные конфигурации, последовательности Фибоначчи.

УДК: 519.14

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

DOI: 10.4213/dm1606


 Англоязычная версия: Discrete Mathematics and Applications, 2021, 31:5, 319–325

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


© МИАН, 2024