Гипотеза Сингмастера

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории чисел гипотеза Сингмастера, названная в честь Дэвида Сингмастера, утверждает, что имеется конечная верхняя граница количества одинаковых чисел (больших единицы) в треугольнике Паскаля. Ясно, что только единица содержится в треугольнике Паскаля бесконечное число раз, поскольку любое другое число x может встретиться только в первых x + 1 строках треугольника. Пол Эрдёш считал, что гипотеза Сингмастера верна, но предполагал, что доказать это будет трудно.

Пусть N(a) — количество появлений числа a > 1 в треугольнике Паскаля. В O-нотации гипотеза Сингмастера записывается как:

Известные результаты[править | править вики-текст]

Сингмастер (1971) показал, что

Позднее Аббот (Abbot), Эрдёш и Хансон (Hanson) улучшили оценку. Лучшая на сегодня оценка

получена Даниэлем Кейном (2007).

Аббот, Эрдёш и Хансон также заметили, что условие гипотезы Крамера о расстоянии между последовательными простыми числами влечёт оценку:

для любого .

Сингмастер (1975) показал, что диофантово уравнение

имеет бесконечно много решений для двух переменных n, k. Отсюда следует, что имеется бесконечно много случаев вхождения чисел 6 и более раз. Решения задаются уравнениями

где Fn — n-ое число Фибоначчи (согласно общепринятому F1 = F2 = 1).

Числовые примеры[править | править вики-текст]

Согласно вычислениям,

  • 2 появляется только один раз; все числа, большие 2, появляются более одного раза;
  • 3, 4, 5 появляются 2 раза;
  • 6 появляется 3 раза;
  • многие числа появляются 4 раза.
  • Каждое из следующих чисел появляется 6 раз:
  • Наименьшее число, появляющееся 8 раз — это 3003, которое является также первым членом бесконечного семейства чисел Сингмастера, встречающихся не менее 6 раз:

Следующее число в бесконечном семействе Сингмастера, и следующее наименьшее известное число, появляющееся шесть и более раз — это 61218182743304701891431482520.

Неизвестно, появляются ли какие-либо числа более чем восемь раз. Существует гипотеза, что максимальное число вхождений не превышает 8, но Сингмастер полагает, что оно должна быть 10 или 12.

Неизвестно, существуют ли числа, которые появляется в треугольнике Паскаля ровно пять или ровно семь раз.

См. также[править | править вики-текст]

Литература[править | править вики-текст]

  • D. Singmaster Repeated binomial coefficients and Fibonacci numbers // Fibonacci Quarterly. — 1975. — Т. 13, вып. 4. — С. 295–298..
  • Daniel M. Kane Improved bounds on the number of ways of expressing t as a binomial coefficient // Integers: Electronic Journal of Combinatorial Number Theory. — 2007. — Т. 7. — С. #A53..

Ссылки[править | править вики-текст]