パスカルの三角形計算

C(n, k) = C(n-1, k-1) + C(n-1, k)、C(n, 0) = C(n, n) = 1、行の合計 = 2^n

n

印字する行数で、いちばん上の1つだけの1を行0と数えます。つまりn行とは行0から行n − 1までのことで、最後に印字される行はn個の項を持ちます。入力は1から53までで、この上限は画面の大きさの話ではありません。先に限界が来るのは行の合計のほうで、その話は下の項目にあります。

k

行の中の位置で、左端を0として数えます。行nにはk = 0からk = nまでの項があり、個数はn + 1です。両端の2つは特別で、C(n, 0)とC(n, n)はどちらも1になり、それが三角形の左右を走る1の並びです。その間にある項はすべて、上の行の2つの項の和です。

C(n-1, k-1) + C(n-1, k)

全体を組み立てる規則で、このページが使っているものでもあります。行nの位置kの項は、その上の2つの項の和です。すぐ左上とすぐ右上の2つで、だから端は1つしか見えず1のままになります。この計算は階乗の式ではなく足し算で行うので、途中の値がすべて正確で、画面に出る三角形はこのページが実際に行った足し算そのものになります。

C(n, k) = n! / (k! (n-k)!)

同じ数のもう1つの顔で、順番を区別せずにn個からk個を選ぶ場合の数です。足し算の規則と同じ値を与え、三角形を代数ではなく数え上げに使うときには、行に並ぶ数の意味そのものになります。このページがこちらで計算しないのは、そうすると2つの別々の計算になって食い違いうるからです。

2^n

行nの合計で、入力がどこで止まるかを決めている量でもあります。行を合計すると必ず2の累乗になります。行0は1、行1は2、行2は4、行6は64です。1行ごとに2倍になるので、個々の係数より先に、合計のほうが正確に表せる範囲を出てしまいます。行52の合計は4503599627370496、行53は9007199254740992で、これは倍精度数が正確に持てる最後の整数の1つ次です。

1, 6, 15, 20, 15, 6, 1

行6を書き出したもので、既定の7行の最後の行です。上の行と見比べながら読むと、どの項も隣り合う2つの和になっています。6は1 + 5、15は5 + 10、20は10 + 10で、あとは鏡写しです。行が真ん中について対称なのはいつも通りで、残すk個を選ぶことと捨てるn − k個を選ぶことが、同じ選択を2通りに数えたものだからです。

二項式を手で展開するいちばん速い道がこの三角形です。(x + y)を6乗に展開するには、6行目をそのまま読んで1x⁶ + 6x⁵y + 15x⁴y² + 20x³y³ + 15x²y⁴ + 6xy⁵ + 1y⁶と書けます。多項式の掛け算は一切要りません。項が1つだけ欲しいときは二項係数が1つあれば足り、組み合わせのページがnとkから直接計算します。行を間にはさむ必要はありません。結果が2通りしかない確率の問題も同じ数を使います。10回投げて表がちょうど4回出る確率はC(10, 4)を2^10で割ったもので、その1,024は行10の合計です。三角形は、一見無関係に見える数え上げの問いにも答えます。格子を一方の角から反対の角まで進む道の数、右と下にしか動けないとして特定のマスに着く場合の数、決まった大きさの部分集合の個数です。数そのものが欲しいのか、その意味が知りたいのかで行き先が変わります。数が欲しいときはこのページが印字し、何通りの起き方があるかを知りたいときは組み合わせのページのほうが近道です。斜めの線に隠れているフィボナッチ数の話は、フィボナッチのページがその数列を直接扱っています。

