Troviamo parole un po' distinte

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

Troviamo parole un po' distinte

Messaggio da scambret » 22 set 2016, 11:29

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: 279
Iscritto il: 08 set 2016, 22:01

Re: Troviamo parole un po' distinte

Messaggio da Sirio » 22 mag 2017, 15:51

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}$
"Sirio Passirio" cit. Nicola S.

Avatar utente
RiccardoKelso
Messaggi: 133
Iscritto il: 25 ago 2015, 14:17
Località: Provincia di Milano

Re: Troviamo parole un po' distinte

Messaggio da RiccardoKelso » 22 mag 2017, 16:18

Occhio agli avverbi :roll:
Hai paura di bagnarti?

Non si può entrare nell'angolo rotture della lidl

$N_n=(n-1)(N_{n-1}+N_{n-2}), \space N_1=0, \space N_2=1$

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

Re: Troviamo parole un po' distinte

Messaggio da Sirio » 22 mag 2017, 16:58

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}$
"Sirio Passirio" cit. Nicola S.

scambret
Messaggi: 681
Iscritto il: 23 mag 2012, 20:49
Località: Acquarica del Capo

Re: Troviamo parole un po' distinte

Messaggio da scambret » 22 mag 2017, 19:14

Mmmh ne sei davvero convinto?

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

Re: Troviamo parole un po' distinte

Messaggio da Sirio » 22 mag 2017, 20:59

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}$
"Sirio Passirio" cit. Nicola S.

scambret
Messaggi: 681
Iscritto il: 23 mag 2012, 20:49
Località: Acquarica del Capo

Re: Troviamo parole un po' distinte

Messaggio da scambret » 23 mag 2017, 00:00

Esatto

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

Re: Troviamo parole un po' distinte

Messaggio da Sirio » 23 mag 2017, 13:14

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}$
"Sirio Passirio" cit. Nicola S.

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

Re: Troviamo parole un po' distinte

Messaggio da Sirio » 23 mag 2017, 16:12

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}$
"Sirio Passirio" cit. Nicola S.

fph
Site Admin
Messaggi: 3478
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Troviamo parole un po' distinte

Messaggio da fph » 23 mag 2017, 19:26

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: 279
Iscritto il: 08 set 2016, 22:01

Re: Troviamo parole un po' distinte

Messaggio da Sirio » 23 mag 2017, 20:41

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}$
"Sirio Passirio" cit. Nicola S.

Rispondi