Coefficiente binomiale: definizioni, implementazione e utilizzo

introduzione

In statistica, i coefficienti binomiali sono usati principalmente insieme alle distribuzioni. Ma c'è di più in loro quando applicati agli algoritmi di calcolo. Sono ampiamente utilizzati nel campo dell'apprendimento automatico statistico e della programmazione dinamica. L'idea di base sui coefficienti binomiali deriva da una distribuzione binomiale. I coefficienti sono usati nel teorema del binomio, e da qui il nome.

In primo luogo, i coefficienti binomiali hanno due definizioni. Sono i seguenti:

1. Coefficienti binomiali per trovare combinazioni

I coefficienti binomiali vengono utilizzati per trovare il numero di modi per selezionare un certo numero di oggetti dal pool di oggetti fornito. Statisticamente, un coefficiente binomiale può aiutare a trovare il numero di modi in cui y oggetti possono essere selezionati da un totale di x oggetti. Il numero di sottoinsiemi di elementi y da x.

La formula è derivata come:

Per selezionare i sottoinsiemi di elementi y da x oggetti, il coefficiente binomiale o le combinazioni possibili sono xCy = x! / si! * (xy)!

Questo metodo potrebbe essere incredibilmente utile mentre devi capire il numero di combinazioni possibili da un grande pool di oggetti. Ma dove si applica?

Esempio

Immagina che ci sia una classe con 15 studenti. Se devi selezionare una squadra di 7 studenti per una competizione, devi capire le possibili combinazioni. Utilizzando la formula dei coefficienti binomiali , la risposta potrebbe essere calcolata facilmente.

Le combinazioni totali = 15! / 7! * (15-7)! = 15! / 7! * 8!

Molti altri casi sono molto più complicati, in cui vengono utilizzati coefficienti binomiali . Ad esempio, la scelta di un partito politico per le elezioni o, più specificamente, di un sindacato. Immagina che ci sia un disegno di legge da approvare e tu sei la frusta di maggioranza per il partito al governo. Devi decidere quali voti ci sono e quanti membri saranno necessari per votare il disegno di legge. I membri devono appartenere al governo così come al partito di opposizione. La combinatoria può essere applicata per trovare i membri a cui chiedere i voti.

Leggi Informazioni: 13 interessanti idee e argomenti per progetti sulla struttura dei dati per principianti

2. Coefficienti binomiali per la distribuzione

Questa definizione è più formale e statistica. Significa trovare i coefficienti di un'espansione polinomiale. In parole povere, il coefficiente binomiale C(a, b) può essere definito come il coefficiente di x^b nella forma distribuita di (x+1)^a.

Cerchiamo di capirlo con un esempio.

Esempio

Ad esempio, si desidera un'espansione polinomiale di (x+1)^2. Se lo confrontiamo con la nostra definizione, otteniamo a=2 e b=0,1,2.

Con il calcolo manuale sappiamo che l'espansione di (x+1)^2 = x^2 + 2x + 1. Ma come vengono calcolati questi coefficienti?

Applichiamo la formula:

Il coefficiente di x^0 = C(2,0)

Il coefficiente di x^1 = C(2,1)

Il coefficiente di x^2 = C(2,2)

Quindi, l'espansione può essere scritta come: C(2,0)x^0 + C(2,1)x^1 + C(2,2)x^2

La formula rimane la stessa. C(a,b) = a! / B! * (ab)!

Applicando qui la stessa formula, C(2,0) = 2! / 0! * (2-0)! = 1

C(2,1) = 2! / 1! * (2-1)! = 2

C(2,2) = 2! / 2! * (2-2)! = 1

Ora, se sostituiamo questi valori nell'espansione, otteniamo x^2 + 2x + 1.

È la risposta esatta che abbiamo richiesto. Poiché si trattava di un'espansione più piccola, potresti ritenere che il modo semplice della moltiplicazione sia migliore. Ma cosa succede se devi calcolare la forma espansa di (x+1)^17?

Non c'è modo di moltiplicare così tante volte e sarà un lavoro noioso. Ma, con il concetto di coefficienti binomiali , il lavoro diventa semplice.

Leggi: Concetto di funzione ricorsiva Python: Tutorial Python per principianti

Implementazione Python

Prima di implementare la formula per trovare i coefficienti binomiali , è necessario notare alcuni punti. Sono necessarie due parti per implementare la funzione. Uno è la sottostruttura e la seconda è una funzione per ripetere le sottostrutture.

Per trovare ricorsivamente il valore di C(a, b), possiamo usare la seguente sottostruttura:

C(a, 0) e C(a, a) = 1

C(a, b) = C(a-1, b) + C(a-1, b-1)

Utilizzando queste due formule, è possibile implementare una funzione ricorsiva. Si noti che con un grado di espansione più elevato, molte delle sottostrutture verrebbero ripetute. Potrebbe aumentare il tempo di calcolo se i calcoli vengono ripetuti inutilmente. Quindi, per un'implementazione efficace, è importante mantenere un dizionario con tutti i calcoli precedenti.

Questo tipo di implementazione ha una complessità temporale di O(a*b). La complessità dello spazio varia a seconda dell'implementazione ma può essere limitata a O(b).

Se stai usando Python e non vuoi implementare la funzione da solo, puoi usare la libreria di Python SciPy. Il modulo speciale in SciPy ha la funzione binom(). Ecco come può essere utilizzato:

Basta digitare scipy.special.binom(a, b) e fornirà il valore per lo stesso. Ad esempio, scipy.special.binom(4,3); darà l'output – 4.0

Utilizzo

Gli usi primari dei coefficienti binomiali sono già stati discussi sopra. I coefficienti binomiali sono usati per l'analisi così come la base per la distribuzione binomiale. Un uso meno noto è che i coefficienti binomiali rappresentano le voci nel triangolo di Pascal. Questi tipi di ragioni statistiche rendono necessari i coefficienti binomiali per la comprensione.

Checkout anche: distribuzione binomiale in Python con esempi del mondo reale

Conclusione

Quindi, si trattava di coefficienti binomiali da un punto di vista statistico e di implementazione. Abbiamo discusso le due definizioni di coefficienti binomiali , per le combinazioni e per il calcolo dei coefficienti di espansione. È stata discussa la strategia di implementazione, così come l'implementazione della biblioteca.

Ci sono molte più applicazioni statistiche per i coefficienti binomiali , specialmente quando sono visti con le distribuzioni. E quindi, è fondamentale conoscere i coefficienti binomiali prima di dirigersi verso concetti avanzati basati su statistiche come il core machine learning e gli algoritmi di analisi.

Se sei interessato a saperne di più sull'apprendimento automatico, dai un'occhiata al Diploma PG di IIIT-B e upGrad in Machine Learning e AI, progettato per i professionisti che lavorano e offre oltre 450 ore di formazione rigorosa, oltre 30 casi di studio e incarichi, IIIT- B Status di Alumni, oltre 5 progetti pratici pratici e assistenza sul lavoro con le migliori aziende.