Coefficiente binomiale simmetrico

Da Wikipedia, l'enciclopedia libera.

Con il termine Coefficiente binomiale simmetrico denotiamo una funzione di due variabili intere del tipo

$\mbox{cbins} ~:~ \mathbb{N}\times\mathbb{N} \mapsto \mathbb{N}$

la quale è simmetrica nei suoi due argomenti e costituisce una variante della funzione che esprime i coefficienti binomiali. La funzione cbins si può definire in modo naturale e significativo come funzione che enumera alcuni tipi di configurazioni discrete equivalenti: in particolare i cammini sui quali basiamo la definizione possono essere visualizzati semplicemente e questa visualizzazione permette di giungere a molti risultati con procedimenti trasparenti, riducendo al minimo le manipolazioni formali. Questa funzione consente di introdurre l'importante nozione di coefficiente binomiale nel modo probabilmente più semplice.

Indice

1 Definizione
2 Prime proprietà
3 Cammini binomiali, sequenze binarie e sottoinsiemi
4 Collegamento con i coefficienti binomiali usuali
5 Collegamento con i numeri di Fibonacci
6 Formula del binomio

[modifica] Definizione

Consideriamo il cosiddetto piano combinatorio o piano ZZ, l'insieme dei punti del piano cartesiano aventi entrambe le coordinate intere. Per un punto di questo insieme usiamo come notazione tipica la $\langle h,k\rangle$ , con h e k numeri interi. Relativamente al piano combinatorio diciamo passo WE o passo verso destra in tale piano ogni segmento orientato avente come estremità due punti della forma $\langle h,k\rangle$ e $\langle h+1,k\rangle$ ; diciamo passo SN o passo verso l'alto ogni segmento orientato avente come estremità due punti della forma $\langle h,k\rangle$ e $\langle h,k+1\rangle$ . Diciamo inoltre cammino ascendente ogni cammino costituito da una sequenza di passi WE e SN consecutivi. Ogni cammino ascendente può essere visualizzato in modo molto evidente.

Si vogliono considerare in particolare quelli che chiamiamo cammini binomiali, cioè i cammini ascendenti che iniziano nell'origine $\langle 0,0\rangle$ ; loro estremità finali possono essere tutti i punti $\langle h,k\rangle \in \mathbb{N}\times\mathbb{N}$ costituenti il primo quadrante del piano ZZ. Evidentemente la corrispondenza fra cammini binomiali e coppie di interi naturali è biunivoca: in altri termini le coppie di interi naturali costituiscono una codifica fedele dei suddetti cammini.

Definiamo dunque come coefficiente binomiale simmetrico relativo ai valori interi naturali h e k e denotiamo con $~\mbox{cbins}(h,k)~$ il numero dei cammini binomiali che iniziano nell'origine e terminano nel punto $\langle h,k\rangle$ .

[modifica] Prime proprietà

Dalla definizione si ricavano facilmente e in modo naturale varie proprietà dei coefficienti binomiali simmetrici.

$\mbox{cbins}(h,k)=\mbox{cbins}(k,h) \qquad \mbox{(simmetria)}$

Questa uguaglianza deriva dal fatto che la riflessione del piano combinatorio rispetto alla diagonale h=k implica una biiezione fra i cammini binomiali che terminano in $\langle h,k\rangle$ e quelli che terminano in $\langle k,h\rangle$ . Di conseguenza il numero dei cammini del primo di questi insiemi è uguale al numero dei cammini del secondo.

$\mbox{cbins}(h,0)=\mbox{cbins}(0,h)=1 \qquad \mbox{(condizioni al contorno)}$

I cammini binomiali che terminano in un punto $\langle h,0\rangle$ dell'asse orizzontale si riducono ad un solo cammino, quello costituito da h passi WE.

$\mbox{cbins}(h,1)\,=\,\mbox{cbins}(1,h)=h+1$

La collezione dei cammini binomiali che terminano in un punto $\langle h,1\rangle$ della linea orizzontale y=1 comprende cammini di h+1 passi uno solo dei quali è un passo SN; comprende quindi h+1 cammini.

$\mbox{cbins}(h,2) \,=\, \mbox{cbins}(2,h) = {(h+2)(h+1)\over 2}$

La collezione dei cammini binomiali che terminano in un punto $\langle h,2\rangle$ della linea orizzontale y=2 è data dall'insieme dei cammini di h+2 passi due dei quali sono passi SN, i restanti passi WE; dato che il primo dei due passi SN si può incontrare in una qualsiasi delle prime h+1 posizioni (chiamiamola posizione j) e il secondo in una qualsiasi delle restanti h+2-j posizioni, il loro numero è uguale a $(h + 1) + h + (h - 1)... + 2 + 1$ , cioè a (h+2)(h+1)/2.

