パスカルの三角形 – 公式、パターン、例

パスカルの三角形とは何ですか?

パスカルの三角形は、特定のパターンとその前の行への接続が続く数値の三角形配列です。 ブレーズ・パスカルによって発明されました。 この三角形は、最初の行の 1 つの要素から始まります。 以降、各行は「XNUMX」で始まり「XNUMX」で終わります。

パスカルの三角形

パスカルのトライアングルの歴史

中国の書籍「数学芸術の九章」には、パスカルの三角形の最初の例の XNUMX つが含まれています。 さらに、今日の三角形に見られるものと同じパターンと性質がいくつか含まれています。

パスカルは、ヨーロッパで三角形を研究した数人の人物のうちの XNUMX 人でした。 他の数学者は、彼の前に同様の三角形の数値配列を調べていました。

パスカルの三角形の構築

パスカルの三角形の構築は簡単です。 覚えておく必要がある唯一のことは、行は 1 で始まり XNUMX で終わるということです。残りの数値の規則は次のとおりです。

行 r と列 c の場合、数値は行 r-1 の列 c-1 と c の合計になります。

ここでは、

  • r = 3,4,5、XNUMX、XNUMX…。
  • n および c = 2,3,4、1、XNUMX、…r-XNUMX。

パスカルの三角形を構築する手順は次のとおりです。

ステップ1) まずは XNUMX 行を埋めてみましょう。

パスカルの三角形の構築

ステップ2) XNUMX 行目の XNUMX 番目の要素は、XNUMX 行目の最初と XNUMX 番目の数値の合計です。

パスカルの三角形の構築

ステップ3) 1行目は「3.」で始まります。 1 番目の数値は 2 で、XNUMX と XNUMX の合計です (青で強調表示されています)。

以下の図は、XNUMX 番目の行を埋める方法を示しています。

パスカルの三角形の構築

ステップ4) XNUMX 行目は XNUMX つの数字で構成されます。 前の手順で行を設定するパターンはすでにわかっています。

パスカルの三角形の構築

パスカルの三角形の公式 – 二項係数

二項係数は、n 個の要素の集合から k 個の要素のサブセットを選択するさまざまな方法を表す数値です。 多くの場合、「C(n,k)」または「n が k を選択」と書かれます。

二項係数は次のように定義されます。

パスカルの三角形の公式 - 二項係数

「!」 は「階乗」を表します。

ん! = n.(n-1)。 (n-2)…3.2.1

たとえば、

5! = 5.4.3.2.1

= 120

したがって、C(5,3) または 5 が 3 = 5 を選択したとしましょう。 / 3!(5-3)!

= 120/(12)

= 10

方法 1: 前の行でパスカルの三角形を構築する

この手順の手順は、パスカルの三角形の手順と同じです。 パスカルの三角形を最大 XNUMX 行まで作成したいとします。

そのための手順は次のとおりです。

ステップ1) 一番上の行は「1」から始めます。

ステップ2) 「r」行の場合、「c」項目は「c-1」と「c」に「r-1」行の番号を掛けたものになります。

ステップ3) 連続する最初と最後の数字は常に「1」になります。

パスカルの三角形を作成するには、これらの XNUMX つの簡単な手順を順守する必要があります。

前の行によるパスカルの三角形の C++ コード

#include <bits/stdc++.h>
using namespace std;
void printRow(int n)
{
  int numbers[n][n];
  for (int row = 0; row < n; row++)
  {
    for (int col = 0; col <= row; col++)
    {
      if (col == 0 || col == row)
      {
        numbers[row][col] = 1;
      }
      else
      {
        numbers[row][col] = numbers[row - 1][col - 1] + numbers[row - 1][col];
      }
      cout << numbers[row][col] << "\t";
    }
    cout << endl;
  }
}
int main()
{
  int n;
  cout << "How many rows: ";
  cin >> n;
  printRow(n);
}

出力:

How many rows: 7
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

前の行によるパスカル三角形公式の Python コード

def printRow(n):
    numbers = [[0 for row in range(n)]
               for col in range(n)
               ]
    for row in range(len(numbers)):
        for col in range(0, row+1):
            if row == col or col == 0:
                numbers[row][col] = 1
            else:
                numbers[row][col] = numbers[row-1][col-1]+numbers[row-1][col]

            print(numbers[row][col],end="\t")
        print("\n")
n = int(input("How many rows: "))
printRow(n)

パスカルの三角形の出力例:

How many rows: 7
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

とplex性分析

A 二次元配列 実装に使用されました。 N がパスカルの三角形の行数であるとします。 これには N が必要です2 ユニットスペース。 したがって、Oはスペースコムになります。plexシティ (N2).

関数には XNUMX つのループがあり、各ループは「N」回実行されます。 それで、タイムコムplexシティも オン2) または二乗時間コムplexity。

方法 2: 二項係数を計算してパスカルの三角形を構築する

二項係数を使用してパスカルの三角形の数を簡単に導き出すことができます。 図は次のとおりです。

二項係数を計算してパスカルの三角形を構築する

二項式を計算してパスカルの三角形を構築する手順は次のとおりです。

ステップ1) 最上位の行は C(0,0) になります。 上記の式を二項係数に使用すると、C(0,0) = 1 となります。なぜなら 0 だからです。 = 1。

ステップ2) 行「i」には、合計「i」個の要素が存在します。 各項目は C(n,r) として計算されます (n は i-1 になります)。

ステップ3) パスカルの三角形に必要な行数だけ手順 2 を繰り返します。

C++ コード二項係数によるパスカルの三角形

