Pascalův trojúhelník – vzorec, vzory a příklady

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“.

Pascalův trojúhelník

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ů.

Konstrukce Pascalova trojúhelníku

Krok 2) Druhý prvek pro třetí řádek je součtem prvního a druhého čísla ve druhém řádku.

Konstrukce Pascalova trojúhelníku

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:

Konstrukce Pascalova trojúhelníku

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ů.

Konstrukce Pascalova trojúhelníku

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

Pascalův trojúhelníkový vzorec - binomický koeficient

"!" 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:

Sestavení Pascalova trojúhelníku výpočtem binomického koeficientu

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.

Fakta o Pascalově trojúhelníku

  • Diagonální součet prvků řádků generuje Fibonacciho posloupnost.

Fakta o Pascalově trojúhelníku

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ů.