$\mbox{cbins}(h+1,k+1) \,=\, \mbox{cbins}(h,k+1) + \mbox{cbins}(h+1,k) \qquad \mbox{(additivita)}$

Ogni cammino binomiale che termina in $\langle h+1,k+1\rangle$ deve passare per uno (solo) dei due punti $\langle h,k+1\rangle$ e $\langle h+1,k\rangle$ ; quindi il numero dei cammini binomiali che terminano nel punto $T=\langle h+1,k+1\rangle$ è dato dalla somma del numero dei cammini binomiali che terminano nel punto $\langle h,k+1\rangle$ immediatamente a sinistra di T e del numero dei cammini binomiali che terminano nel punto $\langle h+1,k\rangle$ immediatamente al di sotto di T. Questo fatto, oltre a quello ottenibile per simmetria, è precisamente quello che esprime l'enunciato.

Dalle uguaglianze esprimenti le condizioni al contorno e l'additività segue un procedimento per individuare effettivamente i valori della funzione che porta a una tabella come la seguente

$\begin{matrix} \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \\ 1 & 8 & 36 & 120 & 330 & 792 & 1716 & 3432 & \cdots \\ 1 & 7 & 28 & 84 & 210 & 462 & 924 & 1716 & \cdots \\ 1 & 6 & 21 & 56 & 126 & 252 & 462 & 792 & \cdots \\ 1 & 5 & 15 & 35 & 70 & 126 & 210 & 330 & \cdots \\ 1 & 4 & 10 & 20 & 35 & 56 & 84 & 120 & \cdots \\ 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & \cdots \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \cdots \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 &\cdots \\ \end{matrix}$

Si tratta di una porzione di una matrice con righe e colonne individuate dai numeri naturali che troveremo equivalente al triangolo di Tartaglia.

[modifica] Cammini binomiali, sequenze binarie e sottoinsiemi

Ogni cammino binomiale che termina in $\langle h,k\rangle$ si può rappresentare con una sequenza binaria di lunghezza h+k e di peso h, cioè con una sequenza di bits (cifre uguali a 0 o 1) comprendente h bits uguali ad 1 (e k bits uguali a 0). In effetti fra i suddetti cammini binomiali e queste sequenze binarie sussiste criptomorfismo: questi due tipi di entità sono logicamente del tutto equivalenti. Quindi i coefficienti binomiali simmetrici si possono interpretare come numeri di sequenze binarie di data lunghezza e di dato peso.

Consideriamo ora un generico insieme esplicito A, cioè un insieme finito individuato da un elenco (o lista) E dei suoi elementi; si osserva che questo elenco stabilisce un ordine sequenziale fra gli elementi di A. Ogni sottoinsieme S di A si può individuare con un sottoelenco di E, cioè con un elenco ottenuto da E eliminando gli elementi di A non appartenenti ad S. Denotiamo poi con h = |S| il numero di elementi del sottoinsieme, con n = |U| la cardinalità dell'intero A, che può essere conveniente chiamare insieme ambiente, e con k il numero degli elementi del complementare di S in U (si è dunque posto k := n - h).

Il sottoinsieme S, invece che con il sottoelenco suddetto, si può individuare con la sequenza binaria di lunghezza n=h+k e di peso h ottenuta facendo riferimento ad E e scegliendo per i=1,2,...,n come bit nella posizione i-esima 0 o 1 secondo che l'elemento nella posizione i di E non appartiene oppure appartiene al sottoinsieme da individuare. Osserviamo che questa sequenza binaria costituisce una rappresentazione della funzione indicatrice del sottoinsieme S di U; precisamente la rappresentazione relativa alla sequenzializzazione di U fornita dall'elenco E.

A questo punto risulta individuata una applicazione significativa dei cammini binomiali terminanti in $\langle h,n-h\rangle$ : ciascuno di essi consente di individuare biunivocamente un sottoinsieme S di h elementi di un insieme A di n elementi (n = h, h+1, ...) riferendosi ad un elenco esplicito E degli elementi dell'ambiente. Si osserva che un cammino binomiale di lunghezza n potrebbe servire per descrivere visivamente un processo consistente nello scorrere l'elenco E degli elementi di A per decidere per ciascuno di essi se va incluso o meno in un sottoinsieme S che si vuole costituito da elementi da privilegiare in quanto soddisfano una qualche condizione, ovvero che si devono evidenziare per un qualche motivo.

Risulta inoltre disponibile un'altra interpretazione dei cooefficienti binomiali simmetrici, forse la più rilevante: $cbins(h, k)$ fornisce il numero dei sottoinsiemi con h elementi di un insieme di cardinalità h+k.

Si osserva anche che ogni sottoelenco che fornisce un sottoinsieme S di h elementi di un ambiente A di h+k elementi dato mediante un elenco esplicito non è che una combinazione senza ripetizioni di h degli h+k contrassegni degli elementi di S. Quindi $cbins(h, k)$ fornisce anche il numero delle combinazioni senza ripetizioni di lunghezza h formate servendosi di h+k elementi.

