Algoritmos para construir o triângulo de Pascal

O triângulo de Pascal é uma disposição ordenada dos números binomiais. E pela definição, dados dois números naturais n e p, com n maior ou igual a p, chamamos de número binomial o par de valores:

|n|
|p|

Onde lê-se binomial de n sobre p, sendo n o numerador e p o denominador, e o cálculo de seu valor pode ser feito pela fórmula:

n! / (n-p)!p!

Na disposição ordenada dos números binomiais, denominado triângulo de Pascal, obtêm-se a forma infinita:

|0|
|0|

|1|  |1|
|0|  |1|

|2|  |2|  |2|
|0|  |1|  |2|

|3|  |3|  |3|  |3|
|0|  |1|  |2|  |3|

|4|  |4|  |4|  |4|  |4|
|0|  |1|  |2|  |3|  |4|

...

E se no triângulo de Pascal substituirmos cada binomial pelo respectivo valor, obteremos os elementos:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...

A construção do triângulo de Pascal usando uma linguagem de programação de computadores pode ser feita com diversos algoritmos. Os apresentados aqui utilizam a própria fórmula da definição do número binomial ou as relações de Stiefel ou de Fermat.

Nos exemplos de códigos abaixo adotou-se uma matriz para armazenar os valores dos elementos e cada par Linha x Coluna referente aos índices na matriz corresponde respectivamente, de forma análoga, ao par n e p do número binomial.

Um algoritmo que utiliza a fórmula da definição pode ser algo como mostrado abaixo. Para cada elemento da matriz é utilizada a fórmula n! / (n-p)!p!:

for (L=0;L<=N-1;L++) {
    for (C=0;C<=L;C++) {
        matriz[L][C] = fatorial(L) / (fatorial(C) * fatorial(L-C));
    }
}

Apenas para ilustração, a função fatorial que complementa o algoritmo:

public static long fatorial(int num) {
    if (num <= 1) {
        return 1;
    } else {
        return num * fatorial(num-1);
    }
}

Os próximos três algoritmos utilizam a relação de Stiefel para calcular os valores dos elementos do triângulo de Pascal, onde:

|n|   | n |   |n+1|
|p| + |p+1| = |p+1|

Então, para aplicar esta relação fazemos o sentido inverso onde o valor de um elemento |n p| é igual a soma dos valores dos binômios em |n-1 p-1| e |n-1 p|.

Nesta primeira versão é feito um controle para o primeiro e o último elemento de cada linha receber 1, nos outros é realizada a soma:

for (L=0;L<=N-1;L++) {
    for (C=0;C<=L;C++) {
        if (C==0 || L==C) {
            matriz[L][C] = 1;
        } else {
            matriz[L][C] = matriz[L-1][C] + matriz[L-1][C-1];
        }
    }
}

Uma propriedade do triângulo de Pascal é que numa linha qualquer, dois binomiais equidistantes dos extremos são iguais. Sendo assim, para esta segunda versão é feito o controle para o primeiro elemento receber 1, até a metade faz a soma, e depois da metade repete-se os elementos anteriores em ordem inversa:

for (L=0;L<=N-1;L++) {
    for (C=0;C<=L;C++) {
        if (C==0) {
            matriz[L][C] = 1;
        } else if (C<=(L/2)) {
            matriz[L][C] = matriz[L-1][C] + matriz[L-1][C-1];
        } else {
            matriz[L][L-C] = matriz[L][C];
        }
    }
}

A terceira versão, que utiliza a relação de Stiefel, é uma forma recursiva onde usa uma função que retorna o valor de um binômio qualquer quando lhe é passada n e p como parâmetro:

for (L=0;L<=N-1;L++) {
    for (C=0;C<=L;C++) {
        matriz[L][C] = binomio(L,C);
    }
}

public static int binomio(int L, int C) {
    if (L==0 || C==0 || C==L) {
        return 1;
    } else {
        return binomio(L-1, C-1) + binomio(L-1, C);
    }
}

E nosso último algoritmo utiliza a relação de Fermat para calcular os valores dos elementos do triângulo de Pascal, onde:

|n|                 | n |
|p| * (n-p / p+1) = |p+1|

Da mesma forma, para aplicar esta relação fazemos o sentido inverso onde o valor de um elemento |n p| é igual a multiplicação do valor do binômio |n p-1| por (n-p+1)/p:

for (L=0;L<=N-1;L++) {
    matriz[L][0] = 1;
    for (C=1;C<=L;C++) {
        matriz[L][C] = matriz[L][C-1] * (L-C+1) / C;
    }
}

Apesar do triângulo de Pascal ser uma estrutura complexa com diversas propriedades e características capazes de relacioná-lo, por exemplo, com algumas sequências numéricas importantes, sua implementação na forma de um algoritmo para linguagem de programação é bastante simples, como foi visto neste artigo.

Obs: A notação no número binomial foi prejudicada neste artigo. O correto é utilizar um grande par de parênteses envolvendo os números n e p, mas aqui foi utilizado o caractere "|".