Quante sono le soluzioni intere non negative (x1, x2) di x1+x2 = 3? 3+0, 2+1, 1+2, 0+3 sono le uniche somme di 2 interi non negativi che
hanno come risultato 3; sono 4. Quante sono le soluzioni intere non negative (x1, x2, x3) di x1+x2+x3 = 3? 3+0+0, 2+1+0, 2+0+1, 1+2+0, 1+1+1, 1+0+2,
0+3+0, 0+2+1, 0+1+2, 0+0+3 sono le somme di 3 interi non negativi che hanno come risultato 4; sono 10. Quante sono le soluzioni intere non negative
x1+x2+x3+x4 = 10?
Ho, in pratica, da piazzare tra 10 barre "||||||||||" 3 simboli "+". Ad esempio 3+0+2+5 lo posso pensare come "|||++||+|||||",
ossia come una opportuna scelta di 3 posti tra i 13 possibili.
Le soluzioni sono tante quante le possibili combinazioni di 13 elementi 3 a 3, ossia C(13,3): 13*12*11/(3*2*1) = 13*2*11 = 286.
Trova una formula per esprimere quante sono le soluzioni intere non negative di x1+x2+
+xK = N con N intero maggiore o eguale a K.
Verifica la soluzione per qualche caso costruendo e utilizzando un programma.
Ho K−1 simboli "+" da piazzare tra N barre. Ossia ho N+K−1 posti tra cui sceglierne K−1. Quindi ho:
C(N+K−1, K−1) soluzioni.
Verifichiamo se i conti tornano nel caso degli esempi fatti.
K = 2, N = 3, C(3+2−1, 1) = 4: OK.
K = 3, N = 3, C(3+3−1, 3−1) = C(5, 2) = 5*4/2*1 = 10: OK.
K = 4, N = 10, C(10+4−1, 4−1) = C(13, 3): OK.
Verifichiamo il calcolo ad esempio con R:
n <- 10; k <- 4; s <- 0 for(a in 0:n) for(b in 0:n) for(c in 0:n) for(d in 0:n) s <- ifelse(a+b+c+d==n,s+1,s); s # 286 choose(n+k-1,k-1) # 286 n <- 8; k <- 5; s <- 0 for(a in 0:n) for(b in 0:n) for(c in 0:n) for(d in 0:n) for(e in 0:n) s <- ifelse(a+b+c+d+e==n,s+1,s); s # 495 choose(n+k-1,k-1) # 495
Il calcolo di C(n-k+1, k-1) posso effettuarlo anche con questa calcolatrice: