파스칼 삼각형 공식과 예시
사라 첸
⚡ 스마트 요약
파스칼 삼각형은 각 값이 바로 위에 있는 두 값의 합과 같은 삼각형 형태의 숫자 배열로, 수 세기 동안 수학자들을 매료시켜 온 조합론, 이항 전개, 확률에 대한 심오한 패턴을 보여줍니다.
파스칼의 삼각형은 무엇입니까?
파스칼 삼각형은 바로 위 행의 숫자에 따라 간단한 패턴을 따르는 삼각형 모양의 숫자 배열입니다. 17세기에 프랑스 수학자 블레즈 파스칼에 의해 널리 알려졌습니다. 삼각형의 맨 위 행은 "1"로 시작하며, 이후 모든 행의 시작과 끝도 "1"로 끝납니다.
파스칼 삼각형은 그 우아한 모양 외에도 심오한 수학적 관계를 담고 있습니다. 이 삼각형은 이항 정리, 조합론, 확률과 밀접한 관련이 있으며, 이러한 이유로 전 세계 대수학, 통계학, 컴퓨터 과학 강의실에서 찾아볼 수 있습니다.
파스칼의 삼각형 역사
비록 블레즈 파스칼의 이름을 따서 명명되었지만, 삼각형은 그보다 수 세기 앞서 존재했습니다. 중국의 수학 서적인 "구장조(九八劍八)"(九八劍八劍)에는 오늘날 우리가 사용하는 것과 동일한 패턴을 보여주는 가장 초기의 예 중 하나가 담겨 있습니다.
페르시아 수학자 알 카라지와 인도 학자 Ping알라(ala) 또한 유사한 배열을 탐구했습니다. 파스칼은 1654년 저서 "산술 삼각형에 관하여(Traité du triangle arithmétique)"에서 삼각형의 속성을 공식화했으며, 이 논문은 서양 수학에서 이 구조에 현대적인 이름을 부여했습니다.
파스칼의 삼각형 만들기
파스칼 삼각형을 만드는 것은 간단합니다. 기억해야 할 유일한 규칙은 각 행이 1로 시작하고 1로 끝나며, 각 행의 숫자는 바로 위 행의 숫자를 기반으로 만들어진다는 것입니다.
임의의 행 r과 열 c에 대해, 해당 값은 행 r-1의 c-1열과 c열에 있는 숫자의 합과 같습니다.
여기
- r = 3, 4, 5, …
- n과 c = 2, 3, 4, …, r-1.
파스칼 삼각형을 만드는 단계는 다음과 같습니다.
단계 1) 첫 두 줄부터 채워주세요.
단계 2) 세 번째 행의 두 번째 요소는 두 번째 행의 첫 번째 숫자와 두 번째 숫자의 합입니다.
단계 3) 네 번째 줄은 "1"로 시작합니다. 두 번째 숫자는 3인데, 이는 1과 2를 더한 값입니다(파란색으로 강조 표시됨).
아래 이미지는 네 번째 줄을 채우는 방법을 보여줍니다.
단계 4) 다섯 번째 행은 다섯 개의 숫자로 구성됩니다. 우리는 앞선 단계에서 행을 채우는 패턴을 이미 알고 있습니다.
파스칼의 삼각형 공식 - 이항 계수
이항 계수는 n개의 원소로 이루어진 집합에서 k개의 원소로 이루어진 부분집합을 선택하는 경우의 수를 나타냅니다. 일반적으로 “C(n, k)” 또는 “n choose k”로 표기합니다.
이항계수는 다음과 같이 정의됩니다.
"!" 기호는 어떤 수의 팩토리얼을 나타냅니다.
n! = 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: 이전 행을 이용하여 파스칼 삼각형 만들기
여기서의 절차는 우리가 삼각형을 수동으로 그리는 방식과 동일합니다. 파스칼 삼각형을 최대 7행까지 생성한다고 가정해 보겠습니다.
그 방법은 다음과 같습니다.
단계 1) 맨 위 줄은 "1"부터 시작하세요.
단계 2) "r" 행의 경우, "c" 요소는 "c-1" 열과 "r-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)
Pascal의 삼각형 예제 출력:
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 XNUMX차원 배열 이 구현에서는 가 사용됩니다. 파스칼 삼각형의 행 수가 N이라고 할 때, 이는 N이 필요합니다.2 단위 공간입니다. 따라서 공간 복잡도는 O(N)입니다.2).
이 함수는 각각 최대 "N"번 실행되는 두 개의 중첩 루프를 사용합니다. 따라서 시간 복잡도 또한 다음과 같습니다. 의 위에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)
Pascal의 삼각형 예제 출력:
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
복잡성 분석
이 구현에서는 세 개의 반복문이 사용됩니다. 하나는 이항 계수를 계산하는 반복문이고, 나머지 두 개는 모든 행과 열을 순회하는 반복문입니다. 행의 개수에 따라 세 개의 반복문은 모두 "n"번 실행됩니다. 따라서 전체 시간 복잡도는 O(n)입니다.3).
중간 결과를 저장하지 않으므로 공간 복잡도는 상수입니다. 프로그램은 각 요소를 즉시 계산하여 행 내에 출력하므로 공간 복잡도는 다음과 같이 줄어듭니다. O (1).
방법 3: 수정된 이항 계수로 파스칼의 삼각형 만들기
이전 기법에서는 이항계수 공식을 사용하여 각 요소를 계산했습니다. 수정된 접근 방식은 C(n, r)을 C(n, r-1)에서 직접 도출하여 계산량을 한 자릿수만큼 줄입니다.
수정된 이항계수를 이용하여 파스칼 삼각형을 만드는 단계는 다음과 같습니다.
단계 1) 첫 번째 행을 "1"로 초기화합니다.
단계 2) 행 번호 "n"과 열 인덱스 "r"에 대해 C(n, r)을 계산합니다. 이 값을 변수 C에 할당합니다.
단계 3) 다음 계수를 계산하려면 C * (n – k) / k를 사용합니다. 이 새로운 값을 다시 C에 할당합니다.
단계 4) "k"가 행의 끝에 도달할 때까지 3단계를 계속합니다. 각 반복 후에는 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)
Pascal의 삼각형 패턴 출력:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
복잡성 분석
이 구현은 두 개의 반복문을 사용하며, 각 반복문은 최대 "n"번 실행됩니다. 여기서 "n"은 삼각형의 행 수입니다. 따라서 시간 복잡도는 다음과 같습니다. 의 위에2), 시간의 제곱.
공간 복잡도 측면에서 보면, 저장을 위한 배열은 필요하지 않습니다. 이전 이항 계수를 저장하는 데 하나의 변수만 사용하므로 추가 공간은 하나만 필요합니다. 따라서 공간 복잡도는 다음과 같습니다. 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번째 행의 세 번째 요소에서 찾을 수 있습니다.
개연성: 파스칼 삼각형은 동전 던지기, 주사위 문제 및 각 결과가 이항 분포에 해당하는 기타 조합 사건에서 확률을 계산하는 데 널리 사용됩니다.
파스칼의 삼각형에 관한 흥미로운 사실
파스칼의 삼각형에 관해 흥미로운 사실은 다음과 같습니다.
- 어떤 행에 있는 모든 요소의 합은 항상 2의 거듭제곱입니다.
- 각 행의 대각선 합이 피보나치 수열을 이룹니다.
- 각 행은 (a+b)의 전개식에서 계수에 해당합니다.n.
- 홀수 부분만 색칠하면 시에르핀스키 삼각형 프랙탈이 만들어집니다.
