Troviamo parole un po' distinte

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
scambret
Messaggi: 734
Iscritto il: 23 mag 2012, 20:49
Località: Acquarica del Capo

Troviamo parole un po' distinte

Messaggio da scambret »

Abbiamo $N$ lettere diverse e vogliamo costruire parole di lunghezza $n$. Trovare la probabilità che nelle parole ci siano esattamente $k$ lettere differenti (diciamo $N \geq k$ e $n \geq k$).
Avatar utente
Sirio
Messaggi: 317
Iscritto il: 08 set 2016, 22:01

Re: Troviamo parole un po' distinte

Messaggio da Sirio »

Un po' di sano necroposting non si nega a nessuno...
Testo nascosto:
In totale il numero di parole lunghe $n$ da un alfabeto di $N$ lettere è $N^n$, mentre il numero di parole lunghe $n$ da un alfabeto di $k$ lettere è $k^n$. Moltiplicando questo $k^n$ per il numero di modi di scegliere quelle $k$ lettere dall'alfabeto di $N$ lettere si ottiene il numero di parole lunghe $n$ con $k$ lettere prese da quell'alfabeto, ovvero $\displaystyle k^n\cdot{N\choose k}$. La probabilità viene quindi questa brutta espressione: $\displaystyle{N \choose k} \cdot \left(\frac k N\right)^n$.
$T=\sqrt{\dfrac l g 12\pi}$
RiccardoKelso

Re: Troviamo parole un po' distinte

Messaggio da RiccardoKelso »

Occhio agli avverbi :roll:
Avatar utente
Sirio
Messaggi: 317
Iscritto il: 08 set 2016, 22:01

Re: Troviamo parole un po' distinte

Messaggio da Sirio »

Sì, ho saltato "esattamente" qua e là, ma in testa ce l'avevo... No?

Edit: Hai ragione, no... Rimedio:
Testo nascosto:
Alle $\displaystyle k^n\cdot {N\choose k}$ tolgo quelle con al massimo $k-1$ lettere, ovvero $\displaystyle \left(k-1\right)^n\cdot {N\choose {k-1}}$, ottenendo $\displaystyle k^n\cdot {N\choose k}-\left(k-1\right)^n\cdot {N\choose {k-1}}$, da dividere per quell'$N^n$ per trovare una probabilità ancora più brutta: $\displaystyle N^{-n}\cdot\left(k^n\cdot {N\choose k}-\left(k-1\right)^n\cdot {N\choose {k-1}}\right)$
$T=\sqrt{\dfrac l g 12\pi}$
scambret
Messaggi: 734
Iscritto il: 23 mag 2012, 20:49
Località: Acquarica del Capo

Re: Troviamo parole un po' distinte

Messaggio da scambret »

Mmmh ne sei davvero convinto?
Avatar utente
Sirio
Messaggi: 317
Iscritto il: 08 set 2016, 22:01

Re: Troviamo parole un po' distinte

Messaggio da Sirio »

Ok, ho capito dove sta l'altro errore...
Testo nascosto:
Nel rimedio ho tolto più volte le stesse parole...
Prossimamente rimedierò ulteriormente.
$T=\sqrt{\dfrac l g 12\pi}$
scambret
Messaggi: 734
Iscritto il: 23 mag 2012, 20:49
Località: Acquarica del Capo

Re: Troviamo parole un po' distinte

Messaggio da scambret »

Esatto
Avatar utente
Sirio
Messaggi: 317
Iscritto il: 08 set 2016, 22:01

Re: Troviamo parole un po' distinte

Messaggio da Sirio »

Lo rifaccio da zero che faccio prima...
Testo nascosto:
Le parole lunghe $n$ da un alfabeto di $k$ lettere sono $k^n$.
Quelle in cui compaiono tutte sono quelle meno quelle in cui compaiono $k-1$ o meno lettere, ovvero $k\left(k-1\right)^n$. Moltiplico questa differenza per ${N\choose k}$ e trovo il numero di parole buone, che moltiplicato per $N^{-n}$ dà la probabilità: $N^{-n}\cdot{N\choose k}\cdot \left(k^n-k\left(k-1\right)^n\right)$
$T=\sqrt{\dfrac l g 12\pi}$
Avatar utente
Sirio
Messaggi: 317
Iscritto il: 08 set 2016, 22:01

Re: Troviamo parole un po' distinte

Messaggio da Sirio »

Lo rifaccio da zero che faccio prima...
Testo nascosto:
Le parole lunghe $n$ da un alfabeto di $k$ lettere sono $k^n$.
Quelle in cui compaiono tutte sono quelle meno quelle in cui compaiono $k-1$ o meno lettere, ovvero $k\left(k-1\right)^n$. Moltiplico questa differenza per ${N\choose k}$ e trovo il numero di parole buone, che moltiplicato per $N^{-n}$ dà la probabilità: $N^{-n}\cdot{N\choose k}\cdot \left(k^n-k\left(k-1\right)^n\right)$
$T=\sqrt{\dfrac l g 12\pi}$
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Troviamo parole un po' distinte

Messaggio da fph »

Come mai quelle in cui compaiono $k-1$ o meno lettere sarebbero $k(k-1)^n$?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
Sirio
Messaggi: 317
Iscritto il: 08 set 2016, 22:01

Re: Troviamo parole un po' distinte

Messaggio da Sirio »

Perché le ho di nuovo ripetute...
Testo nascosto:
Ho pensato $\left(k-1\right)^n$ per ogni scelta delle $k-1$ lettere dalle $k$ iniziali, ma ripensandoci dovrei fare una sorta di inclusione-esclusione, quindi il numero di parole buone dovrebbe essere $\displaystyle \sum_{i=0}^k\left({k \choose i}\cdot\left(k-i\right)^n\cdot\left(-1\right)^i\right)$
Fatemi sapere se ho sbagliato di nuovo...
$T=\sqrt{\dfrac l g 12\pi}$
Rispondi