数学の未解決問題 1以外の任意の自然数について、パスカルの三角形に現れる回数がN未満となるような定数Nは存在するか?
シングマスター予想 (シングマスターよそう、英 : 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 ) {\displaystyle N(a)=O(1)}
既知の上限 パスカルの三角形における出現数 N (a ) について、以下のことがすでに知られている。
(Singmaster 1971 ) N ( a ) = O ( log a ) {\displaystyle N(a)=O(\log a)} すなわち、ある係数 K が存在して、十分大きな a について N ( a ) < K log a {\textstyle N(a)<K\log a} が成り立つ。 (Abbott, Erdős & Hanson 1974 , Theorem 3) N ( a ) = O ( log a log log a ) {\displaystyle N(a)=O\left({\frac {\log a}{\log \log a}}\right)} (Kane 2007 ) N ( a ) = O ( ( log a ) ( log log log a ) ( log log a ) 3 ) {\displaystyle N(a)=O\left({\frac {(\log a)(\log \log \log a)}{(\log \log a)^{3}}}\right)} (Matomäki et al. 2022 , Theorem 1.3) 0 < ε < 1 {\textstyle 0<\varepsilon <1} に対して、十分大きい a を取る (このとき a は ε に依存して取る)。このとき、 ( n m ) = a {\textstyle {\tbinom {n}{m}}=a} を満たす (n , m ) の組は、次の不等式で制限される範囲内には高々4個しか存在しない。 exp ( log ( n ) 2 3 + ε ) ≤ m ≤ n − exp ( log ( n ) 2 3 + ε ) {\displaystyle \exp \left(\log(n)^{{\tfrac {2}{3}}+\varepsilon }\right)\leq m\leq n-\exp \left(\log(n)^{{\tfrac {2}{3}}+\varepsilon }\right)} (Abbott, Erdős & Hanson 1974 , p. 259) 「x が十分大きいとき、x と x + (log x )2 の間に素数が存在する」という(クラメールの予想 )(英語版) を仮定すると、任意の ε > 0 {\textstyle \varepsilon >0} について N ( a ) = O ( log ( a ) 2 3 + ε ) {\displaystyle N(a)=O\left(\log(a)^{{\tfrac {2}{3}}+\varepsilon }\right)}
シングマスターの無限族 シングマスターは、n と k に関するディオファントス方程式
( n + 1 k + 1 ) = ( n k + 2 ) {\displaystyle {n+1 \choose k+1}={n \choose k+2}} について、これが無限に多くの解を持つことを証明した。この方程式の解は、非負整数 i を用いて次のように表される。 n = F 2 i + 2 F 2 i + 3 − 1 k = F 2 i F 2 i + 3 − 1 {\displaystyle {\begin{aligned}n&=F_{2i+2}F_{2i+3}-1\\k&=F_{2i}F_{2i+3}-1\end{aligned}}} ここで F j は j 番目のフィボナッチ数 (F 0 = 0, F 1 = 1 ) である[1] 。 このとき、等しくなる両辺の値を a とおくと、
a = ( a 1 ) = ( n + 1 k + 1 ) = ( n k + 2 ) = ( n n − k − 2 ) = ( n + 1 n − k ) = ( a a − 1 ) {\displaystyle 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 2 ) {\displaystyle {p \choose 2}} (pは、 p > 3 {\displaystyle p>3} を満たす素数)の形で表せる数は4回現れる。 以下の例のようにちょうど6回現れる数も無限にある。 120 = ( 120 1 ) = ( 120 119 ) = ( 16 2 ) = ( 16 14 ) = ( 10 3 ) = ( 10 7 ) {\displaystyle 120={120 \choose 1}={120 \choose 119}={16 \choose 2}={16 \choose 14}={10 \choose 3}={10 \choose 7}} 210 = ( 210 1 ) = ( 210 209 ) = ( 21 2 ) = ( 21 19 ) = ( 10 4 ) = ( 10 6 ) {\displaystyle 210={210 \choose 1}={210 \choose 209}={21 \choose 2}={21 \choose 19}={10 \choose 4}={10 \choose 6}} 1540 = ( 1540 1 ) = ( 1540 1539 ) = ( 56 2 ) = ( 56 54 ) = ( 22 3 ) = ( 22 19 ) {\displaystyle 1540={1540 \choose 1}={1540 \choose 1539}={56 \choose 2}={56 \choose 54}={22 \choose 3}={22 \choose 19}} 7140 = ( 7140 1 ) = ( 7140 7139 ) = ( 120 2 ) = ( 120 118 ) = ( 36 3 ) = ( 36 33 ) {\displaystyle 7140={7140 \choose 1}={7140 \choose 7139}={120 \choose 2}={120 \choose 118}={36 \choose 3}={36 \choose 33}} 11628 = ( 11628 1 ) = ( 11628 11627 ) = ( 153 2 ) = ( 153 151 ) = ( 19 5 ) = ( 19 14 ) {\displaystyle 11628={11628 \choose 1}={11628 \choose 11627}={153 \choose 2}={153 \choose 151}={19 \choose 5}={19 \choose 14}} 24310 = ( 24310 1 ) = ( 24310 24309 ) = ( 221 2 ) = ( 221 219 ) = ( 17 8 ) = ( 17 9 ) {\displaystyle 24310={24310 \choose 1}={24310 \choose 24309}={221 \choose 2}={221 \choose 219}={17 \choose 8}={17 \choose 9}} 3003は8回現れる最小かつ現在唯一知られている数である。 3003 = ( 3003 1 ) = ( 78 2 ) = ( 15 5 ) = ( 14 6 ) = ( 14 8 ) = ( 15 10 ) = ( 78 76 ) = ( 3003 3002 ) {\displaystyle 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 {\textstyle a_{3}=61218182743304701891431482520} である (OEIS : (A090162 ))。 a 3 = ( a 3 1 ) = ( a 3 a 3 − 1 ) = ( 104 39 ) = ( 104 65 ) = ( 103 40 ) = ( 103 63 ) {\displaystyle 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回以上出現する数は存在しないと予想している[2] [3] [注釈 1] 。 ∞, 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 (x 1/2 )であることを示した。
未解決問題 9回以上現れる数、3003以外の8回現れる数が存在するかどうかは知られていない。上限は8と予想できるが、シングマスターは10または12と予想していた。
また、5回または7回現れる数が存在するかどうかも未解決である。関連する数列 オンライン整数列大辞典 の数列 (A003015 ) において等式N (a ) = 5 をみたす a があるかどうかわからないことが言及されている。
脚注
参考文献 Singmaster, D. (1971), “Research Problems: How often does an integer occur as a binomial coefficient?”, American Mathematical Monthly 78 (4): 385–386, doi :10.2307/2316907, JSTOR 2316907, MR 1536288, https://jstor.org/stable/2316907 . Singmaster, D. (1975), “Repeated binomial coefficients and Fibonacci numbers”, Fibonacci Quarterly 13 (4): 295–298, MR 0412095, http://www.fq.math.ca/Scanned/13-4/singmaster.pdf . Abbott, H. L.; Erdős, P. ; Hanson, D. (1974), “On the number of times an integer occurs as a binomial coefficient”, American Mathematical Monthly 81 (3): 256–261, doi :10.2307/2319526, JSTOR 2319526, MR 0335283, https://jstor.org/stable/2319526 . Kane, Daniel M. (2007), “Improved bounds on the number of ways of expressing t as a binomial coefficient” (PDF), INTEGERS: The Electronic Journal of Combinatorial Number Theory 7 (A53), MR 2373115, http://www.emis.de/journals/INTEGERS/papers/h53/h53.pdf . Matomäki, Kaisa; Radsiwiłł, Maksym; Shao, Xuancheng; Tao, Terence; Teräväinen, Joni (2022). “Singmaster's Conjecture in the Interior of Pascal's Triangle”. The Quarterly Journal of Mathematics 73 (3): 1137–1177. arXiv :2106.03335 . doi :10.1093/qmath/haac006.
関連項目 ウィキペディア、ウィキ、本、library、論文、読んだ、ダウンロード、自由、無料ダウンロード、mp3、video、mp4、3gp、 jpg、jpeg、gif、png、画像、音楽、歌、映画、本、ゲーム、ゲーム。