tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

パスカルの三角形にたくさん出てくる数: 3003

この記事は 日曜数学 Advent Calendar 2018 の 1日目の記事です。


今日から12月、今年も アドベントカレンダー の季節がやってきましたね!

毎年12月になると、さまざまなテーマで持ち回りでブログ記事を書き合うお祭りがはじまります。それがアドベントカレンダーです。

4年連続でアドベントカレンダーを企画しているtsujimotterですが、2018年も「日曜数学」というテーマでアドベントカレンダーを立てることにしました。

adventar.org

おかげさまで、既にたくさんの方に書いていただけることが決まっています。ご賛同いただけた皆様、本当にありがとうございます。毎日記事が読めるのを楽しみにしています。

また、今のところ3日分ほど空きがありますので、よろしければ参加していただけると嬉しいです。


さて、1日目のテーマは パスカルの三角形 です。パスカルの三角形にまつわる面白い性質を紹介しましょう。

パスカルの三角形に「整数が何回出てきたか」を数えよう

このブログを見ている皆さんは、パスカルの三角形はご存知かと思います。こんな感じのものですね。

f:id:tsujimotter:20181130193801p:plain:w300

パスカルの三角形の各行には、二項係数

 \displaystyle \binom{n}{k} = \frac{n!}{k! (n-k)!}

が並んでいます。 \binom{n}{k} という記号は、高校では  {}_n \text{C}_k と書いていたものです。

パスカルの三角形の  n 行目には、左から

 \displaystyle \binom{n}{0}, \binom{n}{1}, \binom{n}{2}, \ldots, \binom{n}{n}

の順に二項係数が並んでいます。(一番上の行を  n = 0 行目と考えることに注意。)

たとえば、 n = 4 行目には

 \displaystyle \binom{4}{0}, \binom{4}{1}, \binom{4}{2}, \binom{4}{3}, \binom{4}{4}

すなわち

 \displaystyle 1, 4, 6, 4, 1

が並んでいます。


今日は、パスカルの三角形として現れる整数の個数を数えてみたいと思います。正の整数  a がパスカルの三角形に現れるとは

 \displaystyle \binom{n}{k} = a

なる非負整数  n, k が存在するということです。ここで、 a がパスカルの三角形に現れる回数を  N(a) と定義します。


たとえば、 a = 6 としましょう。パスカルの三角形から  6 を探すと

f:id:tsujimotter:20181130193907p:plain:w300

となり、 3 つの  6 が見つかります(6のところにアスタリスクマークを付けています)。したがって、 N(6) = 3 です。念のため言っておくと、 6 はこれ以降には現れません。


 a = 10 としてみましょう。パスカルの三角形をもう少し広くとると、 10 4 回現れることが分かります。

f:id:tsujimotter:20181130194620p:plain:w430

したがって、 N(10) = 4 となります。繰り返しになりますが、 10 はこれ以降には現れません。

なお、 a = 1 については、パスカルの三角形の両端に無限回表れるので、 N(1) = \infty と表すことにします。 a > 1 であれば、 a 行目までにすべての  a が表れることがわかるので、 N(a) は有限の値をとります。


これまでの話をまとめると、次のようになります。

 a を正の整数とする.

  • パスカルの三角形に  a が表れる回数を  N(a) と定義する.
  •  N(1) = \infty
  •  a > 1 のとき  N(a) < \infty

 N(a) を観察してみよう