1. 7行で、1、6、15、20、15、6、1で終わる

   1. 行0は1、行1は1、1です。どの行も両端はいつも1です
   2. 行2は真ん中の1 + 1 = 2で、1、2、1になります
   3. 行3は1 + 2 = 3が2回で1、3、3、1、行4は1 + 3 = 4と3 + 3 = 6で1、4、6、4、1です
   4. 行5と行6も同じ調子で続き、1、6、15、20、15、6、1で終わります
   5. 行6を足し合わせます。1 + 6 + 15 + 20 + 15 + 6 + 1 = 64で、これは2の6乗です

   既定の入力です。画面と突き合わせて確かめる価値のある点が2つあります。1つ目は、どの数もその上の2つの和になっていることです。15は5 + 10、20は10 + 10で、行が対称なのは、20が7つの項の真ん中にいて左右に1つずつ組になるからです。2つ目は、行の合計が毎回2倍になることです。1、2、4、8、16、32、64なので、上の行が32だと知っている読者は足す前にこの行を予想できます。この2倍は、両端の1が2つあることと同じ事実です。上の行はその合計をまるごと2回、左半分に1回と右半分に1回ぶん渡しているからです。

2. 4行、いちばん短い実用的な三角形

   1. 行0は1、行1は1、1です
   2. 行2は1、2、1で、2は1 + 1から来ます
   3. 行3は1、3、3、1で、3はそれぞれ1 + 2から来ます
   4. 最後の行を合計します。1 + 3 + 3 + 1 = 8で、これは2の3乗です

   ここでは行3が最後の行で、三角形が面白くなり始めるのはここです。1、3、3、1は(x + y)³の係数なので、x³ + 3x²y + 3xy² + y³を、何も掛け合わせずにこの行から書き下せます。手で数秒で確かめられる最後の行でもあるので、長い行の前に見ておく価値があります。4行と言ったら行0から行3までのことです。入力する数は行数であって、いちばん大きい行の番号ではありません。

3. 1行、自明な場合

   1. 行0は1つだけの1で、上に足すものがありません
   2. 1行を頼まれ、1行が印字されました
   3. 行の合計は1で、これは2の0乗です

   このページが受け付けるいちばん小さな入力で、空として扱われるのではなくちゃんと受け付けられます。1行の三角形は退化ではなく、それ以降のすべての行がそこから組み立てられる基本の場合です。これを読むと添字の付け方も確かめられます。1行を頼むと行1ではなく行0が出るので、三角形と二項展開を見比べるときに効いてきます。合計が0ではなく1になるのは、三角形の頂点が1つだけの1であることと同じ主張です。

行数は1から53までの整数でなければなりません。この上限があるのは、印字する数がすべて、コンピュータが正確に表せる整数でなければならないからです。それを超えると隣り合う2つの整数が同じ値に潰れてしまいます。印字された桁はごく普通に見えたまま、もはや主張している数を表さなくなります。先に音を上げるのは行の合計のほうで、行52の合計は4503599627370496、行53は9007199254740992、倍精度数が正確に持てる最大の整数の1つ次です。個々の係数なら行56までは持ちこたえますが、最初に線を越えるのは行57のC(57, 28)です。それでも三角形は1行ずつ印字するものなので、決めるのは合計のほうです。0行は断ります。空の三角形は何も印字しないので、返す答えがありません。行の小数も丸めずに拒否します。2行半というものは存在しないからです。行は数字をコンマで区切った1本の長い行として返り、行と行はセミコロンで区切られます。千位の区切りはどこにも入らないので、大きな係数は184,756ではなく「184756」と印字されます。横に長い三角形では、それは延々とスクロールする1行になります。下の参考表は最初の7行を出すだけで、あなたの入力には追随しません。また、どの行もそれを名指しで頼んで取り出すことはできず、ページはいつも上から下へ印字します。

パスカルの三角形は何に使われますか

二項式の展開が主な用途です。行nの項は(x + y)をn乗に展開したときの係数なので、行6があれば(x + y)⁶の7つの項を、多項式を1つも掛け合わせずにすぐ書き下せます。同じ数が組み合わせも数えます。C(n, k)は行nの位置kの項なので、10人から4人を選ぶ方法は何通りか、といった問いに答えます。確率にも現れます。10回の硬貨投げで表がちょうど4回出る確率は、2^10のうちのC(10, 4)で、その1,024は行10の合計です。格子の道順を数えるのにも使います。一方の角から反対の角まで、右と下にだけ動いて渡る道の数は、三角形の1つの項になります。

