Coefficienti multinomiali

Generalizza in maniera naturale il Coefficiente binomiale: Consideriamo la potenza $n$ -esima del polinomio:

(x_{1} + x_{2} + \dots + x_{k})^{n} = \sum z_{1} z_{2} \dots z_{n} z_{i} \in {x_{1}, \dots, x_{k}}

è una somma di tutte le stringhe lunghe $n$ di elementi scelti tra le $x_{i}$ . Se una data stringa $z = z_{1} \dots z_{n}$ ha $r_{i}$ occorrenze di $x_{i}$ , la somma $\sum_{i} r_{i} = n$ . Se le variabili commuatano, allora la stringa si può scrivere come:

z = x_{1}^{r_{1}} x_{2}^{r_{2}} \dots x_{k}^{r_{k}}

il coefficiente multinomiale $(r _{1} \dots r _{k} n)$ sarà il numero di occorrenze di queste stringhe.

(x_{1} + x_{2} + \dots + x_{k})^{n} = r_{1}, \dots r_{k} \sum r_{i} = n \sum (r _{1} \dots r _{k} n) x_{1}^{r_{1}} x_{2}^{r_{2}} \dots x_{k}^{r_{k}}

Osservazione Una $k$ -partizione ordinata di $[n]$ è una tupla di insiemi $(A_{1}, \dots, A_{k})$ disgiunti che uniti danno $[n]$ . Se fisso le cardinalità degli insiemi $∣ A_{i} ∣ = r_{i}$ , è chiaro che c’è una corrispondenza biunivoca tra le $k$ -partizioni con cardinalità $r_{1}, \dots r_{k}$ e le stringhe sopra menzionate.

un’altra caratterizzazione del coefficiente multinomiale è il numero di partizioni di $[n]$ in $k$ sottoinsiemi (ordinati) con cardinalità fissata $r_{1}, \dots, r_{k}$

Vediamo concretamente:

alfabeto $= {1, 2, 3, 4}$ $k = 4$ stringhe $z = 114432$ $n = 6$

voglio trovare una biiezione tra $z \mapsto (A_{1}, A_{2}, A_{3}, A_{4})$ il carattere $1$ ha due occorrenze, $4$ ne ha due, $3$ e $2$ ne hanno una. Il carattere $1$ corrisponde all’insieme $A_{1}$ , e le posizioni in cui compare $1$ sono gli elementi di $[n]$ che appartengono ad $A_{1}$ . Nel nostro caso:

114432 \mapsto ({1, 2}, {6}, {5}, {3, 4})

è chiaro che è una biiezione.

Se consideriamo una funzione $f : [n] \mapsto [k]$ , con $k \leq n$ , è chiaro che le preimmagini formano una partizione, e ugualmente ogni $k$ -partizione induce una funzione $g : [n] \mapsto [k]$ , se $x \in A_{i}$ allora $g (x) = i$ .

Quindi il coefficiente multinomiale è il numero di funzioni da $[n]$ in $[k]$ con fibre $f^{- 1} (i)$ di cardinalità fissata $r_{1}, \dots, r_{k}$ .

Come per il coefficente binomiale il ruolo delle $r_{i}$ è simmetrico.

Relazione di ricorrenza

Prima di dimostrarla algebricamente, esiste una semplice regola di addizione, una relazione di ricorrenza. Supponiamo di avere $m$ scatole ed $n$ oggetti da distribuire. Sia $α \in [n]$ un particolare oggetto. Se lo mettiamo nella prima scatola, per i rimanenti oggetti abbiamo:

(r _{1} - 1 , r _{2} , \dots , r _{m} n - 1)

in maniera simili, se mettiamo $α$ nella seconda scatola dovremmo diminuire $r_{2}$ di uno. Siccome possiamo partizionare tutti i possibili assegnamenti in base a dove contengono l’elemento $α$ , la cardinalità di tutti gli assegnamenti sarà la somma. $□$

Algebricamente:

(x_{1} + x_{2} + \dots + x_{k})^{n} = (x_{1} + x_{2} + \dots + x_{k})^{n - 1} (x_{1} + x_{2} + \dots + x_{k})

= (s_{1}, \dots s_{k}) \sum s_{i} = n - 1 \sum (s _{1} \dots s _{k} n - 1) x_{1}^{s_{1}} \dots x_{k}^{s_{k}} (x_{1} + x_{2} \dots + x_{k})

= j = 1 \sum k (s_{1}, \dots s_{k}) \sum s_{i} = n - 1 \sum (s _{1} \dots s _{k} n - 1) x_{1}^{s_{1}} \dots x_{j}^{s_{j} + 1} \dots x_{k}^{s_{k}}

adesso se $i \neq = j$ poniamo $r_{i} := s_{i}$ mentre se $i = j$ $r_{i} := s_{i} + 1$ . (quindi la somma $\sum r_{i} = n$ )

= (r_{1}, \dots r_{k}) \sum r_{i} = n \sum j = 1 \sum k (r _{1} \dots r _{j} - 1 \dots r _{k} n - 1) x_{1}^{r_{1}} \dots x_{j}^{r_{j}} \dots x_{k}^{r_{k}}

confrontando otteniamo la seguente relazione:

(r _{1} \dots r _{k} n) = j = 1 \sum k (r _{i} \dots r _{j} - 1 \dots r _{k} n - 1)

Forma algebrica

Dati interi non negativi $r_{1}, \dots r_{k}$ tali che $\sum_{i} r_{i} = n$ , abbiamo:

(r _{1} \dots r _{k} n) = \frac{n !}{r _{1} ! \dots r _{k} !}

Dim

Ricostruiamola a partire dal coefficiente binomiale, per cui abbiamo una forma algebrica. Usiamo la caratterizzazione come funzioni con cardinalità delle fibre fissate. Possiamo scegliere la controimmagine di $1$ in $(r _{1} n)$ modi diversi. Poi restano $n - r_{1}$ elementi per scegliere la preimmagine di $2$ , quindi $(r _{2} n - r _{1})$ e così via. In totale:

(r _{1} n) (r _{2} n - r _{1}) \dots (r _{k} r _{k})

sostituendo la formula algebrica del binomiale:

\frac{n !}{r _{1} ! ( n - r _{1} )!} \frac{( n - r _{1} )!}{r _{2} ! ( n - r _{1} - r _{2} )!} \dots

dopo le cancellazzioni:

\frac{n !}{r _{1} ! r _{2} ! \dots r _{k} !}

$□$

Lorenzo Gregoris

Explorer

Coefficienti multinomiali

Coefficienti multinomiali

Relazione di ricorrenza

Forma algebrica

Dim

Graph View

Table of Contents

Backlinks

Lorenzo Gregoris

Explorer

Coefficienti multinomiali

Coefficienti multinomiali §

Relazione di ricorrenza §

Forma algebrica §

Dim §

Graph View

Table of Contents

Backlinks

Coefficienti multinomiali

Relazione di ricorrenza

Forma algebrica

Dim