Pagina 1 di 1
$x_1+x_2+\ldots+x_k \le n$
Inviato: 14 gen 2013, 13:43
da 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 \]
Re: $x_1+x_2+\ldots+x_k \le n$
Inviato: 14 gen 2013, 14:08
da 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} $
Re: $x_1+x_2+\ldots+x_k \le n$
Inviato: 14 gen 2013, 16:34
da jordan
Hawk ha scritto: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è? (*)
Hawk ha scritto: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 (*)..
Re: $x_1+x_2+\ldots+x_k \le n$
Inviato: 14 gen 2013, 23:10
da simone256
Re: $x_1+x_2+\ldots+x_k \le n$
Inviato: 14 gen 2013, 23:44
da Hawk
Visto che ti trovi dimostra anche l'uguaglianza della sommatoria
.
Re: $x_1+x_2+\ldots+x_k \le n$
Inviato: 14 gen 2013, 23:44
da jordan
La prima risposta è giusta, ma la seconda ancora non è giustificata..
Re: $x_1+x_2+\ldots+x_k \le n$
Inviato: 15 gen 2013, 14:08
da 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.
Re: $x_1+x_2+\ldots+x_k \le n$
Inviato: 15 gen 2013, 14:12
da 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 $.
Re: $x_1+x_2+\ldots+x_k \le n$
Inviato: 15 gen 2013, 14:14
da jordan
xXStephXx ha scritto:Forse questo si può considerare anche come un metodo per dimostrare quella sommatoria.
Esattamente..