YEND WRITING

パスカルの三角形

TypeScriptでパスカルの三角形を実装してみる。

パスカルの三角形とは？

Wikipedia には次のように説明がある。

パスカルの三角形（パスカルのさんかくけい、英: Pascal’s triangle）は、二項展開における係数を三角形状に並べたものである。

これだけではよく分からないので、以下に図を示す。

            1
          1   1
        1   2   1
      1   3   3   1
    1   4   6   4   1
  1   5  10  10   5   1
1   6  15  20  15   6   1

パスカルの三角形は、次のルールで構成される。

  • 最上段（0行目）は 1 のみである
  • 各行の端は常に 1 である
  • それ以外の数字は、上の行の隣り合う2つの数字の和になる

パスカルの三角形と二項係数

パスカルの三角形の数字は、二項係数 を並べたものとしても解釈できる。

二項係数は nCknCk や (nr)\begin{pmatrix} n \\ r \end{pmatrix} と表記され、以下の式で計算される。

nCk=n!k!⋅(n−k)!nCk = \frac{n!}{k! \cdot (n-k)!}

パスカルの三角形を二項係数の形で表現すると、次のようになる。

                 0C0
              1C0   1C1
            2C0   2C1   2C2
         3C0   3C1   3C2   3C3
      4C0   4C1   4C2   4C3   4C4
   5C0   5C1   5C2   5C3   5C4   5C5
6C0   6C1   6C2   6C3   6C4   6C5   6C6

TypeScriptでの実装

それでは、TypeScript でパスカルの三角形を実装してみる。

/**
 * 二項係数（nCr）を計算する関数
 * @param n 全体の数
 * @param r 選ぶ数
 * @returns 組み合わせの数
 */
const combination = (n: number, r: number): number => {
  if (r === 0 || r === n) return 1;
  if (r > n) return 0;

  let result = 1;
  for (let i = 1; i <= r; i++) {
    result *= n - i + 1;
    result /= i;
  }
  return result;
};

/**
 * パスカルの三角形の1行を出力する関数
 * @param row 出力する行番号（0から始まる）
 */
const logPascalRow = (row: number): void => {
  let line = "";
  for (let r = 0; r <= row; r++) {
    const value = combination(row, r);
    line += value + " ";
  }
  console.log(line);
};

// パスカルの三角形を出力
const N = 7;
console.log("出力:");
for (let i = 0; i < N; i++) {
  logPascalRow(i);
}

/* 出力:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
*/

参考