WikiSort.ru - Не сортированное

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

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

${\displaystyle N(a)=O(1).}$

Известные результаты

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

${\displaystyle N(a)=O(\log a).}$

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

${\displaystyle N(a)=O\left({\frac {(\log a)(\log \log \log a)}{(\log \log a)^{3}}}\right)}$

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

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

${\displaystyle N(a)=O\left(\log(a)^{2/3+\varepsilon }\right)}$

для любого ${\displaystyle \varepsilon >0}$ .

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

${\displaystyle {n+1 \choose k+1}={n \choose k+2},}$

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

${\displaystyle n=F_{2i+2}F_{2i+3}-1,}$

${\displaystyle k=F_{2i}F_{2i+3}-1,}$

где F_n — n-ое число Фибоначчи (согласно общепринятому F₁ = F₂ = 1).

Числовые примеры

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

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

  ${\displaystyle {120 \choose 1}={16 \choose 2}={10 \choose 3}}$

  ${\displaystyle {210 \choose 1}={21 \choose 2}={10 \choose 4}}$

  ${\displaystyle {1540 \choose 1}={56 \choose 2}={22 \choose 3}}$

  ${\displaystyle {7140 \choose 1}={120 \choose 2}={36 \choose 3}}$

  ${\displaystyle {11628 \choose 1}={153 \choose 2}={19 \choose 5}}$

  ${\displaystyle {24310 \choose 1}={221 \choose 2}={17 \choose 8}}$

• Наименьшее число, появляющееся 8 раз — это 3003, которое также является членом бесконечного семейства чисел Сингмастера, встречающихся не менее 6 раз:

  ${\displaystyle {3003 \choose 1}={78 \choose 2}={15 \choose 5}={14 \choose 6}}$

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

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

Неизвестно, существуют ли числа, которые появляются в треугольнике Паскаля ровно пять или ровно семь раз, хотя очевидно, что они - подмножество чисел с нечётным вхождением. Это числа вида ${\displaystyle {2n \choose n}}$ .

См. также

• Биномиальный коэффициент

Литература

• D. Singmaster. Research Problems: How often does an integer occur as a binomial coefficient? // American Mathematical Monthly. — 1971. — Т. 78, вып. 4. — С. 385–386. — DOI:10.2307/2316907..

• D. Singmaster. Repeated binomial coefficients and Fibonacci numbers // Fibonacci Quarterly. — 1975. — Т. 13, вып. 4. — С. 295–298..

• H. L. Abbott, P. Erdős, D. Hanson. On the number of times an integer occurs as a binomial coefficient // American Mathematical Monthly. — 2319526. — Т. 81, вып. 3. — С. 256–261. — DOI:10.2307/2319526..

• 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..

Ссылки

• последовательность A003016 в OEIS