Probabilita' simboli diversi
Abbiamo $S$ simboli distinti, se scriviamo casualmente $n$ di questi $S$ simboli (un simbolo puo' essere ripetuto), trovare la probabilita' di avere $r$ simboli diversi.
Esempio: se i simboli sono 0..9 possiamo scrivere ad esempio 00234.Allora $|S| = 10$, $n = 5$, $r = 4$
Esempio: se i simboli sono 0..9 possiamo scrivere ad esempio 00234.Allora $|S| = 10$, $n = 5$, $r = 4$
Risposte
questa e' la mia soluzione, quindi non e' detto che sia giusta 
se ci sono errori non esitate!:
nota: in generale indico le disposizioni semplici $D(n, k)=(n!)/((n-k)!)$ con $n_{k}$
lo spazio campionario sara' dato dalle stringhe del tipo: $(s_{1},s_{2},...,s_{n})$, dove $s_{i} in S$, e per $i,j < n$ puo' essere che $s_{i} = s_{j}$
in totale abbiamo chiaramente $|S|^n$ stringhe diverse.
Ora contiamo quante sono le stringhe con $r$ simboli diversi: Se ci sono $r$ simboli diversi allora ci saranno $n-r+1$ simboli uguali (contare questi e' piu' facile), inoltre dato che i simboli sono $|S|$ (1) abbiamo $|S|((n),(n-r+1))$ modi di piazzarli all'interno della stringa. Ora rimangono $n-(n-r+1) = r-1$ posti, e tutte le stringhe devono essere diverse... dunque, tenendo conto della (1), abbiamo $(|S|)(|S|-1)(|S|-2)...(|S|-1 -(r-1)+1) = |S|_{r}$ disposizioni.
La probabilita' e' quindi: $p = (((n),(n-r+1))|S|_{r})/|S|^n$
se ci sono errori non esitate!:nota: in generale indico le disposizioni semplici $D(n, k)=(n!)/((n-k)!)$ con $n_{k}$
lo spazio campionario sara' dato dalle stringhe del tipo: $(s_{1},s_{2},...,s_{n})$, dove $s_{i} in S$, e per $i,j < n$ puo' essere che $s_{i} = s_{j}$
in totale abbiamo chiaramente $|S|^n$ stringhe diverse.
Ora contiamo quante sono le stringhe con $r$ simboli diversi: Se ci sono $r$ simboli diversi allora ci saranno $n-r+1$ simboli uguali (contare questi e' piu' facile), inoltre dato che i simboli sono $|S|$ (1) abbiamo $|S|((n),(n-r+1))$ modi di piazzarli all'interno della stringa. Ora rimangono $n-(n-r+1) = r-1$ posti, e tutte le stringhe devono essere diverse... dunque, tenendo conto della (1), abbiamo $(|S|)(|S|-1)(|S|-2)...(|S|-1 -(r-1)+1) = |S|_{r}$ disposizioni.
La probabilita' e' quindi: $p = (((n),(n-r+1))|S|_{r})/|S|^n$
Credo di aver capito che tu intendi "esattamente" r simboli diversi e non "almeno" r, giusto?
Detto questo, non capisco un pò cose sulla tua sol, cmq chiarisci
per esempio S=0,1,2,3,4,5,6,7,8,9 n=8, r=4 ha come stringa accettabile
1,2,3,4,4,3,2,1
usa 4 simboli, ma non ripete nessun simbolo 5 volte...
Detto questo, non capisco un pò cose sulla tua sol, cmq chiarisci
"vl4d":
Ora contiamo quante sono le stringhe con $r$ simboli diversi: Se ci sono $r$ simboli diversi allora ci saranno $n-r+1$ simboli uguali (contare questi e' piu' facile),
per esempio S=0,1,2,3,4,5,6,7,8,9 n=8, r=4 ha come stringa accettabile
1,2,3,4,4,3,2,1
usa 4 simboli, ma non ripete nessun simbolo 5 volte...
gia', funziona solo se i simboli ripetuti sono tutti uguali...
edit: il fatto e' che questo problema l'ho pensato io, e avevo in mente il fatto che i simboli ripetuti debbano essere uguali... provo a generalizzare la cosa
edit2: si, intendo esattamente $r$
edit: il fatto e' che questo problema l'ho pensato io, e avevo in mente il fatto che i simboli ripetuti debbano essere uguali... provo a generalizzare la cosa
edit2: si, intendo esattamente $r$
domanda: se io considero l'equazione $s_{1} + s_{2} +...+ s_{r} = n$, so che il numero di soluzioni per $s_{i}>=0$ e' $((r+n-1),(r-1)) = ((r+n-1),(n))$. E se invece pongo $s_{i}>=1$ o in generale $s_{i}>=k$ ?
sei sicuro dell ultime formule che hai postato? A me se non sbaglio viene diverso, ma è tardi e l'ho visto velocemente... magari prova a postare la dimostrazione...
In ogni caso, se poni condizioni di quel tipo, non dovrebbe essere difficile a ricondurre il nuovo problema ad uno privo di quelle condizioni con opportuni cambiamenti di variabile...
In ogni caso, se poni condizioni di quel tipo, non dovrebbe essere difficile a ricondurre il nuovo problema ad uno privo di quelle condizioni con opportuni cambiamenti di variabile...
teo: le soluzioni di $s_{1} + s_{2} +...+ s_{r} = n$, $s_{i}>=0$ sono $((r+n-1),(r-1)) = ((r+n-1),(n))$
noto che trovare le soluzioni dell'equazione equivale a trovare i modi in cui $n$ palline indistinguibili possono disporsi in $r$ celle. Un esempio di soluzione e': |***|**||*| (1) dove le sbarrette rappresentano le celle, e gli '*' rappresentano le palline. Si tratta di contare in quanti modi e' possibile costruire la (1)
Se ho $r$ celle, allora in totale avro $r+1$ sbarrette, so che avro' una sbarretta' come primo simbolo e una sbarretta come ultimo simbolo. Allora dovro' piazzare ancora $r-1$ sbarrette. Inoltre ci sono $n$ '*' dunque piazzare le sbarrette significa prendere $r-1$ posti in un totale di $r+n-1$, ovvero $((r+n-1),(r-1)) = ((r+n-1),(n))$
Se consideriamo che $s_{i}>=1$ abbiamo che le sbarrette non potranno essere "adiacenti", ovvero potranno essere piazzate _solo_ dopo un '*'. L'ultimo * sappiamo che ha gia' una sbarretta, quella di "chiusura". Dunque rimangono $r-1$ sbarrette da piazzare fra $n-1$ posto disponibili. Quindi se nessuna cella puo' essere vuota il numero di soluzioni e' $((n-1),(r-1))$
Supponendo di non aver detto troppe stupidate, ho pensato ad una cosa del genere per quanto riguarda il problema iniziale:
gli $r$ rimboli diversi possono essere scelti in $((|S|),(r))$ modi diversi. (2)
ora, se il numero di ripetizioni per ogni simbolo $i in [1..r]$ e' $s_{i}$, allora il numero di modi in cui posso ripetere gli $r$ simboli diversi nella stringa(che ricordo essere lunga $n$) sara' dato dal teorema precedente, e sara' quindi $((n-1),(r-1))$
se chiamo $s_{i}^k$ il numero di volte che ripeto il simbolo $i$, nella soluzione numero $k in [1, ((n-1),(r-1))]$ allora il numero totale di stringhe formabili sara':
$((|S|),(r))\sum_{k=1}^{((n-1),(r-1))} (n!)/(s_{1}^k!s_{2}^k!...s_{r}^k!)$
Pero' e' abbastanza inutile perche' non so come generare tutte le soluzioni, ovvero tutti gli $s_{i}^k$
noto che trovare le soluzioni dell'equazione equivale a trovare i modi in cui $n$ palline indistinguibili possono disporsi in $r$ celle. Un esempio di soluzione e': |***|**||*| (1) dove le sbarrette rappresentano le celle, e gli '*' rappresentano le palline. Si tratta di contare in quanti modi e' possibile costruire la (1)
Se ho $r$ celle, allora in totale avro $r+1$ sbarrette, so che avro' una sbarretta' come primo simbolo e una sbarretta come ultimo simbolo. Allora dovro' piazzare ancora $r-1$ sbarrette. Inoltre ci sono $n$ '*' dunque piazzare le sbarrette significa prendere $r-1$ posti in un totale di $r+n-1$, ovvero $((r+n-1),(r-1)) = ((r+n-1),(n))$
Se consideriamo che $s_{i}>=1$ abbiamo che le sbarrette non potranno essere "adiacenti", ovvero potranno essere piazzate _solo_ dopo un '*'. L'ultimo * sappiamo che ha gia' una sbarretta, quella di "chiusura". Dunque rimangono $r-1$ sbarrette da piazzare fra $n-1$ posto disponibili. Quindi se nessuna cella puo' essere vuota il numero di soluzioni e' $((n-1),(r-1))$
Supponendo di non aver detto troppe stupidate, ho pensato ad una cosa del genere per quanto riguarda il problema iniziale:
gli $r$ rimboli diversi possono essere scelti in $((|S|),(r))$ modi diversi. (2)
ora, se il numero di ripetizioni per ogni simbolo $i in [1..r]$ e' $s_{i}$, allora il numero di modi in cui posso ripetere gli $r$ simboli diversi nella stringa(che ricordo essere lunga $n$) sara' dato dal teorema precedente, e sara' quindi $((n-1),(r-1))$
se chiamo $s_{i}^k$ il numero di volte che ripeto il simbolo $i$, nella soluzione numero $k in [1, ((n-1),(r-1))]$ allora il numero totale di stringhe formabili sara':
$((|S|),(r))\sum_{k=1}^{((n-1),(r-1))} (n!)/(s_{1}^k!s_{2}^k!...s_{r}^k!)$
Pero' e' abbastanza inutile perche' non so come generare tutte le soluzioni, ovvero tutti gli $s_{i}^k$
Ok... i risultati mi pare tornino tutti...
Io una volta risolto il caso $s_i>=1$, avrei fatto il cambiamento di variabile $m_i=1+s_i$ con $m_i>=1$ e poi si trova il tuo risultato. Notare che il procedimento è facilmente generalizzabile (questo per quanto riguarda una tua domanda precedente).
In realtà il tuo procedimento per $s_i>=0$ non l'ho ben capito, anche se porta al risultato corretto (cioè potrei giustificarlo passando sottobanco il cambiamento di variabile, ma non so se è il tuo ragionamento). Puoi spiegarlo meglio?
In quanto al problema, anch'io avevo trovato la medesima sommatoria (credo)... Se la vuoi più esplicita prova a cercare "coefficienti multinomiali" su google, magari con il binomio di Newton generalizzato si giunge a qualcosa di più compatto, ma non so... prova!
...
ciao!
Io una volta risolto il caso $s_i>=1$, avrei fatto il cambiamento di variabile $m_i=1+s_i$ con $m_i>=1$ e poi si trova il tuo risultato. Notare che il procedimento è facilmente generalizzabile (questo per quanto riguarda una tua domanda precedente).
In realtà il tuo procedimento per $s_i>=0$ non l'ho ben capito, anche se porta al risultato corretto (cioè potrei giustificarlo passando sottobanco il cambiamento di variabile, ma non so se è il tuo ragionamento). Puoi spiegarlo meglio?
In quanto al problema, anch'io avevo trovato la medesima sommatoria (credo)... Se la vuoi più esplicita prova a cercare "coefficienti multinomiali" su google, magari con il binomio di Newton generalizzato si giunge a qualcosa di più compatto, ma non so... prova!
... ciao!
http://www.openmathtext.org/lecture_not ... _book2.pdf
a pagina 38 ci sono le combinazioni con ripetizione, e la soluzione di quella equazione.Comunque se nn ho capito male il problema è sufficiente usare la formula delle combinazioni con ripetizione. Tutti casi possibili sono tutte le combinazioni con rieptizione di S elementi presi n per volta :$((S+n-1),(n))$ .
Per i casi favorevoli inanzitutto scegliamo gli r simboli distinti che compaiono nella stringa di n simboli. Abbiamo $((S),(r))$ modi per farlo. Nella stringa di n simboli ci rimangono ancora $n-r$ "spazi" da riempire con gli $r$ simboli scelti.Utilizzando sempre la formula delle combinazioni con ripetizione abbiamo $((r+(n-r)-1),(n-r))=((n-1),(n-r))$ possibili configurazioni di questo tipo. Quindi:
$p=(((S),(r))((n-1),(n-r)))/(((S+n-1),(n)))$
a pagina 38 ci sono le combinazioni con ripetizione, e la soluzione di quella equazione.Comunque se nn ho capito male il problema è sufficiente usare la formula delle combinazioni con ripetizione. Tutti casi possibili sono tutte le combinazioni con rieptizione di S elementi presi n per volta :$((S+n-1),(n))$ .
Per i casi favorevoli inanzitutto scegliamo gli r simboli distinti che compaiono nella stringa di n simboli. Abbiamo $((S),(r))$ modi per farlo. Nella stringa di n simboli ci rimangono ancora $n-r$ "spazi" da riempire con gli $r$ simboli scelti.Utilizzando sempre la formula delle combinazioni con ripetizione abbiamo $((r+(n-r)-1),(n-r))=((n-1),(n-r))$ possibili configurazioni di questo tipo. Quindi:
$p=(((S),(r))((n-1),(n-r)))/(((S+n-1),(n)))$
A dire il vero non capisco perchè i casi possibili siano quelli...
e poi quando conti i casi, sei sicuro di non contare più volte qualche combinazione... magari prova a a scriverla meglio che vediamo
e poi quando conti i casi, sei sicuro di non contare più volte qualche combinazione... magari prova a a scriverla meglio che vediamo
sisi hai ragione, ai fini della probabilita' in effetti e' meglio contare le combinazioni con ripetizione, e la tua espressione dovrebbe funzionare. Questo e' fattibile perche' comunque ogni combinazione ha $1/(((S+n-1),(n)))$ di probabilita' (edit: NON e' vero). Pero' a me interessava anche trovare il numero di stringhe formabili, e quindi contare il numero di modi in cui si possono ordinare ciascuna delle $((S),(r))((n-1),(n-r))$ combinazioni 
edit: in ogni caso non mi e' ancora chiaro cosa usi come spazio campionario... ?
edit: in ogni caso non mi e' ancora chiaro cosa usi come spazio campionario... ?
penso di aver trovato una falla nel ragionamento... se non ho capito male tu vedi lo spazio campionario come i vari simboli presenti nella stringa senza tenere presente l'ordinamento. Pero' se consideri le due stringhe: 4444 e 1234, nel tuo spazio campionario _non_ hanno la stessa probabilita' di essere formate (la seconda e' maggiore di un fattore $4!$). Dunque non penso che tu possa fare (casi favorevoli)/(casi totali)
Io non vi seguo... siate più chiari...
cmq vl4d leggi questo file per trovare una espressione compatta per quella sommatoria, in particolare la parte sul teorema multinomiale:
http://www.ds.unifi.it/VL/VL_IT/comb/comb4.html
ciao
cmq vl4d leggi questo file per trovare una espressione compatta per quella sommatoria, in particolare la parte sul teorema multinomiale:
http://www.ds.unifi.it/VL/VL_IT/comb/comb4.html
ciao
Mi hanno detto di guardare i numeri di Stirling e penso di aver finalmente risolto il problema!
Ci sono $((|S|),(r))$ modi per prendere gli $r$ simboli diversi.
Ora consideriamo l'insieme N = {1, 2, ..., n} che rappresenta le posizioni (prima, seconda, ecc) nella stringa di n elementi.
Supponiamo che di sapere in quanti modi si puo' partizionare $N$ in modo che nella partizione ci siano $r$ sottoinsiemi, chiamiamo questo numero $S_n^{r}$.
Se consideriamo anche l'ordine delle partizioni abbiamo in totale $S_{n}^rr!$ modi per partizionare.
Allora se ad ognuno degli $r$ simboli associo una partizione di $N$, posso vedere gli elementi dentro la partizione(che sono numeri da $1$ a $n$) come la posizione che l'r-essimo simbolo ha nella stringa di $n$ elementi.
Per un totale di $((|S|), (r))S_n^rr!$
dove $S_n^r = \frac{1}{r!}\sum_{i=1}^{r}(-1)^{r+i}((r),(i))(i)^{n}$ ovvero i numeri di Stirling del Secondo Tipo.
Ci sono $((|S|),(r))$ modi per prendere gli $r$ simboli diversi.
Ora consideriamo l'insieme N = {1, 2, ..., n} che rappresenta le posizioni (prima, seconda, ecc) nella stringa di n elementi.
Supponiamo che di sapere in quanti modi si puo' partizionare $N$ in modo che nella partizione ci siano $r$ sottoinsiemi, chiamiamo questo numero $S_n^{r}$.
Se consideriamo anche l'ordine delle partizioni abbiamo in totale $S_{n}^rr!$ modi per partizionare.
Allora se ad ognuno degli $r$ simboli associo una partizione di $N$, posso vedere gli elementi dentro la partizione(che sono numeri da $1$ a $n$) come la posizione che l'r-essimo simbolo ha nella stringa di $n$ elementi.
Per un totale di $((|S|), (r))S_n^rr!$
dove $S_n^r = \frac{1}{r!}\sum_{i=1}^{r}(-1)^{r+i}((r),(i))(i)^{n}$ ovvero i numeri di Stirling del Secondo Tipo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo