Проблема барицентрической суммы
Комбинаторная теория чисел занимается проблемами теории чисел , которые включают комбинаторные в свои формулировки или решения идеи. Пол Эрдеш — главный основатель этого раздела теории чисел. Типичные темы включают систему покрытия , задачи с нулевой суммой , различные ограниченные множества и арифметические прогрессии в наборе целых чисел. В этой области сильны алгебраические или аналитические методы.
В комбинаторной теории чисел проблемы барицентрической суммы — это вопросы, на которые можно ответить с помощью комбинаторных методов. Контекстом задач барицентрической суммы являются барицентрические последовательности.
Пример
[ редактировать ]Позволять — циклическая группа целых чисел по модулю n . Пусть S — последовательность элементов , где допускается повторение элементов. Позволять длиной S. быть Последовательность с является барицентрическим или имеетбарицентрическая сумма, если она содержит один элемент такой, что .
Неформально, если содержит один элемент , что является «средним» его членов. Барицентрическая последовательность длины называется t-барицентрической последовательностью. Более того, когда S является множеством, вместо барицентрической последовательности используется термин барицентрическое множество. Например, набор {0,1,2,3,4} является 5-барицентрическим с барицентром 2, однако множество {0,2,3,4,5} не является 5-барицентрическим. Задача о барицентрической сумме состоит в нахождении наименьшего целого числа t такого, что любая последовательность длины t содержит k -барицентрическую последовательность для некоторого заданного k . Исследование существования таких t, связанных с k, и изучение барицентрических констант являются частью задач барицентрической суммы. Его представил Ордас, [1] [2] вдохновленный теоремой Хамидуна: [3] каждая последовательность длины в содержит k-барицентрическую последовательность. Заметим, что k -барицентрическая последовательность в , где ka кратно n, представляет собой последовательность с нулевой суммой. Проблема нулевой суммы для последовательностей началась в 1961 году с теоремы Эрдеша, Гинзбурга и Зива: каждая последовательность длины в абелевой группе порядка n содержит n -подпоследовательность с нулевой суммой. [4] [5] [6] [7] [8] [9] [10]
Проблемы барицентрической суммы в общем определены для конечных абелевых групп. Однако большинство основных результатов, полученных к настоящему времени, находятся в .
Барицентрические константы, введенные Ордасом: [11] [12] [13] [14] [15] k -барицентрическая константа Олсона, k -барицентрическая константа Давенпорта, барицентрическая константа Давенпорта, обобщенная барицентрическая константа Давенпорта, ограниченная барицентрическая константа Давенпорта. Эти константы связаны с константой Давенпорта. [16] т.е. наименьшее целое число t такое, что любая t -последовательность содержит подпоследовательность с нулевой суммой. Кроме того, по отношению к классическим числам Рамсея вводятся барицентрические числа Рамсея. Представлен обзор результатов, рассчитанных вручную или автоматически. [17] Реализованные алгоритмы написаны на языке C. [13] [17] [18]
Ссылки
[ редактировать ]- ^ К. Делорм, С. Гонсалес, О. Ордас и М. Т. Варела. Барицентрические последовательности и звезды барицентрических чисел Рамсея, Дискретная математика. 277(2004)45–56.
- ^ К. Делорм, И. Маркес, О. Ордас и А. Ортуньо. Условие существованиядля барицентрических последовательностей, Discrete Math. 281(2004)163–172.
- ^ ЙО Хамидун. О суммах взвешенных последовательностей, Combinatorics, Probability and Computing 4 (1995) 363–367.
- ^ Ю. Каро. Задачи с нулевой суммой: обзор. Дискретная математика. 152 (1996) 93–113.
- ^ П. Эрдеш, А. Гинзбург и А. Зив. Теорема аддитивной теории чисел, Bull. Рез. Совет Израиля 10F (1961) 41–43.
- ^ К. Флорес и О. Ордас. О последовательностях с нулевой суммой в абелевой группе. Том в честь доктора Родольфо А. Рикабарры (испанский), 99-106, Vol. Хоменае, 1, ун. Нак. дель Сур, Баия-Бланка, 1995 год.
- ^ В. Гао и А. Герольдингер, Проблемы с нулевой суммой в конечных абелевых группах: обзор. Математические экспозиции 24 (2006), н. 4, 337–369.
- ^ Д. Д. Гринкевич, О. Ордас, М. Т. Варела и Ф. Вильярроэль, Об обратных теоремах Эрдеша-Гинзбурга-Зива. Акта Арифметика. 129 (2007) 307–318. 2
- ^ Ю. О. Хамидун, О. Ордас и А. Ортуньо. Об одной комбинаторной теореме Эрдоша-Гинзбурга-Зив. Комбинаторика, вероятность и вычисления 7 (1998) 403–412.
- ^ О. Ордас и Д. Кироз, Представление элементов группы в виде подпоследовательностейсуммы, чтобы появиться в дискретной математике.
- ^ С. Гонсалес, Л. Гонсалес и О. Ордас. Барицентрические числа Рамсея для небольших графиков. Будут опубликованы в Бюллетене Малайзийского математического института.Общество наук.
- ^ Л. Гонсалес, И. Маркес, О. Ордас и Д. Кирос, Ограниченные и обобщенные барицентрические константы Давенпорта, Divulgaciones Matemáticas 15 № 1 (2007) 11–21.
- ^ Jump up to: а б К. Гиа, Ф. Лосавио, О. Ордас, М. Т. Варела и Ф. Вильярроэль, Барицентрические константы Давенпорта. Появиться в журнале Mathematical Disclosures.
- ^ О. Ордас, М.Т. Варела и Ф. Вильярроэль. k-барицентрическая константа Олсона.Появиться в математических отчетах.
- ^ О. Ордас и Д. Кирос, Проблема барицентрической суммы: обзор. Математические открытия 15 № 2 (2007) 193–206.
- ^ К. Делорм, О. Ордас и Д. Кирос. Некоторые замечания о константе Давенпорта, Discrete Math. 237(2001)119–128.
- ^ Jump up to: а б Л. Гонсалес, Ф. Лосавио, О. Ордас, М. Т. Варела и Ф. Вильярроэль. Барицентрические целочисленные последовательности. Представлено на математических выставках.
- ^ Ф. Вильярроэль, Докторская диссертация по математике. Барицентрическая константа Олсона k и обратная теорема Эрдеша-Гинзбурга-Зива. Факультет наук. Центральный университет Венесуэлы (2008 г.).