Partizione di un intero n in k parti

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
flutist001
Messaggi: 35
Iscritto il: 12 feb 2012, 20:08

Partizione di un intero n in k parti

Messaggio da flutist001 » 16 nov 2013, 16:07

Ciao a tutti :)
Studiando s'una dispensa di combinatoria olimpica mi sono imbattuto in questa formula per contare il numero di partizioni di un intero $n$ in $k$ parti:
$$ \binom{n+k-1}{k-1} $$
però la dispensa non ne riporta la dimostrazione né sono riuscito a trovarla su internet...voi la conoscete?
Grazie come sempre!

NicolasRossi
Messaggi: 48
Iscritto il: 18 mar 2013, 22:33
Località: Senise (PZ)

Re: Partizione di un intero n in k parti

Messaggio da NicolasRossi » 16 nov 2013, 16:46

Per partire un intero $n$ in $k$ parti considera una serie di $n+k-1$ caselle e scegline $k-1$ da oscurare, così hai $n$ caselle non oscurate separate da delle "sbarre" (le caselle oscurate) in $k$ gruppi, ora, capisci che il numero di tutti i possibili modi per oscurare le $k-1$ è il numero delle possibili partizioni dell'intero $n$ in $k$ elementi. E questi sono appunto i sottoinsiemi di $k-1$ elementi di un insieme di $n+k-1$ elementi, cioè $\binom{n+k-1}{k-1}$


Nota: sicuramente sarebbe più interessante saperlo fare non potendo oscurare le caselle vicine, come si fa?
"Per tre cose vale la pena di vivere: la matematica, la musica, l'amore." [cit.]

Rispondi