#include <iostream>
using namespace std;
int factorial(int n)
{
    int result = 1;
    for (int i = 1; i <= n; i++)
    {
        result *= i;
    }
    return result;
}
int binomialCoefficient(int n, int r)
{
    int result = 1;
    if (r > n)
    {
        return -1;
    }
    result = factorial(n) / (factorial(r) * factorial(n - r));
    return result;
}
void printPascalTriangle(int row)
{
    for (int i = 0; i <= row; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            cout << binomialCoefficient(i, j) << "\t";
        }
        cout << endl;
    }
}
int main()
{
    int n;
    cout << "Enter row number: ";
    cin >> n;
    printPascalTriangle(n);
}

出力:

Enter row number: 9
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
1	7	21	35	35	21	7	1
1	8	28	56	70	56	28	8	1
1	9	36	84	126	126	84	36	9	1

Python コードの二項係数によるパスカルの三角形

def factorial(n):
    result = 1
    for i in range(1,n+1):
        result*=i
    return result
def binomialCoefficient(n,r):
    result =1
    if r>n:
        return None
    result = factorial(n) / (factorial(r) * factorial(n - r))
    return int(result)
def printPascalTriangle(row):
    for i in range(row+1):
        for j in range(i+1):
            print(binomialCoefficient(i, j), end="\t")
        print()
# print(binomialCoefficient(3, 2))
n = int(input("Enter row number: "))
printPascalTriangle(n)

パスカルの三角形の出力例:

Enter row number: 8
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
1       7       21      35      35      21      7       1
1       8       28      56      70      56      28      8       1

とplex性分析

実装では XNUMX つのループが使用されました。 XNUMX つのループは二項係数を計算するためのもので、他の XNUMX つはすべての行の数値を作成するためのものです。 行数に関しては、「n」回実行されるループが XNUMX つあります。 したがって、全体の時間はplex性は 0(n3).

スペースコムplexストレージにデータを保持しないため、ity は一定になります。 プログラムは要素を計算し、それが行に出力されます。 スペースコムplexその後、ity は 0(1) に減少します。

方法 3: 修正二項係数によるパスカルの三角形の構築

前のテクニックでは、二項係数を使用してパスカルの三角形の各要素を計算する方法をすでに見てきました。 このアプローチでは、C.(n, r-1) から C(n,r) が決定されます。 命令が XNUMX つ増えるだけで物事が簡素化されます。

ここでは、修正二項係数によってパスカルの三角形を構築する手順を示します。

ステップ1) 最初の行を「1」で開始します

ステップ2) C(n,r) を計算します。ここで、「n」は行番号、「r」は列または要素です。 変数 C に値を代入します。

ステップ3) C(n,k) を計算する場合、C*(nk)/k となります。 次に、この値を C に代入します。

ステップ4) 「k」が行の終わりに達するまでステップ 3 を続けます。 各反復の後、K の値を XNUMX ずつ増やします。

修正二項係数によるパスカルの三角形の C++ コード

#include <bits/stdc++.h>
using namespace std;
void printpascalTriangle(int n)
{
  for (int row = 1; row <= n; row++)
  {
    int previous_coef = 1;
    for (int col = 1; col <= row; col++)
    {
      cout << previous_coef << "\t";
      previous_coef = previous_coef * (row - col) / col;
    }
    cout << endl;
  }
}

int main()
{
  int n;
  cout << "How many rows: ";
  cin >> n;
  printpascalTriangle(n);
}

出力:

How many rows: 5
1
1       1
1       2       1
1       3       3       1
1       4       6       4       1

修正二項係数によるパスカルの三角形の Python コード

def printpascalTriangle(n):
    for row in range(1, n+1):
        previous_coef = 1
        for col in range(1, row+1):
            print(previous_coef, end="\t")
            previous_coef = int(previous_coef*(row-col)/col)
        print()
n = int(input("How many rows: "))
printpascalTriangle(n)

パスカルの三角形パターンの出力:

How many rows: 5
1
1       1
1       2       1
1       3       3       1
1       4       6       4       1

とplex性分析

この実装には XNUMX つのループがあります。 各ループは最大「n」回実行されます。「n」はパスカル三角形の行数を意味します。 それで、タイムコムplex性は オン2)、二乗時間。

スペースコムについてplexなんと、配列を保存する必要はありませんでした。 前の二項係数を維持するために XNUMX つの変数を使用しただけです。 したがって、追加のスペースが XNUMX つだけ必要でした。 スペースコムplexになりました O(1).

パスカルの三角形の応用

パスカルの三角形の応用例をいくつか示します。

二項展開: パスカルの三角形から二項展開の係数を決定できます。 以下に例を示します。

(x + y)0 1
(x + y)1 1.x + 1.y
(x + y)2 1x2 + 2xy+ 1y2
(x + y)3 1x3 + 3x2および+ 3xy2 + 1y3
(x + y)4 1x4 + 4x3および+ 6x2y2 + 4xy3 + 1y4

組み合わせの計算: パスカルの三角形の要素が二項係数に相当することを見てきました。 たとえば、ボールが 6 つあり、ボールを 3 つ選ぶように求められた場合、次のようになります。 6C3. または、パスカルの三角形の 3 行目の 6 番目の要素の数字を見つけることができます。

パスカルの三角形に関する興味深い事実

パスカルの三角形について興味深い事実をいくつか紹介します。

  • 行内のすべての要素の合計は常に 2 の累乗になります。

パスカルの三角形に関する事実

  • 行の要素を対角的に合計すると、フィボナッチ数列が生成されます。

パスカルの三角形に関する事実

まとめ

  • パスカルの三角形は、二項展開の係数を与えます。
  • パスカルの三角形の各行は「1」で始まり「XNUMX」で終わります。 中間値は、前の行の XNUMX つの要素の合計です。
  • パスカルの三角形のすべての要素を対角線で加算すると、次のようになります。 フィボナッチ配列.
  • パスカルの三角形は二項係数を使用して生成することもできます。