C#で指定した行数のパスカルの三角形を生成する方法を解説

パスカルの三角形は、三角形の形に並べられた数列のパターンです。数学や統計学の分野で幅広く応用されており、特に組み合わせ（コンビネーション）の計算に役立つことで知られています。

パスカルの三角形とは

パスカルの三角形では、各行の数値はその上の行にある2つの数値を足したものになります。たとえば、4行目の「6」は、1つ上の行にある「3」と「3」の合計です。また、どの行でも最初と最後の数値は必ず「1」になります。

具体的な構造は以下のようになります。

        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1

計算量

時間計算量： O(N)
空間計算量： O(N)

ここでのNは生成する行数を表し、各行を順番に作成していくため、全体として線形オーダーで処理が完了します。

C#による実装例

以下のコードは、指定された行数nのパスカルの三角形をList<List<int>>として生成する実装例です。最初の行に「1」を設定し、以降は前の行の隣り合う要素同士を足し合わせて新しい行を作っていきます。

public class Arrays {
    public List<List<int>> GeneratePascal(int n) {
        List<List<int>> res = new List<List<int>>();

        // 行数が0以下の場合はnullを返す
        if (n <= 0) {
            return null;
        }

        // 最初の行は必ず「1」
        List<int> first = new List<int>();
        first.Add(1);
        res.Add(first);

        // 1行だけの場合はここで終了
        if (n == 1) {
            return res;
        }

        // 2行目以降を順に生成
        for (int i = 2; i <= n; i++) {
            List<int> prev = res.LastOrDefault();
            List<int> cur = new List<int>();

            // 新しい行をすべて「1」で初期化
            for (int temp = 0; temp < i; temp++) {
                cur.Add(1);
            }

            // 両端以外は前の行の隣接する2つの値の合計を代入
            for (int j = 1; j < i - 1; j++) {
                cur[j] = prev[j - 1] + prev[j];
            }

            res.Add(cur);
        }

        return res;
    }
}

static void Main(string[] args) {
    Arrays s = new Arrays();
    var res = s.GeneratePascal(5);
}

実装のポイント

• 初期化： 新しい行をすべて「1」で埋めてから、両端を除く要素を前の行の値で上書きします。これにより、行の両端が必ず「1」になるルールを自然に満たせます。
• 境界チェック： nが0以下の場合はnullを返し、nが1の場合は最初の行のみを返すことで、入力の異常系に対応しています。
• 前の行の参照： LastOrDefault()を使って直前に生成した行を取得し、隣接する2つの要素prev[j - 1]とprev[j]の合計を新しい行に代入します。

出力結果

GeneratePascal(5)を実行すると、5行分のパスカルの三角形が以下のように出力されます。

[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

このように、C#のリスト操作を組み合わせるだけで、パスカルの三角形をシンプルかつ効率的に生成できます。組み合わせ計算や二項定理の展開係数を求めたい場合などにも、このアルゴリズムは非常に有用です。