Triàngul trinomial

En matemàtiques, es definix a un triàngul trinomial com una variant del triàngul de Pascal sent l'única diferència que en el triàngul trinomial és generat en la suma de les tres entrades adjacents de l'anterior fila a diferència del triàngul de Pascal que són dos. Té aplicacions relacionades en la combinatòria i els números triangulars.

$\begin{array}{ccccccc}& & & & & & 1\\ & & & & & 1& 1& 1\\ & & & & 1& 2& 3& 2& 1\\ & & & 1& 3& 6& 7& 6& 3& 1\\ & & 1& 4& 10& 16& 19& 16& 10& 4& 1\\ & 1& 5& 15& 30& 45& 51& 45& 30& 15& 5& 1\end{array}$

Triàngul trinomial primeres 6 files.

El coeficient de la fila n i entrada k es definiria de la següent manera:

${(\genfrac{}{}{0ex}{}{n}{k})}_2$

Les files s'escomencen a contar en 0 i les entrades en -n, tenint 2n + 1 elements cada fila.

Propietats

Complix esta propietat:

${(\genfrac{}{}{0ex}{}{n}{k})}_2={(\genfrac{}{}{0ex}{}{n}{-k})}_2$

I ademés complix:

$\sum _{k=-n}^n{(\genfrac{}{}{0ex}{}{n}{k})}_2=3^n$

Els coeficients de la n-fila coincidirien en l'expansió de $(1+x+x^2{)}^n$.

$(1+x+x^2{)}^n=\sum _{k=-n}^n{(\genfrac{}{}{0ex}{}{n}{k})}_2{x}^{n-k}$

Càlcul de les entrades del triàngul trinomial

Fòrmula directa

${(\genfrac{}{}{0ex}{}{n}{k})}_2=\sum _{i=0}^n(-1{)}^i(\genfrac{}{}{0ex}{}{n}{i})(\genfrac{}{}{0ex}{}{2(n-i)}{n-k-i})$

Recursiva

${(\genfrac{}{}{0ex}{}{n}{k})}_2=\{\begin{array}{c}1,sin,k=0\\ 0,si|k|>n\\ {(\genfrac{}{}{0ex}{}{n-1}{k-1})}_2+{(\genfrac{}{}{0ex}{}{n-1}{k})}_2+{(\genfrac{}{}{0ex}{}{n-1}{k+1})}_2,sino\end{array}$

Pseudocódigo usant recursión:

sancer TrianguloTrinomial(entere n,entere k){
    si(n == 0 i k == 0) tornar 1;
    si(valorAbsoluto(k) > n) tornar 0;
    tornar TrianguloTrinomial(n-1,k-1)+TrianguloTrinomial(n-1,k)+TrianguloTrinomial(n-1,k+1);
}

Ya que hi ha varis resultats iguals que es calculen vàries voltes és aconsellable usar programació dinàmica:

sancer matrix[n+1][k];
inicializar tots elements matrix a -1;
sancer TrianguloTrinomial(entere n,entere k){
    si(n == 0 i k == 0) tornar 1;
    si(valorAbsoluto(k) > n) tornar 0;
    si(matrix[n][valorAbsoluto(k)] == -1) matrix[n][valorAbsoluto(k)] = TrianguloTrinomial(n-1,k-1)+TrianguloTrinomial(n-1,k)+TrianguloTrinomial(n-1,k+1)
    tornar matrix[n][valorAbsoluto(k)];
}

Aprofitant-nos de les propietats del triàngul trinomial podem reduir el número de valors almagasenats en la memòria agarrant el valor absolut de k. Ya que la fòrmula directa pot implicar calcular factorials molt grans pot ser més adequada utilisar esta fòrmula.