パスカルの三角形の公式と例
サラ・チェン
⚡ スマートサマリー
パスカルの三角形とは、各数値がその真上にある2つの数値の和に等しくなるように配置された三角形の数値のことで、組み合わせ論、二項展開、確率論における深いパターンを明らかにし、何世紀にもわたって数学者を魅了してきた。
パスカルの三角形とは何ですか?
パスカルの三角形は、上の行に基づいて単純なパターンに従う、三角形の数字の配列です。17世紀にフランスの数学者ブレーズ・パスカルによって広められました。三角形は一番上に「1」が1つだけあり、それ以降のすべての行も「1」で始まり「1」で終わります。
パスカルの三角形は、その優美な形状だけでなく、深い数学的関係性を内包している。二項定理、組み合わせ論、確率論と密接に関連しているため、世界中の代数学、統計学、コンピュータサイエンスの授業で取り上げられている。
パスカルのトライアングルの歴史
三角形はブレーズ・パスカルにちなんで名付けられたが、その起源は彼より数世紀も遡る。中国の数学書『九章算術』には、現存する最古の例の一つが掲載されており、今日私たちが用いる多くのパターンが示されている。
ペルシャの数学者アル・カラジとインドの学者 Pingアラも同様の配列を研究した。パスカルは1654年の論文「算術三角形論」で三角形の性質を体系化し、西洋数学においてこの構造に現代の名称を与えた。
パスカルの三角形の構築
パスカルの三角形を作るのは簡単です。覚えておくべき唯一のルールは、各行は1で始まり1で終わること、そしてそれ以外の数字はすべて上の行の数字から作られるということです。
任意の行 r と列 c について、その値は行 r-1 の列 c-1 と列 c の数値の合計に等しくなります。
ここでは、
- r = 3, 4, 5, …
- nとc = 2, 3, 4, …, r-1。
パスカルの三角形を作る手順は以下のとおりです。
ステップ1） まず最初の2行を埋めてください。
ステップ2） 3行目の2番目の要素は、2行目の1番目と2番目の数値の合計です。
ステップ3） 4行目は「1」で始まります。2番目の数字は3で、これは1と2の合計です（青色で強調表示されています）。
下の画像は、4行目を埋める方法を示しています。
ステップ4） 5行目は5つの数字で構成されています。行を埋めるパターンは、前の手順ですでに分かっています。
パスカルの三角形の公式 – 二項係数
二項係数は、n個の要素からk個の要素を選ぶ方法の数を表します。一般的には「C(n, k)」または「n個の中からk個を選ぶ」と表記されます。
二項係数は次のように定義されます。
「!」記号は、数の階乗を表します。
n! = n.(n-1).(n-2)…3.2.1
たとえば、
5！ = 5.4.3.2.1
= 120
つまり、C(5, 3) または「5 choose 3」= 5! / 3!(5-3)!
= 120/12
= 10
方法1：前の行を使ってパスカルの三角形を作る
ここでの手順は、三角形を手動で描画した方法と同じです。パスカルの三角形を最大7行まで生成したいとしましょう。
その手順は以下のとおりです。
ステップ1） 一番上の行を「1」から始めます。
ステップ2） 行「r」の場合、要素「c」は、行「r-1」の列「c-1」と列「c」の合計になります。
ステップ3） 各行の最初と最後の数字は必ず「1」になります。
これら３つの簡単な手順に従うことで、三角形全体を体系的に構築することができます。
C++ Code パスカルの三角形の前の行
#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 Code パスカルの三角形の公式を前の行で表す
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(N)である。2).
この関数は、それぞれ最大「N」回実行される2つのネストされたループを使用します。したがって、時間計算量も オン2)または、時間計算量の二乗。
方法2：二項係数を計算してパスカルの三角形を構築する
パスカルの三角形の各要素は、二項係数を用いて直接導出できます。下の図はその関係を示しています。
二項係数を計算してパスカルの三角形を作成する手順は以下のとおりです。
ステップ1） 一番上の行は C(0, 0) です。上記の式を用いると、0! = 1 なので、C(0, 0) = 1 となります。
ステップ2） 行「i」には合計「i」個の要素があります。各項目はC(n, r)として計算され、nはi-1です。
ステップ3） パスカルの三角形を生成したい行数だけ、手順2を繰り返してください。
C++ Code 二項係数によるパスカルの三角形
#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 Code 二項係数によるパスカルの三角形
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
複雑さの分析
この実装では3つのループが使用されています。1つは二項係数を計算するため、残りの2つは各行と各列を反復処理するためです。行数に関して、これら3つのループはすべて「n」回実行されます。したがって、全体の時間計算量はO(n)となります。3).
中間結果を一切保存しないため、空間計算量は一定です。プログラムは各要素をその場で計算し、行内に出力するため、空間計算量は減少します。 O（1）.
方法 3: 修正二項係数によるパスカルの三角形の構築
従来の手法では、二項係数式を用いて各要素を計算していました。改良された手法では、C(n, r)をC(n, r-1)から直接導出することで、計算量を1桁削減します。
修正二項係数を用いてパスカルの三角形を構築する手順は以下のとおりです。
ステップ1） 最初の行を「1」で開始します。
ステップ2） 行番号を「n」、列インデックスを「r」として、C(n, r)を計算します。その値を変数Cに代入します。
ステップ3） 次の係数を計算するには、C * (n – k) / k を使用します。この新しい値を C に代入します。
ステップ4） ステップ3を「k」が行の末尾に達するまで続けます。各反復処理の後、kを1ずつ増やします。
C++ Code 修正二項係数によるパスカルの三角形
#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 Code 修正二項係数によるパスカルの三角形
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
複雑さの分析
実装では、それぞれ最大で「n」回実行される2つのループを使用します。ここで「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その値は、パスカルの三角形の6行目の3番目の要素で見つけることができます。
確率： パスカルの三角形は、コイン投げ、サイコロ問題、その他各結果が二項分布に対応する組み合わせ事象における確率を計算するために広く用いられている。
パスカルの三角形に関する興味深い事実
パスカルの三角形について興味深い事実をいくつか紹介します。
- どの行においても、すべての要素の合計は常に2のべき乗となる。
- 行の対角線の合計はフィボナッチ数列を生成する。
- 各行は、(a+b) の展開における係数に対応します。n.
- 奇数だけを塗りつぶすと、結果として得られる図形はシェルピンスキーの三角形フラクタルを形成します。
