impazzire su un calcolo combinatorio

Messaggioda fabiola » 25/07/2007, 17:57

Ho un insieme così definito $K_n={(k_1,k_2,...k_r)\in N_0^r:sum_(s=1)^r k_s=n}$ e devo dimostrare che $K_n$ ha $((n+r)!)/((r-1)!(n+1)!)$ elementi ovvero $n+r$ su $r-1$ dove per su intendo coefficiente binomiale
fabiola
Junior Member
Junior Member
 
Messaggio: 8 di 117
Iscritto il: 12/06/2007, 16:02

Messaggioda Megan00b » 25/07/2007, 22:51

Se con $N_0$ intendi i naturali compreso lo 0 credo che la relazione sia sbagliata: se prendi r=2 allora Kn ha n+1 elementi infatti per ogni scelta di $k_1$ c'è una solo scelta possibile per $k_2$ e cioè $n-k_1$.
A $k_1$ puoi dare tutti i valori tra 0 e n compresi quindi n+1 possibilità. Mentre la formula che hai scritto vorrebbe n+2 possibilità.
Così su due piedi direi che la formula corretta dovrebbe essere $((n+r-1)!)/((r-1)!(n)!).
"Un popolo che non riconosce i diritti dell'uomo e non attua la divisione dei poteri non ha Costituzione" [Déclaration des droits de l'homme et du citoyen]
Chi di spada perisce... muore.
Avatar utente
Megan00b
Senior Member
Senior Member
 
Messaggio: 18 di 1167
Iscritto il: 01/07/2007, 20:05
Località: Pisa

Messaggioda Megan00b » 25/07/2007, 22:57

Per quanto riguarda la dimostrazione pensala così:
se r=2 vedi sopra.
per r generico. supponi che la formula sia vera per r e la verifichi per r+1:
prendi $k_1$: hai n-r possibilità. Per ognuna di queste calcoli quante possibilità hai di scegliere $k_2 ... k_r$ in modo che la loro somma sia $n-k_1$. Per hp induttiva le possibiltà
in tutto diventano la sommatoria per $k_1$ da 0 a n del numero di possibilità di scelta degli elementi 2...r (cioè la nostra formula). NOn se è chiaro. Se provi a semplificare la somma dovresti ottenere la forumla per r+1.
"Un popolo che non riconosce i diritti dell'uomo e non attua la divisione dei poteri non ha Costituzione" [Déclaration des droits de l'homme et du citoyen]
Chi di spada perisce... muore.
Avatar utente
Megan00b
Senior Member
Senior Member
 
Messaggio: 19 di 1167
Iscritto il: 01/07/2007, 20:05
Località: Pisa

Messaggioda fabiola » 26/07/2007, 18:08

Ti ringrazio perchè mi hai dato molte delucidazioni, ma ho ancora qualche dubbio; perchè dici che per $k_1$ ho $n-r$ possibilità? dovrebbero essere sempre $n+1$ o sbaglio? Infine, cerco di ragionare sulla sommatoria, faccio delle semplificazioni, ma non riesco ad arrivare al risultato voluto. Grazie ancora
fabiola
Junior Member
Junior Member
 
Messaggio: 9 di 117
Iscritto il: 12/06/2007, 16:02

Messaggioda Megan00b » 27/07/2007, 11:06

perchè dici che per k1 ho n-r possibilità?

perchè avevo fumato pesante :D
sì sono n+1. Insomma l'idea è che al primo posto ci metti quello che ti pare. Per ogni scelta del primo posto provi a riempire i successivi in modo che la loro somma faccia n-(il primo elemento).
per le semplificazioni più tardi vedo se ci riesco io e posto.
"Un popolo che non riconosce i diritti dell'uomo e non attua la divisione dei poteri non ha Costituzione" [Déclaration des droits de l'homme et du citoyen]
Chi di spada perisce... muore.
Avatar utente
Megan00b
Senior Member
Senior Member
 
Messaggio: 24 di 1167
Iscritto il: 01/07/2007, 20:05
Località: Pisa


Torna a Statistica e probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite