Intuizione della soluzione di questo esercizio con il coefficiente binomiale?
Salve a tutti, vi propongo il problema che mi è stato chiesto di risolvere, e come l'ho risolto:
Esercizio: Si considerino tutte le possibili Word di lunghezza $n$ che si possono generare a partire dai simboli ${0,1}$ (cioè essenzialmente, bit) e si determini quante di queste posseggono più $1$ che $0$.
Premetto che avendo studiato con ottimo profitto informatica alla scuola superiore, la risposta la sapevo già, per cui ne ho approfittato per cercare di compiere il percorso al contrario.
Se $n$ è un numero pari allora di parole (per un totale di $2^n$ di queste) con più uni che zeri, sono esattamente $2^{n-1}-1$. Si pensi per convincersene che il complemento ad uno di ognuna delle parole che ha più zeri che uni ha più uni che zeri, e il viceversa.
Se $n$ è un numero dispari di parole con più uni che zeri (risparmio anche qui la spiegazione) è $2^{n-1}$.
Per cui, notando che \(\sum_{k=0}^n {{n}\choose{k}} = 2^n \to 2^{n-1} = \frac{1}{2} \sum_{k=0}^n {{n}\choose{k}} = \sum_{k=0}^{⌊\frac{n}{2}⌋} {{n}\choose{k}}\)
Questo perché \({{n}\choose{k}} = {{n}\choose{n-k}}\)
E contemporaneamente \(2^{n-1}-1 = \sum_{k=0}^{⌊\frac{n}{2}⌋} {{n}\choose{k}} - 1 = \sum_{k=0}^{⌊\frac{n}{2}-1⌋} {{n}\choose{k}}\)
\( \text{Risposta} = \begin{cases} \sum_{k=0}^{⌊\frac{n}{2}-1⌋} {{n}\choose{k}} & \mbox{Se } n\mbox{ è pari} \\ \sum_{k=0}^{⌊\frac{n}{2}⌋} {{n}\choose{k}}\ & \mbox{Se } n\mbox{ è dispari} \end{cases} \)
Tuttavia sono ben convinto che non ci sarei mai arrivato usando il solo ragionamento statistico (cioè procedendo nel verso giusto, quello obbligato se non avessi conosciuto a priori la risposta).
Come si deve ragionare in questi casi?
Esercizio: Si considerino tutte le possibili Word di lunghezza $n$ che si possono generare a partire dai simboli ${0,1}$ (cioè essenzialmente, bit) e si determini quante di queste posseggono più $1$ che $0$.
Premetto che avendo studiato con ottimo profitto informatica alla scuola superiore, la risposta la sapevo già, per cui ne ho approfittato per cercare di compiere il percorso al contrario.
Se $n$ è un numero pari allora di parole (per un totale di $2^n$ di queste) con più uni che zeri, sono esattamente $2^{n-1}-1$. Si pensi per convincersene che il complemento ad uno di ognuna delle parole che ha più zeri che uni ha più uni che zeri, e il viceversa.
Se $n$ è un numero dispari di parole con più uni che zeri (risparmio anche qui la spiegazione) è $2^{n-1}$.
Per cui, notando che \(\sum_{k=0}^n {{n}\choose{k}} = 2^n \to 2^{n-1} = \frac{1}{2} \sum_{k=0}^n {{n}\choose{k}} = \sum_{k=0}^{⌊\frac{n}{2}⌋} {{n}\choose{k}}\)
Questo perché \({{n}\choose{k}} = {{n}\choose{n-k}}\)
E contemporaneamente \(2^{n-1}-1 = \sum_{k=0}^{⌊\frac{n}{2}⌋} {{n}\choose{k}} - 1 = \sum_{k=0}^{⌊\frac{n}{2}-1⌋} {{n}\choose{k}}\)
\( \text{Risposta} = \begin{cases} \sum_{k=0}^{⌊\frac{n}{2}-1⌋} {{n}\choose{k}} & \mbox{Se } n\mbox{ è pari} \\ \sum_{k=0}^{⌊\frac{n}{2}⌋} {{n}\choose{k}}\ & \mbox{Se } n\mbox{ è dispari} \end{cases} \)
Tuttavia sono ben convinto che non ci sarei mai arrivato usando il solo ragionamento statistico (cioè procedendo nel verso giusto, quello obbligato se non avessi conosciuto a priori la risposta).
Come si deve ragionare in questi casi?
Risposte
"Moralizzatore":
Se $n$ è un numero pari allora di parole (per un totale di $2^n$ di queste) con più uni che zeri, sono esattamente $2^{n-1}-1$.
Nessuno si accorge che questo risultato è errato?
Il risultato corretto è $(2^n-((n),(n/2)))/2=2^(n-1)-1/2 ((n),(n/2))$
Che è semplicemente il totale delle combinazioni meno il termine centrale della successione il tutto diviso 2.
Infatti:
$2^n=sum_(k=0)^(n)((n),(k))=sum_(0)^(n/2-1)((n),(k))+((n),(n/2))+sum_(k=n/2+1)^(n)((n),(k))=2sum_(k=0)^(n/2-1)((n),(k))+((n),(n/2))$
E dunque
$sum_(k=0)^(n/2-1)((n),(k))=(2^n-((n),(n/2)))/2=2^(n-1)-1/2((n),(n/2))$
Mentre per $n$ dispari il risultato è corretto e banalmente viene $2^n/2=2^(n-1)$
L'interpretazione probabilistica è semplicissima: $((n),(k))$sono proprio le combinazioni con k successi su n prove
Ovviamente le formule che avete impostato con le somme dei coefficienti binomiali sono giuste ma alquanto inutili, soprattutto per l'abuso della funzione "Floor"
Penso di non avere ben capito: Il numero totale di combinazioni con $n$ numeri è $2^n$. Tra queste si devono scegliere tutte quelle con almeno:
$\cdot \ceil{\frac{n}{2}}$ Se $n$ è dispari
$\cdot \frac{n}{2} + 1$ Se $n$ è pari
caratteri uno, e i rimanenti tutti nulli ovviamente.
A questo punto mi trovo in difficoltà ad inserire il binomiale, perché nella mia sconfinata ignoranza lo interpreto come il numero di modi in cui si può selezionare da un insieme di cardinalità $N$ un sottoinsieme con cardinalità $ k< N $, ma qui a priori non si sa quante sono le parole, tra le $2^n$, che hanno più uni che zeri, ed è quello che appunto si vuole trovare ($k$ non è noto).
$\cdot \ceil{\frac{n}{2}}$ Se $n$ è dispari
$\cdot \frac{n}{2} + 1$ Se $n$ è pari
caratteri uno, e i rimanenti tutti nulli ovviamente.
A questo punto mi trovo in difficoltà ad inserire il binomiale, perché nella mia sconfinata ignoranza lo interpreto come il numero di modi in cui si può selezionare da un insieme di cardinalità $N$ un sottoinsieme con cardinalità $ k< N $, ma qui a priori non si sa quante sono le parole, tra le $2^n$, che hanno più uni che zeri, ed è quello che appunto si vuole trovare ($k$ non è noto).
"tommik":
....mentre a te sarebbe venuto $2^(4-1)-1=7$
Sì, ho fatto caso all'errore quanto ho conteggiato sul campo già prima della mia ultima risposta, ma continuo a far fatica, alla luce della interpretazione che ho studiato del coefficiente binomiale, a convincermi che se $k$ indica il numero di cifre $1$ in una word di $n$ bit allora \( {n}\choose{k}\) indica la quantità di parole tra tutte le $2^n$ con esattamente $k$ uni.
Per il resto ci sono.
Certo, ho peccato di specificare, mea culpa: nella pratica oramai sono convinto che sia vero, ho già verificato in più modi diversi, il mio dubbio era più che altro teorico...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo