Impazzire su un calcolo combinatorio

[fabiola5]

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

[Megan00b]

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)!).

[Megan00b]

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.

[fabiola5]

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

[Megan00b]

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

perchè avevo fumato pesante
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.