せっかくなので、 a \leq 120 までの  N(a) を列挙してみましょう。しばらく、式が続くので、ざーっとで構いませんので眺めてみてください。(飛ばしてしまってもかまいません。)

 N(1) = \infty
 N(2) = 1
 N(3) = 2
 N(4) = 2
 N(5) = 2
 N(6) = 3
 N(7) = 2
 N(8) = 2
 N(9) = 2
 N(10) = 4
 N(11) = 2
 N(12) = 2
 N(13) = 2
 N(14) = 2
 N(15) = 4
 N(16) = 2
 N(17) = 2
 N(18) = 2
 N(19) = 2
 N(20) = 3
 N(21) = 4
 N(22) = 2
 N(23) = 2
 N(24) = 2
 N(25) = 2
 N(26) = 2
 N(27) = 2
 N(28) = 4
 N(29) = 2
 N(30) = 2
 N(31) = 2
 N(32) = 2
 N(33) = 2
 N(34) = 2
 N(35) = 4
 N(36) = 4
 N(37) = 2
 N(38) = 2
 N(39) = 2
 N(40) = 2
 N(41) = 2
 N(42) = 2
 N(43) = 2
 N(44) = 2
 N(45) = 4
 N(46) = 2
 N(47) = 2
 N(48) = 2
 N(49) = 2
 N(50) = 2
 N(51) = 2
 N(52) = 2
 N(53) = 2
 N(54) = 2
 N(55) = 4
 N(56) = 4
 N(57) = 2
 N(58) = 2
 N(59) = 2
 N(60) = 2
 N(61) = 2
 N(62) = 2
 N(63) = 2
 N(64) = 2
 N(65) = 2
 N(66) = 4
 N(67) = 2
 N(68) = 2
 N(69) = 2
 N(70) = 3
 N(71) = 2
 N(72) = 2
 N(73) = 2
 N(74) = 2
 N(75) = 2
 N(76) = 2
 N(77) = 2
 N(78) = 4
 N(79) = 2
 N(80) = 2
 N(81) = 2
 N(82) = 2
 N(83) = 2
 N(84) = 4
 N(85) = 2
 N(86) = 2
 N(87) = 2
 N(88) = 2
 N(89) = 2
 N(90) = 2
 N(91) = 4
 N(92) = 2
 N(93) = 2
 N(94) = 2
 N(95) = 2
 N(96) = 2
 N(97) = 2
 N(98) = 2
 N(99) = 2
 N(100) = 2
 N(101) = 2
 N(102) = 2
 N(103) = 2
 N(104) = 2
 N(105) = 4
 N(106) = 2
 N(107) = 2
 N(108) = 2
 N(109) = 2
 N(110) = 2
 N(111) = 2
 N(112) = 2
 N(113) = 2
 N(114) = 2
 N(115) = 2
 N(116) = 2
 N(117) = 2
 N(118) = 2
 N(119) = 2
 N(120) = 6


値を観察してみると、 1 < a < 120 までの間は、 N(a) \leq 4 となることがわかります。 a = 120 ではじめて  N(a) = 6 の値をとるわけですね。つまり、 a = 120 は「 N(a) 6 以上になる最小の  a」ということになります。

Singmaster予想

「パスカルの三角形に表れる数の個数なんて誰が考えるんだ」と思うかもしれませんが、世の中いろいろな人はいるもので、Singmaster(シングマスター)という数学者によってたくさん成果が出ています。それらのうちのいくつかを紹介したいと思います。

まずは、Singmaster予想という、1971年に提唱された  N(a) についての予想を紹介しましょう。

