Pascalův trojúhelník – vzorec, vzory a příklady
Sarah Chen
Co je Pascalův trojúhelník?
Pascalův trojúhelník je trojúhelníkové pole čísel následovaných určitým vzorem a spojením s řádkem před ním. Vynalezl jej Blaise Pascal. Tento trojúhelník začíná jedním prvkem v první řadě. Poté každý řádek začíná a končí „1“.
Historie Pascalova trojúhelníku
Čínská kniha „Devět kapitol o matematickém umění“ obsahuje jeden z prvních příkladů Pascalova trojúhelníku. Kromě toho obsahuje některé ze stejných vzorů a vlastností, jaké se dnes vyskytují v trojúhelníkech.
Pascal byl jedním z několika lidí v Evropě, kteří studovali trojúhelník. Jiní matematici zkoumali podobná trojúhelníková pole čísel před ním.
Konstrukce Pascalova trojúhelníku
Konstrukce Pascalova trojúhelníku je jednoduchá. Jediné, co si musíte zapamatovat, je, že řádek začíná a končí 1. Pro zbytek čísel platí následující pravidlo:
Pro libovolný řádek r a sloupec c bude číslo součtem sloupců c-1 a c z řádku r-1.
Zde,
- r = 3,4,5….
- nac = 2,3,4,…r-1.
Zde jsou kroky k sestavení Pascalova trojúhelníku:
Krok 1) Začněme vyplněním dvou řádků.
Krok 2) Druhý prvek pro třetí řádek je součtem prvního a druhého čísla ve druhém řádku.
Krok 3) Čtvrtý řádek bude začínat "1.". Druhé číslo je 3, což je součet 1 a 2 (zvýrazněno modře).
Níže uvedený obrázek ukazuje, jak vyplnit čtvrtý řádek:
Krok 4) Pátá řada se bude skládat z pěti čísel. Vzor pro vyplnění řádků již známe z předchozích kroků.
Pascalův trojúhelníkový vzorec – binomický koeficient
Binomický koeficient je číslo, které vyjadřuje různé metody pro výběr podmnožiny k prvků z kolekce n prvků. Často se zapisuje jako „C(n,k)“ nebo „n zvolte k“.
Binomický koeficient je definován jako
"!" označuje „faktoriální“.
n! = n.(n-1). (n-2)…3.2.1
Například,
5 = 5.4.3.2.1
= 120
Řekněme tedy, že C(5,3) nebo 5 zvolí 3 = 5! / 3! (5-3)!
= 120/(12)
= 10
Metoda 1: Sestavení Pascalova trojúhelníku podle předchozí řady
Kroky v tomto postupu jsou stejné jako kroky v Pascalově trojúhelníku. Řekněme, že chceme vytvořit Pascalův trojúhelník až do sedmi řad.
Kroky, jak toho dosáhnout, jsou následující:
Krok 1) Začněte nejvyšší řádek s „1“.
Krok 2) Pro řádek „r“ bude položka „c“ součinem „c-1“ a „c“ číslem řádku „r-1“.
Krok 3) První a poslední číslo v řadě bude vždy „1“.
Abychom vytvořili Pascalův trojúhelník, musíme dodržet tyto tři snadné kroky.
C++ Kód Pascalova trojúhelníku předchozí řadou
#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);
}
Výstup:
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 Kód vzorce Pascal Triangle podle předchozího řádku
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)
Výstup příkladu Pascalova trojúhelníku:
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
Analýza složitosti
A dvourozměrné pole byl použit při realizaci. Vzhledem k tomu, že N je počet řádků v Pascalově trojúhelníku. To bude vyžadovat N2 jednotkové prostory. Proto O bude prostorová složitost (N2).
Ve funkci máme dvě smyčky a každá smyčka běží „N“ krát. Tedy i časová náročnost NA2) nebo kvadrát časové složitosti.
Metoda 2: Sestavení Pascalova trojúhelníku výpočtem binomického koeficientu
Čísla Pascalova trojúhelníku můžeme jednoduše odvodit pomocí binomického koeficientu. Zde je schéma:
Zde jsou kroky k sestavení Pascalova trojúhelníku výpočtem binomu:
Krok 1) Nejvyšší řádek bude C(0,0). Pomocí výše uvedeného vzorce pro binomický koeficient je C(0,0) = 1. Protože 0! = 1.
Krok 2) Pro řádek „i“ bude celkový počet prvků „i“. Každá položka bude vypočítána C(n,r), kde n bude i-1.
Krok 3) Opakujte krok 2 pro požadovaný počet řádků pro pascalův trojúhelník.
C++ Kód Pascalův trojúhelník pomocí binomického koeficientu
#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);
}
Výstup:
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 Kód Pascalův trojúhelník pomocí binomického koeficientu
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)
Výstup příkladu Pascalova trojúhelníku:
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
Analýza složitosti
Při realizaci byly použity tři smyčky. Jedna smyčka je pro výpočet binomického koeficientu a další dvě jsou pro vytváření čísel pro všechny řádky. Pokud jde o počet řádků, máme tři smyčky, které se provádějí „n“ krát. V důsledku toho bude celková časová složitost 0 (n3).
Prostorová složitost je nyní konstantní, protože v úložišti neuchováváme žádná data. Program vypočítá prvek a vytiskne jej v řadě. Prostorová složitost se pak sníží na 0(1).
Metoda 3: Sestavení Pascalova trojúhelníku pomocí modifikovaného binomického koeficientu
V předchozí technice jsme již viděli, jak použít binomický koeficient k výpočtu každého prvku Pascalova trojúhelníku. Tento přístup určí C(n,r) z C. (n, r-1). Zjednoduší to o jednu objednávku.
Zde jsou kroky k sestavení Pascalova trojúhelníku pomocí modifikovaného binomického koeficientu:
Krok 1) Zahajte první řádek s „1“
Krok 2) Vypočítejte C(n,r), kde „n“ je číslo řádku a „r“ je sloupec nebo prvek. Přiřaďte hodnotu do proměnné C.
Krok 3) Pro výpočet C(n,k) to bude C*(nk)/k. Nyní přiřaďte tuto hodnotu C.
Krok 4) Pokračujte krokem 3, dokud „k“ nedosáhne konce řádku. Po každé iteraci zvyšte hodnotu K o jedna.
C++ Kód pro Pascalův trojúhelník upraveným binomickým koeficientem
#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);
}
Výstup:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python kód pro Pascalův trojúhelník upraveným binomickým koeficientem
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)
Výstup vzorů Pascalova trojúhelníku:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Analýza složitosti
Implementace má dvě smyčky. Každá smyčka běží maximálně po dobu „n“, kde „n“ znamená počet řádků v pascalském trojúhelníku. Časová složitost tedy je Na2), čas na druhou.
Pokud jde o složitost prostoru, nepotřebovali jsme žádné pole k uložení. Právě jsme použili jednu proměnnou k zachování předchozího binomického koeficientu. Takže jsme potřebovali jen jedno místo navíc. Vesmírná složitost se stala O (1).
Aplikace Pascalova trojúhelníku
Zde jsou některé aplikace Pascalova trojúhelníku:
Binomické rozšíření: Koeficient binomických rozšíření můžeme určit z Pascalova trojúhelníku. Zde je příklad:
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2a + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3a + 6x2y2 + 4xy3 + 1y4 |
Výpočet kombinací: Viděli jsme, že prvky Pascalova trojúhelníku jsou ekvivalentní binomickým koeficientům. Například, pokud máte 6 míčků a byli jste požádáni, abyste si vybrali 3 míče, bude to tak 6C3. Nebo můžete číslo najít ve 3. prvku 6. řady z Pascalova trojúhelníku.
Zajímavá fakta o Pascalově trojúhelníku
Zde jsou některá zajímavá fakta o Pascalově trojúhelníku:
- Součet všech prvků v řadě je vždy mocninou 2.
- Diagonální součet prvků řádků generuje Fibonacciho posloupnost.
Shrnutí
- Pascalův trojúhelník udává koeficienty pro binomické expanze.
- Každá řada Pascalova trojúhelníku začíná a končí „1“. Mezihodnoty jsou součtem dvou prvků předchozího řádku.
- Diagonální přidání všech prvků v Pascalově trojúhelníku vám dá Fibonacciho sekvence.
- Pascalův trojúhelník lze také generovat pomocí binomických koeficientů.