Coefficienti binomiali e loro proprietà

Premessa

Per quel che riguarda la struttura di dati, abbiamo fin'ora visto alcuni esempi con array, e le liste. Dove anch'esse hanno come gli  array indici automaticamente associati alle celle, solo che le liste sono migliori in quanto di consentono di lavorare molto più facilmente e di ridurre il rischio di fare meno errori. Adesso il nostro scopo è di utilizzare le sorted list che è una struttura di dati molto simile ad una dictionary. Nel senso che è  una lista di chiavi valore, cioè coppie di chiavi valore. Ed è anche indicizzata come una lista, queste celle sono assegnati le posizioni dalla zero  alla count -1. Per fare  un esempio che abbia qualche significato statistico della sorted list, sia utile calcolare le probabilità della distribuzione binomiale o della distribuzione ipergeometrica. Perché ci consentono di avere un esempio significativo di utilizzo della sorted list per immagazzinare una distribuzione statistica.

Coefficiente binomiale 
Introduciamo le combinazioni perché ci serviranno per introdurre il concetto di coefficiente binomiale. Qual'è la differenza tra permutazioni e combinazioni? Noi consideriamo diverse due permutazioni, se differiscono, anche per l'ordine. Invece per quanto riguarda le combinazioni, due configurazioni che hanno gli stessi elementi sarebbero uguali anche se avessero segno diverso.

1) Permutazioni → fanno riferimento agli elementi e all'ordine
2) Combinazioni → fanno riferimento agli elementi non all'ordine.

Il significato della formula qui sopra posta, sta ad identificare  la combinazione di n oggetti su k posti. L'ultima formula dell'uguaglianza è la formula esplicita del coefficiente binomiale. Si chiamano coefficienti binomiali proprio perché sono stati studiati nell'ambito dello studio delle potenze del binomio.

Cioè tra gli n fattori ne prendiamo k, stiamo parlando delle combinazioni di n elementi su k posti. La combinazione  è il fattore di replicazione di a^k. I coefficienti sono ottenuti attraverso  il triangolo di tartaglia:

Esiste una relazione di ricorrenza tra i coefficienti binomiali che fa in modo che ci possiamo calcolare i coefficienti in modo semplice:

Questa relazione di ricorrenza che giustifica la struttura del triangolo d tartaglia, ci interessano perché le utilizzeremo per le nostre applicazioni. Ora vogliamo trovare altre due relazioni che ci leghino a questi due coefficiente. Partendo dal fattoriale tronco tirando fuori l'n iniziale  per il primo elemento, invece per  il secondo abbiamo estratto il termine  del fattoriale tronco di coda. Abbiamo scorporato il primo e l'ultimo termine del fattoriale tronco. 

Tutto ciò ci è servito ai fini computazionali  per l'implementazione di algoritmi efficienti per il calcolo di  probabilità.