なぜ入力は53行で止まるのですか

行の合計が、コンピュータが正確に表せる整数でなくなってしまうからです。行52の合計は4503599627370496、行53は9007199254740992で、この2つ目の数は倍精度数が正確に持てる最大の値の1つ次です。それを超えると隣り合う2つの整数が同じ値になるので、印字された桁は普通に見えたまま、主張している数を表さなくなります。個々の係数ならもっと持ちこたえます。最初に線を越えるのは行57のC(57, 28)です。それでも三角形は1行ずつ印字するものなので、決めるのは合計のほうです。合計だけが間違っていて個々の項は正しい行を出すのは、とても混乱するものになります。

なぜ最後の行が2回印字されるのですか

大きな三角形では、ほとんどの読者が欲しいのは最後の行だけで、長い数字の列の中からそれを見つけるのは手間だからです。40行を頼むと、三角形の出力は数字の壁になり、目当ての行は右端のほうにあります。最後の行の出力は、その同じ行を単独で、読める大きさで出したものです。どちらも同じ計算から来ているので、食い違うことはありません。行の合計が3つ目に印字されるのも同じ理由です。数字の列では一目で分からない問いに答える、1つの数だからです。

行は0から始まりますか、1からですか

0からです。二項係数が普通そのように添字を振られるからです。C(n, k)は行nの位置kの項を意味するので、いちばん上の1つだけの1が行0で、7行を頼むと行0から行6まで、1、6、15、20、15、6、1で終わります。行nはいつもn + 1個の項を持つので、7つの数です。これは三角形と二項展開を見比べるときに効いてきます。(x + y)⁶の係数の行は行7ではなく行6です。入力する数は行数であって、いちばん大きい行の番号ではありません。

行の合計とは何で、なぜいつも2の累乗なのですか

どの行を足し合わせても、行の番号を指数とする2の累乗になります。行0は1、行6は64、行10は1,024です。理由は三角形を組み立てる規則にあります。各行は上の行に、1つずらした同じ行を足して作られるので、上の行のどの数も下の行で2回、左側に1回と右側に1回ずつ数えられます。合計が毎回2倍になるので、2の累乗になるのです。同じ事実は別の言い方もできます。行nの合計はn個の要素を持つ集合の部分集合をすべて数えたもので、そのような部分集合は2のn乗個あります。10回の硬貨投げの確率の下に出てくる1,024が行10から直接出てくるのは、そのためです。

この三角形のどこからフィボナッチ数が出てくるのですか

浅い斜めの線からです。左上へ向かって走る線に沿って数を足していくと、たとえば1、次に4、次に3で、途中までの合計は1、1、2、3、5、8、13となります。これがフィボナッチ数で、それぞれが前の2つの和になっています。理由は、斜めの線の各項が、それ自体が上の2つの項から作られていて、そのうち1つは同じ斜めの線に乗り、もう1つは隣の斜めの線に乗っているからです。だから斜めの線はフィボナッチの漸化式をそのまま受け継ぎます。この数列をもっと追いたいときは、フィボナッチのページがその数列を直接扱っています。

• Pascal's Triangle — 二項係数を並べた配列と、その足し算の規則、そこから出てくる諸性質 — Wolfram MathWorld (United States)
• Binomial Coefficient — C(n, k) が数えているもの、階乗の式、そして足し算の規則が同じ値を与える理由 — Wolfram MathWorld (United States)
• Binomial Theorem — (x + y)^nの展開と、その係数が三角形の各行になること — Wolfram MathWorld (United States)
• 学習指導要領（平成29・30・31年改訂） — 中学校の「数と式」で扱う式の展開と、高等学校で扱う二項定理・場合の数の根拠になる文部科学省の告示・解説 — 文部科学省