Il problema delle 'scatole di pop corn'...
cari amici
mi sono talmente divertito a cimentarmi nel ‘problema delle coincidenze’ proposto da karl, che ho pensato bene di ricambiare il favore proponendo a mia volta un problema [non nuovo intendiamoci…] nel campo delle probabilità. Si tratta del cosiddetto ‘problema delle scatole di pop corn’.
Supponiamo che un produttore di cereali in scatola per promuovere il suo prodotto inserisca in ogni confezione di pop corn un premio [tipo una penna colorata, un pupazzetto, una cartolina, etc…] scelto a caso fra 6 [anche qui il numero può essere diverso…]. Se si vuole entrare in possesso di tutti e 6 i premi qual è all’incirca il numero di confezioni che occorrerà acquistare?… [si spera di non dover svuotare il negozio…]
Buon lavoro!…
lupo grigio
mi sono talmente divertito a cimentarmi nel ‘problema delle coincidenze’ proposto da karl, che ho pensato bene di ricambiare il favore proponendo a mia volta un problema [non nuovo intendiamoci…] nel campo delle probabilità. Si tratta del cosiddetto ‘problema delle scatole di pop corn’.
Supponiamo che un produttore di cereali in scatola per promuovere il suo prodotto inserisca in ogni confezione di pop corn un premio [tipo una penna colorata, un pupazzetto, una cartolina, etc…] scelto a caso fra 6 [anche qui il numero può essere diverso…]. Se si vuole entrare in possesso di tutti e 6 i premi qual è all’incirca il numero di confezioni che occorrerà acquistare?… [si spera di non dover svuotare il negozio…]
Buon lavoro!…
lupo grigio
Risposte
sicuramente dico una ultra-mega-fesseria...sono per caso 65??
ti prego di scusare la mia ignoranza..ma le probabilità non sono state mai il mio forte...ti chiederai allora perchè ho risposto?...bella domanda...
ciao
il vecchio
ti prego di scusare la mia ignoranza..ma le probabilità non sono state mai il mio forte...ti chiederai allora perchè ho risposto?...bella domanda...
ciao
il vecchio
ti dirò: io stavo pensando a 66, ma mi è sorto un dubbio. Se il problema fosse stato con 2 regali quale sarebbe stata la risposta? 3? Ma a posteriori ho pensato: se prendo 3 scatole c'è comunque 1 possibilità su 4 di prendere sempre lo stesso regalo. Qualsiasi numero di scatole prenda ci sara sempre una possibilità (magari molto piccola) di prendere sempre lo stesso regalo. Qui mi sono bloccato.
mamma mia!!!! adesso mi fai venire troppi dubbi!!! anche perchè se dovessi seguire il porcedimento di prima io comprerei solo 2 scatole!!!!e non mi pare il caso!!! però sono contento di essermi almeno avvicinato al tuo ragionamento!!!
di più però non so che fare...magari compro i biscotti...
ciao
il vecchio
di più però non so che fare...magari compro i biscotti...
ciao
il vecchio
I problemi con le probabilità, nonostante mi abbiano sempre affascinato, non sono proprio il mio forte. Quanto sto per riportare potrebbe dunque essere frutto di un "abbaglio".
Riporto le probabilità di avere tutti e 6 i premi (ed anche 5) ai vari acquisti
10 acquisti: 27.18% 6 premi; 50.64% 5 premi
13 acquisti: 51.39% 6 premi; 41.39% 5 premi
18 acquisti: 78.47% 6 premi; 20.53% 5 premi
23 acquisti: 91.08% 6 premi; 8.79% 5 premi
27 acquisti: 95.66% 6 premi; 4.31% 5 premi
36 acquisti: 99.15% 6 premi; 0.85% 5 premi
Non ci metto le mani sul fuoco!
Cordiali Saluti,
Marcello
Riporto le probabilità di avere tutti e 6 i premi (ed anche 5) ai vari acquisti
10 acquisti: 27.18% 6 premi; 50.64% 5 premi
13 acquisti: 51.39% 6 premi; 41.39% 5 premi
18 acquisti: 78.47% 6 premi; 20.53% 5 premi
23 acquisti: 91.08% 6 premi; 8.79% 5 premi
27 acquisti: 95.66% 6 premi; 4.31% 5 premi
36 acquisti: 99.15% 6 premi; 0.85% 5 premi
Non ci metto le mani sul fuoco!
Cordiali Saluti,
Marcello
lupo grigio,
ti sei scordato di noi? Sono curioso di sapere se c'ho azzeccato oppure no.
Marcello
ti sei scordato di noi? Sono curioso di sapere se c'ho azzeccato oppure no.
Marcello
caro Marcello
stai sicuro che non mi sono scordato del problema da me posto... il fatto è semplicemente che l'ho posto senza conoscere la soluzione che ancora debbo trovare...
A risentirci [spero] presto!...
lupo grigio
stai sicuro che non mi sono scordato del problema da me posto... il fatto è semplicemente che l'ho posto senza conoscere la soluzione che ancora debbo trovare...
A risentirci [spero] presto!...
lupo grigio
Jeckyll, perché ti fermi al 99,15%? Qui sta il mio problema, infatti si chiede di entrare in possesso di tutti e sei i regali, quando mi devo fermare? C'è sempre la possibilità (vedi Murphy) di non beccare mai il 6°.
lupo grigio
scusa, pensavo avessi già la soluzione del problema. D'altronde la tua soluzione al problema di karl era così accurata ed esauriente che mi è venuto istintivo pensare che già avessi la soluzione di quest'altro problema. A tutto ciò si aggiunge il fatto che non sono per nulla sicuro del ragionamento che ho seguito (a giochi fatti possiamo discuterne) ed ero curioso di confrontare i miei risultati con i tuoi.
Sarò più paziente
WonderP,
Il fatto è che, per quanto possa essere improbabile, tutti e sei i regali potrebbero non ottenersi mai anche comprando moltissime scatole. Allora la certezza di avere tutti e 6 i regali va intesa, a mio parere, in senso probabilistico: Che probabilità ho di ottenere tutti e sei i regali comprando n scatole? Teoricamente il 100% non si potrà raggiungere mai, ma praticamente una percentuale del 99% può in buona sostanza ritenersi quasi una "certezza". Ho trovato un algoritmo che calcola tale probabilità (di cui però non garantisco la correttezza) al variare del numero di scatole e ho riportato il numero di scatole che forniscono certi "traguardi" di probabilità: il 50%, il 75%, il 90% il 95% ed il 99%
Marcello
scusa, pensavo avessi già la soluzione del problema. D'altronde la tua soluzione al problema di karl era così accurata ed esauriente che mi è venuto istintivo pensare che già avessi la soluzione di quest'altro problema. A tutto ciò si aggiunge il fatto che non sono per nulla sicuro del ragionamento che ho seguito (a giochi fatti possiamo discuterne) ed ero curioso di confrontare i miei risultati con i tuoi.
Sarò più paziente
WonderP,
Il fatto è che, per quanto possa essere improbabile, tutti e sei i regali potrebbero non ottenersi mai anche comprando moltissime scatole. Allora la certezza di avere tutti e 6 i regali va intesa, a mio parere, in senso probabilistico: Che probabilità ho di ottenere tutti e sei i regali comprando n scatole? Teoricamente il 100% non si potrà raggiungere mai, ma praticamente una percentuale del 99% può in buona sostanza ritenersi quasi una "certezza". Ho trovato un algoritmo che calcola tale probabilità (di cui però non garantisco la correttezza) al variare del numero di scatole e ho riportato il numero di scatole che forniscono certi "traguardi" di probabilità: il 50%, il 75%, il 90% il 95% ed il 99%
Marcello
Il mio ragionamento è stato diverso (e penso simile a quello di vecchio): [(5/6+4/6+3/6+2/6+1/6)^-1] + 1
Cioè alla prima scatola sono sicuro di trovare un regalo che mi manca (il +1), alla seconda ho 5/6 di trovare un regalo che mi manca, poi 4/6 e così via risultato 65,5, quindi 66 scatole. Tale ragionamento mi convince veramente poco è lo stesso discorso di chi nel lotto scommette sui ritardatari, se un numero non esce da 200 estrazioni ha la stessa possibilità di uscire di un numero appena estratto.
Modifica
ho sbagliato a scrivere [(5/6+4/6+3/6+2/6+1/6)^-1] + 1
in realtaà è [(5/6*4/6*3/6*2/6*1/6)^-1] + 1
Modificato da - WonderP il 29/01/2004 17:56:45
Cioè alla prima scatola sono sicuro di trovare un regalo che mi manca (il +1), alla seconda ho 5/6 di trovare un regalo che mi manca, poi 4/6 e così via risultato 65,5, quindi 66 scatole. Tale ragionamento mi convince veramente poco è lo stesso discorso di chi nel lotto scommette sui ritardatari, se un numero non esce da 200 estrazioni ha la stessa possibilità di uscire di un numero appena estratto.
Modifica
ho sbagliato a scrivere [(5/6+4/6+3/6+2/6+1/6)^-1] + 1
in realtaà è [(5/6*4/6*3/6*2/6*1/6)^-1] + 1
Modificato da - WonderP il 29/01/2004 17:56:45
mmm...io veramente ho fatto così..sicuramente sbaglio...cmq...
ho 6 tipi di regali no? A B C D E F
compro 1 scatola ci sarà un regalo...
nella prox scatola la probabilità di trovare un regalo diverso sarà 5/6 giusto?
compro la III scatola, la probabilità di trovarvi un regalo diverso dalle 2 precedenti è 4/6
nella IV scatola la probabilità di trovare un altro regalo è così 3/6
poi 2/6
e infine 1/6 per l'ultima scatola.
quindi, e ripeto sicuramente sbaglio, la probabilità di questa immensa botta di culo (cioè di aver comperato proprio 6 scatole in cui ci sono tutti regali differenti) è uguale a
1*5/6*4/6*3/6*2/6*1/6=120/7776
cioè su 7776 sestine 120 sono fortunate come la mia!! ma a me ne occorre solo una per cui faccio 7776/120=64,8 quindi 65!!!
però non ne sono per nulla al mondo sicuro!!!bo...adesso che l'ho scritto mi sono confuso pure io...mo ci dormo su...
WonderP non capisco le tue addizioni elevate alla -1...sintomo di grande ignoranza da parte mia???
il vecchio
ho 6 tipi di regali no? A B C D E F
compro 1 scatola ci sarà un regalo...
nella prox scatola la probabilità di trovare un regalo diverso sarà 5/6 giusto?
compro la III scatola, la probabilità di trovarvi un regalo diverso dalle 2 precedenti è 4/6
nella IV scatola la probabilità di trovare un altro regalo è così 3/6
poi 2/6
e infine 1/6 per l'ultima scatola.
quindi, e ripeto sicuramente sbaglio, la probabilità di questa immensa botta di culo (cioè di aver comperato proprio 6 scatole in cui ci sono tutti regali differenti) è uguale a
1*5/6*4/6*3/6*2/6*1/6=120/7776
cioè su 7776 sestine 120 sono fortunate come la mia!! ma a me ne occorre solo una per cui faccio 7776/120=64,8 quindi 65!!!
però non ne sono per nulla al mondo sicuro!!!bo...adesso che l'ho scritto mi sono confuso pure io...mo ci dormo su...
WonderP non capisco le tue addizioni elevate alla -1...sintomo di grande ignoranza da parte mia???
il vecchio
cari amici
è probabile, e di ciò mi scuso con voi, che abbia formulato il problema non in modo del tutto chiaro e questo ha portato qualcuno un poco fuori strada. Il problema posto è attinente al calcolo delle probabilità, il quale in genere non conosce i concetti di ‘certezza’ o ‘impossibilità’ ma solo di eventi aventi una probabilità più o meno grande di verificarsi. Quindi non ha senso chiedersi quante scatole di pop corn occorre acquistare per avere la ‘certezza’ di procurarsi tutti i premi in palio dal momento che nessun numero rende la probabilità di questo evento pari a 1. Il quesito del problema poi riguardava il calcolo del ‘valore atteso’ del numero di confezioni di pop corn che occorre acquistare per entrare in possesso di tutti i premi in palio. Vediamo di definire meglio le cose…
Indicando con k il numero dei premi in palio [nel problema k=6] e n il numero di confezioni acquistate sia p(k,n) la probabilità che all’n-esimo acquisto si entri in possesso di tutti e k i premi. Il ‘valore atteso’ di n per definizione sarà…
= 
n=1,+00 n*p(k,n) (1)
E’chiaro che,come giustamente ha fatto Jeckyll, per prima cosa occorre trovare p(k,n). Per rendere bene il problema proviamo ad affrontare il caso ‘facile’, quello con due soli premi in palio [k=2]…
Indicando con x e y i due premi in palio ipotizziamo che ad ogni acquisto abbia uguale probabilità di trovare x e y per cui è px=py=1/k=1/2. La probabilità che all’n-esimo acquisto si realizzi l’obiettivo è data dalla probabilità di trovare x dopo aver trovato y nelle n-1 volte precedenti o viceversa. Tale valore è…
p(2,n)= px*py^(n-1) + py*px^(n-1) = ½^(n-1) n>1 (2)
Il risultato è abbastanza intuitivo e si trova, ad esempio, che la probabilità di entrare in possesso di entrambi i premi acquistando due sole confezioni è ½. Delle quattro combinazioni possibili infatti [xx, xy, yx, yy] la seconda e la terza consentono di ottenere il risultato. Il valore aspettato di n si trova applicando la (1)…
= n=2,+00 n*p(2,n) = n=2,+00 n*1/2^(n-1) (3)
Per trovare il valore della serie poniamo nella (3) n-1=i ottenendo…
= i=1,+00 (i+1)*1/2^i = i=1,+00 ½^i + i=1,+00 i*1/2^i (4)
La prima serie che compare nella (4) è nota come ‘serie geometrica’ e il suo valore è…
i=1,+00 a^i = a/1-a = 1 per a=1/2 (5)
La seconda serie che compare nella (4) è nota come ‘serie aritmetico-geometrica’ e il suo valore è…
i=1,+00 d*i*a^i=a*d/(1-a)^2=2 per a=1/2 e d=1 (6)
Il valore atteso che stiamo cercando è dunque=3, ossia mediamente sarà necessario acquistare tre confezioni per entrare in possesso di entrambi i premi. Ciò ovviamente non significa che qualcuno ce la faccia con due e qualcun altro debba invece acquistare decine di confezioni prima di trovare entrambi i premi.
Questo è il ‘caso semplice’. Che dosa succede però se i premi divengono tre o più?…
un cordiale saluto a tutti!...
lupo grigio
è probabile, e di ciò mi scuso con voi, che abbia formulato il problema non in modo del tutto chiaro e questo ha portato qualcuno un poco fuori strada. Il problema posto è attinente al calcolo delle probabilità, il quale in genere non conosce i concetti di ‘certezza’ o ‘impossibilità’ ma solo di eventi aventi una probabilità più o meno grande di verificarsi. Quindi non ha senso chiedersi quante scatole di pop corn occorre acquistare per avere la ‘certezza’ di procurarsi tutti i premi in palio dal momento che nessun numero rende la probabilità di questo evento pari a 1. Il quesito del problema poi riguardava il calcolo del ‘valore atteso’ del numero di confezioni di pop corn che occorre acquistare per entrare in possesso di tutti i premi in palio. Vediamo di definire meglio le cose…
Indicando con k il numero dei premi in palio [nel problema k=6] e n il numero di confezioni acquistate sia p(k,n) la probabilità che all’n-esimo acquisto si entri in possesso di tutti e k i premi. Il ‘valore atteso’ di n per definizione sarà…
n=1,+00 n*p(k,n) (1)E’chiaro che,come giustamente ha fatto Jeckyll, per prima cosa occorre trovare p(k,n). Per rendere bene il problema proviamo ad affrontare il caso ‘facile’, quello con due soli premi in palio [k=2]…
Indicando con x e y i due premi in palio ipotizziamo che ad ogni acquisto abbia uguale probabilità di trovare x e y per cui è px=py=1/k=1/2. La probabilità che all’n-esimo acquisto si realizzi l’obiettivo è data dalla probabilità di trovare x dopo aver trovato y nelle n-1 volte precedenti o viceversa. Tale valore è…
p(2,n)= px*py^(n-1) + py*px^(n-1) = ½^(n-1) n>1 (2)
Il risultato è abbastanza intuitivo e si trova, ad esempio, che la probabilità di entrare in possesso di entrambi i premi acquistando due sole confezioni è ½. Delle quattro combinazioni possibili infatti [xx, xy, yx, yy] la seconda e la terza consentono di ottenere il risultato. Il valore aspettato di n si trova applicando la (1)…
n=2,+00 n*p(2,n) = n=2,+00 n*1/2^(n-1) (3)Per trovare il valore della serie poniamo nella (3) n-1=i ottenendo…
i=1,+00 (i+1)*1/2^i = i=1,+00 ½^i + i=1,+00 i*1/2^i (4)La prima serie che compare nella (4) è nota come ‘serie geometrica’ e il suo valore è…
i=1,+00 a^i = a/1-a = 1 per a=1/2 (5) La seconda serie che compare nella (4) è nota come ‘serie aritmetico-geometrica’ e il suo valore è…
i=1,+00 d*i*a^i=a*d/(1-a)^2=2 per a=1/2 e d=1 (6)Il valore atteso che stiamo cercando è dunque
Questo è il ‘caso semplice’. Che dosa succede però se i premi divengono tre o più?…
un cordiale saluto a tutti!...
lupo grigio
lupo grigio,
c'è qualcosa che mi sfugge.
Credo di aver capito il discorso del "valore atteso", ma ho qualche problema con la serie che hai descritto. Il fatto è che questa serie non mi converge sia nel caso dei 6 premi che nel caso dei 2 premi.
Se non ho capito male tu hai indicato con p(k,n) la probabilità che all'n-ennesima scatola acquistata si entri in possesso di "k" premi. Il problema è che nel caso dei 6 premi, p(6,n) tende ad 1 per "n" che tende ad infinito (cosa che tra l'altro mi pare anche ragionevole) e quindi non vedo come la serie che dà il valore atteso possa convergere.
Anche nel caso semplificato dei 2 premi i conti non mi tornano con la funzione p(2,n) che hai riportato. Consideriamo ad esempio il caso in cui n=3. Tutte le possibili combinazioni sono le seguenti 8: xxx xxy xyx xyy yxx yxy yyx yyy. Si vede che in 6 casi su 8 si hanno 2 premi e solo in 2 casi si ha solo un premio. Quindi dovrebbe essere p(2,3)=0.75, mentre la p(2,n) che hai indicato tu dà p(2,3)=0.25.
Non riesco proprio a districarmi.
Cordiali Saluti,
Marcello
c'è qualcosa che mi sfugge.
Credo di aver capito il discorso del "valore atteso", ma ho qualche problema con la serie che hai descritto. Il fatto è che questa serie non mi converge sia nel caso dei 6 premi che nel caso dei 2 premi.
Se non ho capito male tu hai indicato con p(k,n) la probabilità che all'n-ennesima scatola acquistata si entri in possesso di "k" premi. Il problema è che nel caso dei 6 premi, p(6,n) tende ad 1 per "n" che tende ad infinito (cosa che tra l'altro mi pare anche ragionevole) e quindi non vedo come la serie che dà il valore atteso possa convergere.
Anche nel caso semplificato dei 2 premi i conti non mi tornano con la funzione p(2,n) che hai riportato. Consideriamo ad esempio il caso in cui n=3. Tutte le possibili combinazioni sono le seguenti 8: xxx xxy xyx xyy yxx yxy yyx yyy. Si vede che in 6 casi su 8 si hanno 2 premi e solo in 2 casi si ha solo un premio. Quindi dovrebbe essere p(2,3)=0.75, mentre la p(2,n) che hai indicato tu dà p(2,3)=0.25.
Non riesco proprio a districarmi.
Cordiali Saluti,
Marcello
caro Jeckill
il malinteso nasce dalla definzione di p(k,n). Essa è definita come probabilità che all'n-esimo acquisto si entri in possesso di tutti e k i premi, e ciò significa implicitamante che nei precednti n-1 acquisti questo non era riuscito. Per questo motivo nell'esempio da te citato per k=2 ed n=3 le seuqnze valide sono solamente due [xxy e yyx] dal momento che delle altre due [xxx e yyy] chiramente non soddisfano e le altre quattro [xyx,xyy,yxx,yxy] non sono valide perchè in tal caso il risaultato sarebbe stato raggiunto all'acquisto della seconda confezione [ossia per n=2]. La probabilità cercata è pertanto p(2,3)=2/8=.25...
un cordiale saluto!...
lupo grigio
il malinteso nasce dalla definzione di p(k,n). Essa è definita come probabilità che all'n-esimo acquisto si entri in possesso di tutti e k i premi, e ciò significa implicitamante che nei precednti n-1 acquisti questo non era riuscito. Per questo motivo nell'esempio da te citato per k=2 ed n=3 le seuqnze valide sono solamente due [xxy e yyx] dal momento che delle altre due [xxx e yyy] chiramente non soddisfano e le altre quattro [xyx,xyy,yxx,yxy] non sono valide perchè in tal caso il risaultato sarebbe stato raggiunto all'acquisto della seconda confezione [ossia per n=2]. La probabilità cercata è pertanto p(2,3)=2/8=.25...
un cordiale saluto!...
lupo grigio
Grazie lupo grigio,
adesso i conti mi tornano
Torno a ragionare sul problema.
Marcello
adesso i conti mi tornano
Torno a ragionare sul problema.
Marcello
citazione:
WonderP non capisco le tue addizioni elevate alla -1...sintomo di grande ignoranza da parte mia???
Ho sbagliato a scrivere sono tutti prodotti, ed i conti sono come i tuoi differiscono per il +1 (che torna con il
Dunque,
alla luce di ciò che credo di aver capito, per il problema dei sei premi ho ottenuto un valore atteso di 14.7 scatole (15 scatole "i suppose")
Per quanto riguarda le percentuali nude e crude ho ottenuto i seguenti dati:
con 14 scatole acquistate c'è una probabilità del 58.28% di avere ottenuto tutti e 6 i premi, del 36,82% di averne ottenuti 5 e del 4.77 % di averne ottenuti 4 (più tutta una serie di percentuali minori nei casi di 3, 2 ed 1 regali ottenuti)
Con 15 scatole acquistate c'è una probabilità del 64.42% di avere ottenuto tutti e 6 i premi, del 32.27% di averne ottenuti 5 e del 3.24% di averne ottenuti 4 (più tutta la solita serie di percentuali minori)
Ciò dovrebbe significare che su 1000 persone che acquistano 15 scatole, 644 beccano tutti e sei i premi, 323 se ne beccano 5, 32 se ne beccano 4, ed una sola persona (che in genere sono io) avrà trovato meno di 4 regali.
Rimango in attesa di conferme o smentite.
Cordiali Saluti,
Marcello
alla luce di ciò che credo di aver capito, per il problema dei sei premi ho ottenuto un valore atteso di 14.7 scatole (15 scatole "i suppose")
Per quanto riguarda le percentuali nude e crude ho ottenuto i seguenti dati:
con 14 scatole acquistate c'è una probabilità del 58.28% di avere ottenuto tutti e 6 i premi, del 36,82% di averne ottenuti 5 e del 4.77 % di averne ottenuti 4 (più tutta una serie di percentuali minori nei casi di 3, 2 ed 1 regali ottenuti)
Con 15 scatole acquistate c'è una probabilità del 64.42% di avere ottenuto tutti e 6 i premi, del 32.27% di averne ottenuti 5 e del 3.24% di averne ottenuti 4 (più tutta la solita serie di percentuali minori)
Ciò dovrebbe significare che su 1000 persone che acquistano 15 scatole, 644 beccano tutti e sei i premi, 323 se ne beccano 5, 32 se ne beccano 4, ed una sola persona (che in genere sono io
) avrà trovato meno di 4 regali.Rimango in attesa di conferme o smentite.
Cordiali Saluti,
Marcello
cari amici
mi scuso con voi per aver atteso un poco per tornare sul problema da me proposto, ma ho pensato che, prima di affrontarne la soluzione nel caso generale [ossia con un numero qualsiasi k di premi in palio], servisse il passaggio attraverso uno step preliminare…
Consideriamo k diverse classi di oggetti e proviamo a trovare le possibili partizioni di n oggetti comunque scelti da esse. Se in generale abbiamo n1 oggetti della prima classe, n2 della seconda classe…. nk della k-esima classe dovrà essere…
n1+n2+…+nk=n (1)
... in cui le ni, i=1,2,…,k sono interi non negativi. E’ importante sottolineare il fatto che se un certo insieme N=(n1,n2,…,nk) soddisfa la (1) lo stesso varrà per tutti gli altri insiemi ottenuti da quello permutando le ni. Il problema che ci proponiamo di risolvere è stabilire il numero di insiemi distinti di numeri che soddisfano la (1) e chiameremo questo numero q(k,n). Un esempio assai semplice: k=2, n=3. Le combinazioni di numeri che soddisfano la (1) sono in questo caso 4 e precisamente: (3,0) (0,3) (2,1) (1,2)…
Per trovare q(k,n) procediamo in questo modo. Dalla nota identità…
1+x+x^2+…+x^n+… =1/(1-x) -1
… si ricava senza difficoltà che…
(1-x)^-k = (1+x+x^2+...+x^n+...)^k= q(k,0)+q(k,1)*x+q(k,2)*x^2+...+q(k,n)*x^n+… (3)
Della validità della (3) ci si rende conto se si considera il fatto che il coefficiente della potenza n-esima di x nel polinomio che costituisce l’ultimo termine rappresenta proprio il numero di possibili modi con cui moltiplicando una potenza di x di grado ni scelta da ciascuno dei k fattori si ottiene un termine pari a x^n, rispettando così la (1).
Supponiamo ora di derivare il polinomio espresso dalla (3) n volte rispetto alla x. Otterremo…
d^n/dx^n [(1-x)^-k] = n! *q(k,n) + (n+1)! q(k,n+1)* x +[termini contenenti potenze di x di grado >=2] (4)
Dalla (4) si ricava immediatamente la relazione che stiamo cercando, ossia…
q(k,n)= 1/n!* d^n/dx^n [(1-x)^-k] per x=0 = k*(k+1)*…*(k+n-1)/n! = (k+n-1)!/[(k-1)!*n!] (5)
Il termine ottenuto ha la forma di un ‘coefficiente binomiale’ e si indica per comodità con (k+n-1,n).
Verifichiamo a titolo di esempio per k=6, n=2. Sarà q(6,2)= 7!/(5!2!) = 21. Le 21 soluzioni sono riportate qui di seguito…
(2,0,0,0,0,0) (0,2,0,0,0,0) (0,0,2,0,0,0)
(0,0,0,2,0,0) (0,0,0,0,2,0) (0,0,0,0,0,2)
(1,1,0,0,0,0) (1,0,1,0,0,0) (1,0,0,1,0,0)
(1,0,0,0,1,0) (1,0,0,0,0,1) (0,1,1,0,0,0)
(0,1,0,1,0,0) (0,1,0,0,1,0) (0,1,0,0,0,1)
(0,0,1,1,0,0) (0,0,1,0,1,0) (0,0,1,0,0,1)
(0,0,0,1,1,0) (0,0,0,1,0,1) (0,0,0,0,1,1)
A che cosa potrà servire il risultato ottenuto ora lo vedremo tra non molto… almeno lo spero…
cordiali saluti a tutti!…
lupo grigio
Modificato da - lupo grigio il 11/02/2004 10:01:16
mi scuso con voi per aver atteso un poco per tornare sul problema da me proposto, ma ho pensato che, prima di affrontarne la soluzione nel caso generale [ossia con un numero qualsiasi k di premi in palio], servisse il passaggio attraverso uno step preliminare…
Consideriamo k diverse classi di oggetti e proviamo a trovare le possibili partizioni di n oggetti comunque scelti da esse. Se in generale abbiamo n1 oggetti della prima classe, n2 della seconda classe…. nk della k-esima classe dovrà essere…
n1+n2+…+nk=n (1)
... in cui le ni, i=1,2,…,k sono interi non negativi. E’ importante sottolineare il fatto che se un certo insieme N=(n1,n2,…,nk) soddisfa la (1) lo stesso varrà per tutti gli altri insiemi ottenuti da quello permutando le ni. Il problema che ci proponiamo di risolvere è stabilire il numero di insiemi distinti di numeri che soddisfano la (1) e chiameremo questo numero q(k,n). Un esempio assai semplice: k=2, n=3. Le combinazioni di numeri che soddisfano la (1) sono in questo caso 4 e precisamente: (3,0) (0,3) (2,1) (1,2)…
Per trovare q(k,n) procediamo in questo modo. Dalla nota identità…
1+x+x^2+…+x^n+… =1/(1-x) -1
… si ricava senza difficoltà che…
(1-x)^-k = (1+x+x^2+...+x^n+...)^k= q(k,0)+q(k,1)*x+q(k,2)*x^2+...+q(k,n)*x^n+… (3)
Della validità della (3) ci si rende conto se si considera il fatto che il coefficiente della potenza n-esima di x nel polinomio che costituisce l’ultimo termine rappresenta proprio il numero di possibili modi con cui moltiplicando una potenza di x di grado ni scelta da ciascuno dei k fattori si ottiene un termine pari a x^n, rispettando così la (1).
Supponiamo ora di derivare il polinomio espresso dalla (3) n volte rispetto alla x. Otterremo…
d^n/dx^n [(1-x)^-k] = n! *q(k,n) + (n+1)! q(k,n+1)* x +[termini contenenti potenze di x di grado >=2] (4)
Dalla (4) si ricava immediatamente la relazione che stiamo cercando, ossia…
q(k,n)= 1/n!* d^n/dx^n [(1-x)^-k] per x=0 = k*(k+1)*…*(k+n-1)/n! = (k+n-1)!/[(k-1)!*n!] (5)
Il termine ottenuto ha la forma di un ‘coefficiente binomiale’ e si indica per comodità con (k+n-1,n).
Verifichiamo a titolo di esempio per k=6, n=2. Sarà q(6,2)= 7!/(5!2!) = 21. Le 21 soluzioni sono riportate qui di seguito…
(2,0,0,0,0,0) (0,2,0,0,0,0) (0,0,2,0,0,0)
(0,0,0,2,0,0) (0,0,0,0,2,0) (0,0,0,0,0,2)
(1,1,0,0,0,0) (1,0,1,0,0,0) (1,0,0,1,0,0)
(1,0,0,0,1,0) (1,0,0,0,0,1) (0,1,1,0,0,0)
(0,1,0,1,0,0) (0,1,0,0,1,0) (0,1,0,0,0,1)
(0,0,1,1,0,0) (0,0,1,0,1,0) (0,0,1,0,0,1)
(0,0,0,1,1,0) (0,0,0,1,0,1) (0,0,0,0,1,1)
A che cosa potrà servire il risultato ottenuto ora lo vedremo tra non molto… almeno lo spero…
cordiali saluti a tutti!…
lupo grigio
Modificato da - lupo grigio il 11/02/2004 10:01:16
cari amici
facciamo ancora un passetto avanti nella suzione del problema e determiniamo questa volta le combinazioni di k numeri strettamente positivi [ossia ni>0 per i=1,2,…,k] in modo che sia…
n1+n2+… nk=n (1)
Indichiamo con s(k,n) il numero di queste combinazioni. Per calcolare s(k,n) introduciamo una nuova funzione generatrice che chiameremo Hk(x) e il cui sviluppo è dato da…
Hk(x)= x^k * (1-x)^-k = (x+x^2+...+x^i+…)^k= s(k,k)*x^k+s(k,k+1)*x^k+1+…+s(k,n)*x^n+… (2)
Non è difficle vedere che anche in questo caso, come nel precedente è…
s(k,n)= 1/n! * d^n/dx^n Hk(x) per x=0 (2)
Per il calcolo della derivata si utilizza la formula generale che da la derivata del prodotto di due funzioni u(x) e v(x)…
d^n/dx^n (u*v)= [i=0,n] (n,i) d^i/dx^i u * d^(n-i)/dx^(n-i) v (3)
… in cui con (n,i) si intendono i ‘coefficienti binomiali’ dati da (n,i)= n!/i!*(n-i)!
Ponendo u(x)= x^k e v(x)= (1-x)^-k si ottiene…
d^i/dx^i x^k = k*(k-1)*…(k-i+1)*x^(k-i)
d^i/dx^i (1-x)^-k = k*(k+1)*…*(k+i-1)*(1-x)^-(k+i) (4)
Siccome siamo interessati alle derivate di Hk(x) per x=0 è interessante rilevare che tutte le derivate della u(x) si annul,ano per x=0, ad eccezione della derivata di ordine k che vale k!. Per questo possiamo scrivere…
d^/dx^n Hk(x) per x=0 = (n,k)*k!*d^(n-k)/dx^(n-k) (1-x)^-k = n!*(n-1)*(n-2)*…*(k+1)*k/(n-k)!=
= n!*(n-1)!/(k-1)!*(n-k)! (5)
Il risultato cercato sarà dunque…
s(k,n) = (n-1)!/(n-k)!*(k-1)! (6)
Alcuni esempi. Per k=3, n=4 s(3,4)= 3!/2!=3 , qui sotto riportati…
(2,1,1) (1,2,1) (1,1,2)
Per k=3, n=5 s(3,5)= 4!/2!*2!=3*2=6 , qui sotto riportati…
(3,1,1) (1,3,1) (1,1,3)
(2,2,1) (2,1,2) (1,2,2)
Per k=6, n=8 s(6,8)= 7!/2!*5!= 7*3=21, qui sotto riportati…
(3,1,1,1,1,1) (1,3,1,1,1,1) (1,1,3,1,1,1)
(1,1,1,3,1,1) (1,1,1,1,3,1) (1,1,1,1,1,3)
(2,2,1,1,1,1) (2,1,2,1,1,1) (2,1,1,2,1,1)
(2,1,1,1,2,1) (2,1,1,1,1,2) (1,2,2,1,1,1)
(1,2,1,2,1,1) (1,2,1,1,2,1) (1,2,1,1,1,2)
(1,1,2,2,1,1) (1,1,2,1,2,1) (1,1,2,1,1,2)
(1,1,1,2,2,1) (1,1,1,2,1,2) (1,1,1,1,2,2)
L’utilità di questo risultato per la soluzione finale del problema sarà ben presto evidente…
cordiali saluti a tutti!…
lupo grigio
facciamo ancora un passetto avanti nella suzione del problema e determiniamo questa volta le combinazioni di k numeri strettamente positivi [ossia ni>0 per i=1,2,…,k] in modo che sia…
n1+n2+… nk=n (1)
Indichiamo con s(k,n) il numero di queste combinazioni. Per calcolare s(k,n) introduciamo una nuova funzione generatrice che chiameremo Hk(x) e il cui sviluppo è dato da…
Hk(x)= x^k * (1-x)^-k = (x+x^2+...+x^i+…)^k= s(k,k)*x^k+s(k,k+1)*x^k+1+…+s(k,n)*x^n+… (2)
Non è difficle vedere che anche in questo caso, come nel precedente è…
s(k,n)= 1/n! * d^n/dx^n Hk(x) per x=0 (2)
Per il calcolo della derivata si utilizza la formula generale che da la derivata del prodotto di due funzioni u(x) e v(x)…
d^n/dx^n (u*v)=
[i=0,n] (n,i) d^i/dx^i u * d^(n-i)/dx^(n-i) v (3)… in cui con (n,i) si intendono i ‘coefficienti binomiali’ dati da (n,i)= n!/i!*(n-i)!
Ponendo u(x)= x^k e v(x)= (1-x)^-k si ottiene…
d^i/dx^i x^k = k*(k-1)*…(k-i+1)*x^(k-i)
d^i/dx^i (1-x)^-k = k*(k+1)*…*(k+i-1)*(1-x)^-(k+i) (4)
Siccome siamo interessati alle derivate di Hk(x) per x=0 è interessante rilevare che tutte le derivate della u(x) si annul,ano per x=0, ad eccezione della derivata di ordine k che vale k!. Per questo possiamo scrivere…
d^/dx^n Hk(x) per x=0 = (n,k)*k!*d^(n-k)/dx^(n-k) (1-x)^-k = n!*(n-1)*(n-2)*…*(k+1)*k/(n-k)!=
= n!*(n-1)!/(k-1)!*(n-k)! (5)
Il risultato cercato sarà dunque…
s(k,n) = (n-1)!/(n-k)!*(k-1)! (6)
Alcuni esempi. Per k=3, n=4 s(3,4)= 3!/2!=3 , qui sotto riportati…
(2,1,1) (1,2,1) (1,1,2)
Per k=3, n=5 s(3,5)= 4!/2!*2!=3*2=6 , qui sotto riportati…
(3,1,1) (1,3,1) (1,1,3)
(2,2,1) (2,1,2) (1,2,2)
Per k=6, n=8 s(6,8)= 7!/2!*5!= 7*3=21, qui sotto riportati…
(3,1,1,1,1,1) (1,3,1,1,1,1) (1,1,3,1,1,1)
(1,1,1,3,1,1) (1,1,1,1,3,1) (1,1,1,1,1,3)
(2,2,1,1,1,1) (2,1,2,1,1,1) (2,1,1,2,1,1)
(2,1,1,1,2,1) (2,1,1,1,1,2) (1,2,2,1,1,1)
(1,2,1,2,1,1) (1,2,1,1,2,1) (1,2,1,1,1,2)
(1,1,2,2,1,1) (1,1,2,1,2,1) (1,1,2,1,1,2)
(1,1,1,2,2,1) (1,1,1,2,1,2) (1,1,1,1,2,2)
L’utilità di questo risultato per la soluzione finale del problema sarà ben presto evidente…
cordiali saluti a tutti!…
lupo grigio
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo