シングマスター予想
シングマスター予想 (シングマスターよそう、Singmaster's conjecture) は、「パスカルの三角形において1以外の数字の出現回数には上限が存在する」という組み合わせ数学の予想である。名前の由来は1971年にこの予想を提唱したイギリスの数学者デヴィッド・シングマスターに由来する。
1より大きい任意の整数 n について、この数はパスカルの三角形において上から n + 1 行までにしか出現しないため、1より大きい数の出現が有限であることは明らかである。シングマスター予想は、この出現回数がある有限の数を越えないことを主張している。
なお、1は明らかにパスカルの三角形において無限回出現し、上記の事実から1はパスカルの三角形で無限回出現する唯一の数である。
整数 a > 1 に対して、N(a) をパスカルの三角形における a の出現回数とする。 シングマスター予想の主張は、ある (a に依存しない) 有限の数 M が存在して N(a) < M が成り立つことである。
ランダウのOを用いると、予想の主張は以下の通りになる。
N(a) = O(1)
パスカルの三角形における出現数 N(a) について、以下のことがすでに知られている。
N(a) = O(\log a)すなわち、ある係数 K が存在して、十分大きな a について N(a)<K\log a が成り立つ。
N(a) = O\left(\frac{\log a}{\log \log a}\right)
N(a) = O\left(\frac{(\log a)(\log \log \log a)}{(\log \log a)^3}\right)
0 < \varepsilon < 1  に対して、十分大きい a を取る (このとき a は ε に依存して取る)。このとき、\tbinom{n}{m}=a を満たす (n, m) の組は、次の不等式で制限される範囲内には高々4個しか存在しない。\exp \left(\log(n)^{\tfrac{2}{3}+\varepsilon} \right) \le m \le n - \exp \left(\log(n)^{\tfrac{2}{3}+\varepsilon} \right)
「x が十分大きいとき、x と x + (log x)2 の間に素数が存在する」というクラメールの予想を仮定すると、任意の \varepsilon > 0  について N(a) = O\left( \log(a)^{\tfrac{2}{3}+\varepsilon}\right)
シングマスターは、n と k に関するディオファントス方程式{n+1 \choose k+1} = {n \choose k+2}について、これが無限に多くの解を持つことを証明した。この方程式の解は、非負整数 i を用いて次のように表される。\begin{align}
n &= F_{2i+2} F_{2i+3} - 1\\
k &= F_{2i}F_{2i+3}-1
\end{align}ここで Fj は j 番目のフィボナッチ数 (F0 = 0, F1 = 1) である。
このとき、等しくなる両辺の値を a とおくと、a = \binom{a}{1} = \binom{n+1}{k+1} = \binom{n}{k+2} = \binom{n}{n-k-2} = \binom{n+1}{n-k} = \binom{a}{a-1}となり、パスカルの三角形に (少なくとも) 6回登場する数の族を得る。これをシングマスターの無限族と呼ぶ。
2 は1回だけ現れる。それより大きい整数は2回以上現れる。
3, 4, 5 はそれぞれ2回現れる。ちょうど2個現れる整数は無限にある。
全ての奇素数は2回現れる。
6 は3回現れる。3回現れる整数も無限個ある。
{p \choose 2} (pは、 p>3 を満たす素数)の形で表せる数は4回現れる。
以下の例のようにちょうど6回現れる数も無限にある。120 = {120 \choose 1} ={120 \choose 119} = {16 \choose 2} ={16 \choose 14} = {10 \choose 3} ={10 \choose 7}210 = {210 \choose 1} ={210 \choose 209} = {21 \choose 2} ={21 \choose 19} = {10 \choose 4}={10 \choose 6}1540 = {1540 \choose 1} ={1540 \choose 1539} = {56 \choose 2} ={56 \choose 54} = {22 \choose 3} = {22 \choose 19}7140 = {7140 \choose 1} ={7140 \choose 7139} = {120 \choose 2} ={120 \choose 118} = {36 \choose 3} = {36 \choose 33}11628 = {11628 \choose 1} = {11628 \choose 11627} = {153 \choose 2} = {153 \choose 151} = {19 \choose 5} = {19 \choose 14}24310 = {24310 \choose 1} = {24310 \choose 24309} = {221 \choose 2} = {221 \choose 219} = {17 \choose 8} = {17 \choose 9}
3003は8回現れる最小かつ現在唯一知られている数である。3003 = {3003 \choose 1} = {78 \choose 2} = {15 \choose 5} = {14 \choose 6} = {14 \choose 8} = {15 \choose 10} = {78 \choose 76} = {3003 \choose 3002} 3003はシングマスターの無限族によって求められる数でもある。シングマスターの無限族における次の数は a_3 = 61218182743304701891431482520 である (OEIS: A090162)。a_3 = {a_3 \choose 1} = {a_3 \choose a_3-1} = {104 \choose 39} = {104 \choose 65} = {103 \choose 40} = {103 \choose 63}
Benjamin M. M. de Wegerは、上記の120、210、1540、7140、11628、24310およびシングマスターの無限族以外にパスカルの三角形で5回以上出現する数は存在しないと予想している正確には、すでに知られた形以外で異なる二項係数が一致することはないと主張している。従って予想が正しいならば、パスカルの三角形に出現する回数の最大値は8である。。
n がパスカルの三角形に現れる回数は、
∞, 1, 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 2, 4, 2, 2, 2, 2, 3, 4, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 2, 2, 2, 2, 2, 4, 2, 2, ... A003016
Abbott, Erdős, and Hanson (1974)は、 x 以下のパスカルの三角形に3回以上現れる整数の数は、O(x1/2)であることを示した。
9回以上現れる数、3003以外の8回現れる数が存在するかどうかは知られていない。上限は8と予想できるが、シングマスターは10または12と予想していた。
また、5回または7回現れる数が存在するかどうかも未解決である。関連する数列 A003015 において等式N(a) = 5 をみたす aがあるかどうかわからないことが言及されている。