$x_1+x_2+\ldots+x_k \le n$

[jordan]

Siano $n,k$ due interi positivi fissati. Trovare quante sono le soluzioni ordinate negli interi non negativi a \[ x_1+x_2+\ldots+x_k \le n \]

[Hawk]

Allora proviamoci.
Il numero di modi di scrivere $ n $ come somma di $ k $ interi $ \geq 0 $ (in modo che due somme differiscano anche per l'ordine degli addendi) è dato da: $ \displaystyle\binom{n+k-1}{k-1} $.
Per cui applicando questo per $ 0,1,....n $, si ha che il numero di soluzioni è $ \displaystyle\sum_{i=0}^n \displaystyle\binom{i+k-1}{i}=\displaystyle\binom{n+k}{n} $

[jordan]

Il numero di modi di scrivere $ n $ come somma di $ k $ interi $ \geq 0 $ (in modo che due somme differiscano anche per l'ordine degli addendi) è dato da: $ \displaystyle\binom{n+k-1}{k-1} $.

Giusto, perchè? (*)

Per cui applicando questo per $ 0,1,....n $, si ha che il numero di soluzioni è $ \displaystyle\sum_{i=0}^n \displaystyle\binom{i+k-1}{i}=\displaystyle\binom{n+k}{n} $

Come giustifichi questa sommatoria?

Volendo, potresti concludere direttamente da (*)..

[simone256]

Provo a rispondere io!

Testo nascosto:

La partizione di un intero $ n $ a me piace pensarla (e mi è anche stata spiegata così) come mettere $ n $ palline bianche in fila... e per suddividerle in $ k $ gruppi basta mettere a caso tra queste $ k-1 $ palline nere che fanno diciamo da "divisore". Ora non ci resta che trovare le combinazioni $ \displaystyle\binom{n+k-1}{k-1} $.
Per risolvere il problema basta sommare le partizioni di tutti gli $ i $ interi minori uguali a $ n $: $ \displaystyle\sum_{i=0}^n \displaystyle\binom{i+k-1}{i}=\displaystyle\binom{n+k}{n} $

[Hawk]

Visto che ti trovi dimostra anche l'uguaglianza della sommatoria .

[jordan]

La prima risposta è giusta, ma la seconda ancora non è giustificata..

[xXStephXx]

Volendo credo che per raggirare la sommatoria si può ottenere lo stesso risultato da $x_1+x_2+...+x_k+x_{k+1} = n$
Infatti togliendo l'ultimo addendo si ottiene proprio $x_1+x_2+...+x_k \leq n$ (e viceversa).
Forse questo si può considerare anche come un metodo per dimostrare quella sommatoria.

[Hawk]

La sommatoria sfrutta la ben nota identità:
$ \dbinom{n+0}{0}+.....\dbinom{n+i}{i}=\dbinom{n+r+1}{r} $, basta porre nel nostro caso $ n=k-1 $.

[jordan]

Forse questo si può considerare anche come un metodo per dimostrare quella sommatoria.

Esattamente..