パスカルの三角形 – 公式、パターン、例
サラ・チェン
パスカルの三角形とは何ですか?
パスカルの三角形は、特定のパターンと前の行とのつながりが続く三角形の数字の配列です。ブレーズ パスカルによって発明されました。この三角形は、最初の行の 1 つの要素から始まります。その後、各行は「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） 3 行目の 2 番目の要素は、2 番目の行の最初の数値と 2 番目の数値の合計です。
ステップ3） 1行目は「3.」で始まります。 1 番目の数値は 2 で、XNUMX と XNUMX の合計です (青で強調表示されています)。
以下の図は、XNUMX 番目の行を埋める方法を示しています。
ステップ4） 5 行目は 5 つの数字で構成されます。行にデータを入力するパターンは、前の手順ですでにわかっています。
パスカルの三角形の公式 – 二項係数
二項係数は、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
複雑さの分析
A 二次元配列 実装に使用されました。 N がパスカルの三角形の行数であるとします。 これには N が必要です2 単位空間。したがって、Oは空間計算量（N2).
関数には2つのループがあり、各ループは「N」回実行されます。したがって、時間計算量も オン2) または時間の複雑さの二乗。
方法 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
複雑さの分析
実装では0つのループが使用されました。XNUMXつのループは二項係数を計算するためのもので、他のXNUMXつはすべての行の数値を作成するためのものです。行の数に関しては、XNUMXつのループが「n」回実行されます。したがって、全体の時間計算量はXNUMX(n3).
ストレージにデータを保持しないため、空間計算量は一定になります。プログラムは要素を計算し、それを行に出力します。すると、空間計算量は 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
複雑さの分析
この実装には2つのループがあります。各ループは最大で「n」回実行されます。ここで「n」はパスカル三角形の行数を意味します。したがって、時間計算量は オン2)、二乗時間。
空間計算量に関しては、保存する配列は必要ありませんでした。前の二項係数を保持するために1つの変数を使用するだけでした。つまり、必要なスペースは1つだけです。空間計算量は 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 つの要素の合計です。
- パスカルの三角形のすべての要素を対角線で加算すると、次のようになります。 フィボナッチ配列.
- パスカルの三角形は二項係数を使用して生成することもできます。
