この記事は 日曜数学 Advent Calendar 2018 の 1日目の記事です。
今日から12月、今年も アドベントカレンダー の季節がやってきましたね!
毎年12月になると、さまざまなテーマで持ち回りでブログ記事を書き合うお祭りがはじまります。それがアドベントカレンダーです。
4年連続でアドベントカレンダーを企画しているtsujimotterですが、2018年も「日曜数学」というテーマでアドベントカレンダーを立てることにしました。
おかげさまで、既にたくさんの方に書いていただけることが決まっています。ご賛同いただけた皆様、本当にありがとうございます。毎日記事が読めるのを楽しみにしています。
また、今のところ3日分ほど空きがありますので、よろしければ参加していただけると嬉しいです。
さて、1日目のテーマは パスカルの三角形 です。パスカルの三角形にまつわる面白い性質を紹介しましょう。
パスカルの三角形に「整数が何回出てきたか」を数えよう
このブログを見ている皆さんは、パスカルの三角形はご存知かと思います。こんな感じのものですね。
パスカルの三角形の各行には、二項係数
が並んでいます。 という記号は、高校では と書いていたものです。
パスカルの三角形の 行目には、左から
の順に二項係数が並んでいます。(一番上の行を 行目と考えることに注意。)
たとえば、 行目には
すなわち
が並んでいます。
今日は、パスカルの三角形として現れる整数の個数を数えてみたいと思います。正の整数 がパスカルの三角形に現れるとは
なる非負整数 が存在するということです。ここで、 がパスカルの三角形に現れる回数を と定義します。
たとえば、 としましょう。パスカルの三角形から を探すと
となり、 つの が見つかります(6のところにアスタリスクマークを付けています)。したがって、 です。念のため言っておくと、 はこれ以降には現れません。
としてみましょう。パスカルの三角形をもう少し広くとると、 が 回現れることが分かります。
したがって、 となります。繰り返しになりますが、 はこれ以降には現れません。
なお、 については、パスカルの三角形の両端に無限回表れるので、 と表すことにします。 であれば、 行目までにすべての が表れることがわかるので、 は有限の値をとります。
これまでの話をまとめると、次のようになります。
- パスカルの三角形に が表れる回数を と定義する.
- のとき
を観察してみよう
せっかくなので、 までの を列挙してみましょう。しばらく、式が続くので、ざーっとで構いませんので眺めてみてください。(飛ばしてしまってもかまいません。)
値を観察してみると、 までの間は、 となることがわかります。 ではじめて の値をとるわけですね。つまり、 は「 が 以上になる最小の 」ということになります。
Singmaster予想
「パスカルの三角形に表れる数の個数なんて誰が考えるんだ」と思うかもしれませんが、世の中いろいろな人はいるもので、Singmaster(シングマスター)という数学者によってたくさん成果が出ています。それらのうちのいくつかを紹介したいと思います。
まずは、Singmaster予想という、1971年に提唱された についての予想を紹介しましょう。
式 の右辺は「ビッグ・オー記法」と呼ばれるもので、正の定数 が存在して
とかけることを表しています。
これが何を意味しているかというと、 には上限値があるということです。一見すると、 は を大きくとれば、いくらでも大きくなりそうな気がします。しかしながら、実は には(大きさはわからないが)上限値があって、それを超えるような が存在しないと主張しているのです。これはかなり非自明なことだと思います。
上で観察したように、 においては、 の上限値は でした。 はいったいいくつの値で上から抑えることができるでしょうか。
現在までに知られている の上限値は です。そして、 となる最小の は
です。言い換えると 「パスカルの三角形にもっともたくさん出てくる数の現時点でのワールド・レコードが 」 というわけですね。これが、今日の記事のタイトルだったのでした。
実際、
はすべて の値をとります。 すごい!
さらにいうと、 なる としては、今のところ しか見つかっていません!つまり 回以上パスカルの三角形に現れる数は、 以外に見つかっていないのです!
これは、 という数の性質としては申し分ないものですね。私はこの事実を知ってからしばらくの間、興奮が収まりませんでした。
ちなみに、Singmaster自身は の上限値としては、 か だろうと予想しているそうです。まだまだ先があるのですね・・・。
Singmaster's infinite family(シングマスターの無限族)
ところで、どうやって、 が大きなものを見つけたらよいでしょうか。
この問題には、Singmasterが発見した次の事実が有用です。
は無限に多くの解を持つ.その解は
で表せる. は 番目のフィボナッチ数である.ここで とする.
式 は二項係数の間の等式になっています。つまり、パスカルの三角形の「ここ」と「あそこ」が同じ値になっているということです。このような条件を満たす の組は無限に存在するというのがSingmasterの主張です。
しかも、そのような は具体的に式 の形で表すことができるというのです。さらにさらに、その式がフィボナッチ数で表されているという。
これ、なかなかすごくないですか!?
具体的に のとき、 より
なので
が成り立つはずです。実際
が成り立ちます。
実は、これが である秘密だったのです。どういうことかというと
の時点で、 はパスカルの三角形の2箇所に登場することがわかります。さらに、二項係数の性質
により
の4箇所に登場することが確定するわけです。
また、一般に
が成り立つので、あっという間に
の6箇所に出ることがわかってしまいました!
これで です!
こんな風に、Singmasterの定理の条件 を満たす の組によって得られる は、 になることが示されます。さらに、Singmasterの定理によって
これらをSingmasterの無限族と言います。素晴らしいですね。
最後に、 の次に小さいSingmasterの無限族の仲間を紹介して終わりにしましょう。
とすると、 より
が得られます。このときの は
となります。
もちろんこの も
が成り立ちます!Singmasterすごい!!
どうやって見つけたか
最後の最後に、今回のSingmasterの話の元ネタをご紹介して終わりにしましょう。
まず、最初に見つけたのはWikipediaの "3000" の記事です。
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の1975年の論文
を参考にしました。
こんな感じで見つけたものですから、日曜数学アドベントカレンダーのID番号にしてやろうと思って、虎視眈々とねらっていたのですが・・・残念ながら失敗しました。笑
結果的に、日曜数学アドベントカレンダーのIDは3009になってしまったのですが、もし3009の面白い性質を見つけた方がおられましたら、tsujimotterまでご連絡ください。
最後に紹介した「Wikipediaを使った数の性質探し」はなかなか楽しいので、ぜひ「日曜数学」として実践してみてください。
明日のアドベントカレンダーは・・・
dogradishさんが、ユークリッド幾何の第1公準について書いてくださるそうです。楽しみにしています。
それでは今日はこの辺で。
追記:3003 はなぜ8回も出てくるのか?
ところで、Singmasterの定理の条件から であることが分かったわけですが、ではなぜ なのでしょうか。これは が「三角数」であることに関係しています。
たしかに、Wikipediaの "3000" の記事には
3003 - 三角数、六角数、パスカルの三角形に8回現れる数として知られている唯一の数(8回を超えて現れる数は知られていない、en:Singmaster's conjectureを参照)
と書いてありました。「三角数」であることが実は重要だったのです。
三角数とは
のように、三角形に並べられる数のことです。式で表すと
と表すことができる のことです。これは二項係数で表すことができて
ということです。
さて、3003は
と表せますので、三角数であり、 なる二項係数で表せます。したがって
の2箇所に現れることがわかります。これらは、上で計算した6箇所とは異なりますので、計8箇所に登場することが確定します。
したがって、 です。
3003の特殊性は「Singmasterの定理の条件を満たす数(Singmasterの無限族の数)」であり「三角数」であるような、現在知られている唯一の例であるところにあったというわけです。面白いですね!!