Singmaster予想(Singmaster's conjecture, 1971)
 a > 1 を正の整数としたとき,次が成り立つ:
 N(a) = \mathcal{O}(1) \tag{1}

 (1) の右辺は「ビッグ・オー記法」と呼ばれるもので、正の定数  C が存在して

 N(a) < C

とかけることを表しています。

これが何を意味しているかというと、 N(a) には上限値があるということです。一見すると、 N(a) a を大きくとれば、いくらでも大きくなりそうな気がします。しかしながら、実は  N(a) には(大きさはわからないが)上限値があって、それを超えるような  a が存在しないと主張しているのです。これはかなり非自明なことだと思います。

上で観察したように、 a \leq 120 においては、 N(a) の上限値は  6 でした。 N(a) はいったいいくつの値で上から抑えることができるでしょうか。

現在までに知られている  N(a) の上限値は  8 です。そして、 N(a) \geq 8 となる最小の  a

 3003

です。言い換えると 「パスカルの三角形にもっともたくさん出てくる数の現時点でのワールド・レコードが  3003 というわけですね。これが、今日の記事のタイトルだったのでした。

実際、

 \displaystyle \binom{3003}{1} = \binom{78}{2} = \binom{15}{5} = \binom{14}{6} = \binom{14}{8} = \binom{15}{10} = \binom{78}{76} = \binom{3003}{3002}

はすべて  3003 の値をとります。 3003 すごい!


さらにいうと、 N(a) \geq 8 なる  a としては、今のところ  a = 3003 しか見つかっていません!つまり  8 回以上パスカルの三角形に現れる数は、 3003 以外に見つかっていないのです!

これは、 3003 という数の性質としては申し分ないものですね。私はこの事実を知ってからしばらくの間、興奮が収まりませんでした。


ちなみに、Singmaster自身は  N(a) の上限値としては、 10 12 だろうと予想しているそうです。まだまだ先があるのですね・・・。

Singmaster's infinite family(シングマスターの無限族)

ところで、どうやって、 N(a) が大きなものを見つけたらよいでしょうか。

この問題には、Singmasterが発見した次の事実が有用です。

定理(Singmaster, 1975)
整数  n, k を変数とする2変数方程式
 \displaystyle \binom{n+1}{k+1} = \binom{n}{k+2} \tag{2}

は無限に多くの解を持つ.その解は

 \begin{cases} n = F_{2i+2} F_{2i+3} - 1 \\
 k = F_{2i} F_{2i+3} - 1 \end{cases} \tag{3}

で表せる. F_j j 番目のフィボナッチ数である.ここで  F_0 = 0, \; F_1 = 1 とする.


 (2) は二項係数の間の等式になっています。つまり、パスカルの三角形の「ここ」と「あそこ」が同じ値になっているということです。このような条件を満たす  n, k の組は無限に存在するというのがSingmasterの主張です。

f:id:tsujimotter:20181201130733p:plain:w300

しかも、そのような  n, k は具体的に式  (3) の形で表すことができるというのです。さらにさらに、その式がフィボナッチ数で表されているという。

これ、なかなかすごくないですか!?


具体的に  i = 1 のとき、 F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, \ldots より

 \begin{align} n &= F_{2\cdot 1+2} F_{2\cdot 1+3} - 1 = F_4 F_5 - 1 = 14 \\
 k &= F_{2\cdot 1} F_{2\cdot 1+3} - 1 = F_2 F_5 - 1 = 4 \end{align}

なので

 \displaystyle \binom{15}{5} = \binom{14}{6}

が成り立つはずです。実際

 \displaystyle \binom{15}{5} = \binom{14}{6} = 3003

が成り立ちます。

実は、これが  N(3003) \geq 6 である秘密だったのです。どういうことかというと

 \displaystyle 3003 = \binom{15}{5} = \binom{14}{6}

の時点で、 3003 はパスカルの三角形の2箇所に登場することがわかります。さらに、二項係数の性質

 \displaystyle \binom{n}{k} = \binom{n}{n-k}

により

 \displaystyle 3003 = \binom{15}{5} = \binom{15}{10} = \binom{14}{6} = \binom{14}{8}

4箇所に登場することが確定するわけです。

また、一般に

 \displaystyle n = \binom{n}{1} = \binom{n}{n-1}

が成り立つので、あっという間に

 \displaystyle 3003 = \binom{15}{5} = \binom{15}{10} = \binom{14}{6} = \binom{14}{8} = \binom{3003}{1} = \binom{3003}{3002}

6箇所に出ることがわかってしまいました!

これで  N(3003) \geq 6 です!


こんな風に、Singmasterの定理の条件  (2) を満たす  n, k の組によって得られる  \binom{n+1}{k+1} = a は、 N(a) \geq 6 になることが示されます。さらに、Singmasterの定理によって

このような  a は無限に存在します!

これらをSingmasterの無限族と言います。素晴らしいですね。


最後に、 3003 の次に小さいSingmasterの無限族の仲間を紹介して終わりにしましょう。

 i = 2 とすると、 F_4 = 3, F_5 = 5, F_6 = 8, F_7 = 13, \ldots より

 \begin{align} n &= F_{2\cdot 2+2} F_{2\cdot 2+3} - 1 = F_6 F_7 - 1 = 103 \\
 k &= F_{2\cdot 2} F_{2\cdot 2+3} - 1 = F_4 F_7 - 1 = 38 \end{align}

が得られます。このときの  a

 \displaystyle a = \binom{104}{39} = 61218182743304701891431482520

となります。

でかっ!!!

やばっ!!!


もちろんこの  61218182743304701891431482520

 N(61218182743304701891431482520) \geq 6

が成り立ちます!Singmasterすごい!!

どうやって見つけたか

最後の最後に、今回のSingmasterの話の元ネタをご紹介して終わりにしましょう。

まず、最初に見つけたのはWikipediaの "3000" の記事です。

3000 - Wikipedia

wikipediaで "1000", "2000", "3000" のように入力して検索すると出てくるページでは、1000番台、2000番台、3000番台にある面白い整数の性質が紹介されています。いったい誰がまとめているんだというような全然知らない性質が載っていて非常に面白いです。これらのページはなかなかおすすめです。

この "3000" のページに

3003 - 三角数、六角数、パスカルの三角形に8回現れる数として知られている唯一の数(8回を超えて現れる数は知られていない、en:Singmaster's conjectureを参照)

とあるのを見つけました。特に

パスカルの三角形に8回現れる数として知られている唯一の数(8回を超えて現れる数は知られていない、en:Singmaster's conjectureを参照)

の部分は今まで聞いたこともなかったので、驚いてテンションが上がりました。

そして、Wikipediaの "Singmaster's conjecture" の記事

Singmaster's conjecture - Wikipedia

を見つけたというのが経緯です。今日の話はほとんど上の記事に載っている内容です。

一部、Singmasterの1975年の論文

https://www.fq.math.ca/Scanned/13-4/singmaster.pdf

を参考にしました。

こんな感じで見つけたものですから、日曜数学アドベントカレンダーのID番号にしてやろうと思って、虎視眈々とねらっていたのですが・・・残念ながら失敗しました。笑

結果的に、日曜数学アドベントカレンダーのIDは3009になってしまったのですが、もし3009の面白い性質を見つけた方がおられましたら、tsujimotterまでご連絡ください。


最後に紹介した「Wikipediaを使った数の性質探し」はなかなか楽しいので、ぜひ「日曜数学」として実践してみてください。

明日のアドベントカレンダーは・・・

dogradishさんが、ユークリッド幾何の第1公準について書いてくださるそうです。楽しみにしています。

それでは今日はこの辺で。

追記:3003 はなぜ8回も出てくるのか?

ところで、Singmasterの定理の条件から  N(3003) \geq 6 であることが分かったわけですが、ではなぜ  N(3003) = 8 なのでしょうか。これは  3003 が「三角数」であることに関係しています。

たしかに、Wikipediaの "3000" の記事には

3003 - 三角数、六角数、パスカルの三角形に8回現れる数として知られている唯一の数(8回を超えて現れる数は知られていない、en:Singmaster's conjectureを参照)

と書いてありました。「三角数」であることが実は重要だったのです。

三角数とは

f:id:tsujimotter:20181201151256p:plain:w260

のように、三角形に並べられる数のことです。式で表すと

 \displaystyle n = 1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}

と表すことができる  n のことです。これは二項係数で表すことができて

 \displaystyle n = \frac{(k+1)k}{2} = \binom{k+1}{2}

ということです。

さて、3003は

 \displaystyle 3003 = 1 + 2 + 3 + \cdots + 77 = \frac{77(77+1)}{2} = \binom{77+1}{2}

と表せますので、三角数であり、 \binom{78}{2} なる二項係数で表せます。したがって

 \displaystyle 3003 = \binom{78}{2} = \binom{78}{76}

2箇所に現れることがわかります。これらは、上で計算した6箇所とは異なりますので、計8箇所に登場することが確定します。

したがって、 N(3003) \geq 8 です。


3003の特殊性は「Singmasterの定理の条件を満たす数(Singmasterの無限族の数)」であり「三角数」であるような、現在知られている唯一の例であるところにあったというわけです。面白いですね!!