Per il numero di queste sequenze si trova che è dato dal numero delle disposizioni di h+k oggetti di lunghezza h diviso per h!; quindi

$\mbox{cbins}(h,k) = {(h+k)! \over h! k!}$

[modifica] Collegamento con i coefficienti binomiali usuali

Diamo ora le semplici uguaglianze di collegamento fra coefficienti binomiali simmetrici e coefficienti binomiali individuati con la notazione di Albert von Ettinghausen.

${n \choose h} = \mbox{cbins}(h,n-h) \qquad\qquad \mbox{cbins}(h,k) = {h+k \choose h}$

A questo punto può essere utile riscrivere per i coefficienti binomiali usuali i risultati trovati in precedenza; è inoltre utile esplicitare loro interpretazioni in termini insiemistici.

La tavola numerica precedente viene riferita ai due assi delle variabili h e k; i punti che corrispondono ai sottoinsiemi di un ambiente di n = h + k elementi relativi a diversi valori di h e k = n - h si trovano allineati sulla linea di equazione cartesiana x+y=n. Per ottenere i valori dei coefficienti binomiali riferiti agli assi delle variabili n e h (o k) basta modificare la tabella precedente facendo slittare la seconda linea dal basso, relativa a k=1, di una posizione a destra, la linea relativa a k=2 di due posizioni e così via. Si ottiene quindi la tabella triangolare

$\begin{matrix} & & & & & & & & 1 & \cdots \\ & & & & & & & 1 & 8 & \cdots \\ & & & & & & 1 & 7 & 28 & \cdots \\ & & & & & 1 & 6 & 21 & 56 & \cdots \\ & & & & 1 & 5 & 15 & 35 & 70 & \cdots \\ & & & 1 & 4 & 10 & 20 & 35 & 56 & \cdots \\ & & 1 & 3 & 6 & 10 & 15 & 21 & 28 & \cdots \\ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \cdots \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ \end{matrix}$

In questo quadro non è difficile individuare una variante nel solo aspetto del triangolo di Tartaglia, ottenibile con una sorta di rotazione della suddetta tabella.

Sommando i valori che si trovano nelle successive colonne si ottiene la successione delle potenze di 2: 1, 2, 4, 8, 16, 32, 64, 128, 256, ... . In effetti gli interi positivi nella colonna relativa a un dato valore di n forniscono i numeri dei sottoinsiemi di un ambiente di n elementi aventi rispettivamente h = 0, 1, 2, ..., n=1, n elementi. La somma di queste cardinalità fornisce il numero complessivo dei sottoinsiemi di un ambiente di n elementi: questo coincide con il numero delle sequenze binarie di lunghezza n che come abbiamo visto corrispondono biunivocamente ai suddetti sottoinsiemi (sono le rispettive funzioni indicatrici) e tale numero è chiaramente pari a $\,2^n\,$ (coincide con il numero delle disposizioni con ripetizione di lunghezza n di 2 oggetti).

Risulta quindi dimostrata la seguente formula di sommazione per i coefficienti binomiali:

$\sum_{h=0}^n {n \choose h} = 2^n$

Questa identità si può anche ricavare come caso particolare dello sviluppo del binomio di Newton formula che vedremo più avanti ma che esprime un fatto più complesso del precedente.

Conviene osservare che questa formula di sommazione per un dato n corrisponde alla distribuzione dei nodi del reticolo booleano dei sottoinsiemi di un ambiente di n elementi sui diversi livelli (ranghi) di tale reticolo graduato (per il punto di vista probabilistico della formula precedente vedi distribuzione binomiale).

[modifica] Collegamento con i numeri di Fibonacci

Consideriamo ora i raggruppamenti dei valori dei coefficienti binomiali forniti dalla tabella precedente che corrispondono ai punti su ciascuna delle rette oblique individuate dalle equazioni y = -x + n per n = 0, 1, 2, ... . Il raggruppamento relativo a un dato n contiene $\left\lfloor {n\over 2}\right\rfloor +1$ elementi e per la successione delle somme si trovano i valori

$1,\; 1,\; 2,\; 3,\; 5,\; 8,\; 13,\; 21,\; 34,\; 55,\; ...$

Questa è la successione dei numeri di Fibonacci, successione definita richiedendo

$\,F_0:=F_1:=1, \quad F_n:=F_{n-1}+F_{n-2} \quad \mbox{per } n=2, 3, ...$ .

Questo fatto si dimostra considerando che la proprietà di additività comporta che ciascuno dei valori del raggruppamento relativo a n è ottenuto da uno dei valori dei due raggruppamenti immediatamente precedenti o dalla somma di due di tali valori.