Teorema multinomial

De Viquipèdia
Dreceres ràpides: navegació, cerca

En matemàtiques, el teorema multinomial és una expressió d'una potència d'una suma en termes de potències dels sumands. Per qualsevol enter positiu m i qualsevol enter no negatiu n, la fórmula multinomial és

(x_1 + x_2 + \cdots + x_m)^n 
 = \sum_{k_1,k_2,\ldots,k_m} {n \choose k_1, k_2, \ldots, k_m}
 x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}.

El sumatori es realitza en totes les seqüències dels índexs enters no negatius k1 a km tals que \sum_{i=1}^m {k_i} = n. Igual que en el teorema binomial, les quantitats de la forma 00 que apareixen es consideren iguals a 1.

Els nombres

 {n \choose k_1, k_2, \ldots, k_m}
 = \frac{n!}{k_1!\, k_2! \cdots k_m!}
 = {k_1\choose k_1}{k_1+k_2\choose k_2}\cdots{k_1+k_2+\cdots+k_m\choose k_m} 
 = \prod_{i=1}^m {\sum_{j=1}^i k_j \choose k_i}

són els coeficients multinomials.

Els coeficients multinomials tenen una interpretació directa en combinatòria, com el nombre de formes de posar n objectes diferents en m capses, amb k1 objectes a la primera capsa, k2 objectes a la segona capsa, etcètera.

A més, el coeficient multinomial és també el nombre de formes diferents de permutar un conjunt de n elements, sent ki el nombre de cops que es repeteix cada un dels diferents elements. Per exemple, el nombre de permutacions diferents de les lletres de la paraula ARRANJAR, que té 3 As, 3 Rs, 1 N, i 1 J és

{8 \choose 3, 3, 1, 1} = \frac{8!}{3!\, 3!\, 1!\, 1!} = 1120

El teorema binomial és un cas especial, per m = 2, del teorema multinomial.

Demostració[modifica | modifica el codi]

Aquesta demostració del teorema multinomial usa el teorema binomial i el teorema d'inducció en m.

Pel pas inicial (m = 1), els dos costats valen x_1^n.

Pel pas inductiu, suposa el teorema multinomial per m. Llavors

(x_1+x_2+\cdots+x_m+x_{m+1})^n =
= (x_1+x_2+\cdots+(x_m+x_{m+1}))^n =
= \sum_{k_1,k_2,\cdots,k_{m-1},K}{n\choose k_1,k_2,\ldots,k_{m-1},K} x_1^{k_1}x_2^{k_2}\cdots x_{m-1}^{k_{m-1}}(x_m+x_{m+1})^K =

per la hipòtesi d'inducció, sent K = k_m+k_{m+1}.

Aplicant el teorema binomial a l'últim factor,

= \sum_{k_1,k_2,\cdots,k_{m-1},K}{n\choose k_1,k_2,\ldots,k_{m-1},K} x_1^{k_1}x_2^{k_2}\cdots x_{m-1}^{k_{m-1}}\sum_{k_m,k_{m+1}}{K\choose k_m,k_{m+1}}x_m^{k_m}x_{m+1}^{k_{m+1}} =
= \sum_{k_1,k_2,\cdots,k_{m-1},k_m,k_{m+1}}{n\choose k_1,k_2,\ldots,k_{m-1},k_m,k_{m+1}} x_1^{k_1}x_2^{k_2}\cdots x_{m-1}^{k_{m-1}}x_m^{k_m}x_{m+1}^{k_{m+1}}

que completa la inducció.

L'últim pas se segueix de

{n\choose k_1,k_2,\ldots,k_{m-1},K}{K\choose k_m,k_{m+1}} = {n\choose k_1,k_2,\ldots,k_{m-1},k_m,k_{m+1}},

com es pot veure escrivint els tres coeficients usant factorials:

 \frac{n!}{k_1! k_2! \cdots k_{m-1}!K!} \frac{K!}{k_m! k_{m+1}!}=\frac{n!}{k_1! k_2! \cdots k_{m+1}!}