Triângulo de Pascal – Fórmula, Padrões e Exemplos
Sarah Chen
O que é o Triângulo de Pascal?
O Triângulo de Pascal é uma matriz triangular de números seguida por um padrão específico e conexão com a linha anterior. Foi inventado por Blaise Pascal. Este triângulo começa com um elemento na primeira linha. Depois disso, cada linha começa e termina com “1”.
História do Triângulo de Pascal
O livro chinês “Os Nove Capítulos da Arte Matemática” contém um dos primeiros exemplos do Triângulo de Pascal. Além disso, contém alguns dos mesmos padrões e qualidades encontrados nos triângulos atuais.
Pascal foi uma das várias pessoas na Europa que estudou o triângulo. Outros matemáticos examinaram matrizes triangulares de números semelhantes antes dele.
Construção do Triângulo de Pascal
Construir o Triângulo de Pascal é simples. A única coisa que você precisa lembrar é que a linha começa e termina com 1. A regra para o restante dos números é a seguinte:
Para qualquer linha re coluna c, o número será a soma das colunas c-1 e c da linha r-1.
Aqui,
- r = 3,4,5….
- n e c = 2,3,4,…r-1.
Aqui estão as etapas para construir o Triângulo de Pascal:
Passo 1) Vamos começar preenchendo duas linhas.
Passo 2) O segundo elemento da terceira linha é a soma do primeiro e do segundo números da segunda linha.
Passo 3) A quarta linha começará com “1.”. O segundo número é 3, que é a soma de 1 e 2 (destacado em azul).
A imagem abaixo mostra como preencher a quarta linha:
Passo 4) A quinta linha consistirá de cinco números. Já conhecemos o padrão para preencher as linhas das etapas anteriores.
Fórmula do Triângulo de Pascal – Coeficiente Binomial
Um coeficiente binomial é um número que expressa diferentes métodos para selecionar um subconjunto de k elementos de uma coleção de n elementos. Freqüentemente, é escrito como “C(n,k)” ou “n escolha k”.
O coeficiente binomial é definido como
O "!" denota o “fatorial”.
não! = n.(n-1). (n-2)…3.2.1
Por exemplo, nos
5! = 5.4.3.2.1
= 120
Então, digamos C(5,3) ou 5 escolha 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
Método 1: Construindo o Triângulo de Pascal pela linha anterior
As etapas deste procedimento são as mesmas do triângulo de Pascal. Digamos que queremos criar um triângulo de Pascal com até sete linhas.
Os passos para realizá-lo são os seguintes:
Passo 1) Comece a linha superior com “1”.
Passo 2) Para a linha “r”, o item “c” será o produto de “c-1” e “c” o número da linha “r-1”.
Passo 3) O primeiro e o último número consecutivo serão sempre “1”.
Devemos seguir estes três passos fáceis para criar o triângulo de Pascal.
C++ Código do Triângulo de Pascal pela Linha Anterior
#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);
}
Saída:
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 Código da fórmula do triângulo de Pascal pela linha anterior
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)
Resultado do exemplo do triângulo de 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
Análise de Complexidade
A matriz bidimensional foi usado na implementação. Dado que N é o número de linhas do triângulo de Pascal. Isso exigirá N2 espaços unitários. Portanto, O será a complexidade do espaço (N2).
Temos dois loops na função e cada loop é executado “N” vezes. Portanto, a complexidade do tempo também é SOBRE2) ou complexidade de tempo ao quadrado.
Método 2: Construindo o Triângulo de Pascal calculando o coeficiente binomial
Podemos simplesmente derivar os números do triângulo de Pascal usando o coeficiente binomial. Aqui está o diagrama:
Aqui estão as etapas para construir o Triângulo de Pascal calculando o Binomial:
Passo 1) A linha superior será C(0,0). Usando a fórmula acima para o Coeficiente Binomial, C(0,0) = 1. Porque 0! = 1.
Passo 2) Para a linha “i”, haverá um total de elementos “i”. Cada item será calculado C(n,r) onde n será i-1.
Passo 3) Repita a etapa 2 para o número de linhas desejadas para o triângulo de Pascal.
C++ Codifique o Triângulo de Pascal por Coeficiente Binomial
#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);
}
Saída:
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 Codifique o Triângulo de Pascal por Coeficiente Binomial
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)
Resultado do exemplo do triângulo de 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
Análise de Complexidade
Três loops foram usados na implementação. Um loop serve para calcular o coeficiente binomial e os outros dois servem para criar números para todas as linhas. Quanto ao número de linhas, temos três loops que executam “n” vezes. Consequentemente, a complexidade geral do tempo será 0(n3).
A complexidade do espaço agora é constante porque não mantemos nenhum dado armazenado. O programa calcula o elemento e ele é impresso em uma linha. A complexidade do espaço então diminui para 0(1).
Método 3: Construindo o Triângulo de Pascal por Coeficiente Binomial Modificado
Na técnica anterior, já vimos como utilizar um coeficiente binomial para calcular cada elemento do triângulo de Pascal. Esta abordagem determinará C(n,r) a partir de C. (n, r-1). Isso simplificará as coisas em um pedido.
Aqui estão as etapas para construir o Triângulo de Pascal pelo Coeficiente Binomial Modificado:
Passo 1) Inicie a primeira linha com “1”
Passo 2) Calcule C(n,r), onde “n” é o número da linha e “r” é a coluna ou o elemento. Atribua o valor em uma variável C.
Passo 3) Para calcular C(n,k), será C*(nk)/k. Agora, atribua esse valor a C.
Passo 4) Continue o passo 3 até que “k” chegue ao final da linha. Após cada iteração, aumente o valor de K em um.
C++ Código para o Triângulo de Pascal por Coeficiente Binomial modificado
#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);
}
Saída:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python código para o Triângulo de Pascal por coeficiente binomial modificado
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)
Saída dos padrões triangulares de Pascal:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Análise de Complexidade
A implementação possui dois loops. Cada loop executa no máximo “n” tempo, onde “n” significa o número de linhas no triângulo pascal. Então, a complexidade do tempo é Sobre2), tempo ao quadrado.
Em relação à complexidade do espaço, não precisávamos de nenhum array para armazenar. Usamos apenas uma variável para manter o coeficiente binomial anterior. Então, só precisávamos de um espaço extra. A complexidade do espaço tornou-se O (1).
Aplicação do Triângulo de Pascal
Aqui estão algumas aplicações do Triângulo de Pascal:
Expansões binomiais: Podemos determinar o coeficiente das expansões binomiais do triângulo de Pascal. Aqui está um exemplo:
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2e + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3e + 6x2y2 + 4xy3 + 1y4 |
Calculando Combinações: Vimos que os elementos do triângulo de Pascal são equivalentes a coeficientes binomiais. Por exemplo, se você tem 6 bolas e foi solicitado a escolher 3 bolas, será 6C3. Ou você pode encontrar o número no 3º elemento da 6ª linha do triângulo de Pascal.
Fatos interessantes sobre o triângulo de Pascal
Aqui estão alguns fatos que você achará interessantes sobre o triângulo de Pascal:
- A soma de todos os elementos consecutivos é sempre a potência de 2.
- A soma diagonal dos elementos das linhas gera a sequência de Fibonacci.
Resumo
- O triângulo de Pascal fornece os coeficientes para as expansões binomiais.
- Cada linha do triângulo de Pascal começa e termina com “1”. Os valores intermediários são a soma de dois elementos da linha anterior.
- A adição diagonal de todos os elementos do triângulo de Pascal lhe dará a Seqüência Fibonacci.
- O triângulo de Pascal também pode ser gerado com coeficientes binomiais.
