Newsgroup: it.hobby.enigmi
Titolo: Terne di addendi

Mi è stato posto un problema che non riesco a risolvere e che vi propongo:
Trovare una formula generale che fornisca il numero di terne di addendi (con 
ripetizione) che danno come somma un numero intero k. Estendere poi la 
formula per n-ple di addendi.
Grazie per l' aiuto
Claudio 

 Mi č stato posto un problema che non riesco a risolvere e che vi propongo:

Ciao,
sulle terne io direi che possa essere (k-1)*(k-2)/2.
Empiricamente si vede che p. es. le terne a somma 5 sono 6 (113, 122, 131,
212, 221, 311).
Oppure che le terne a somma 6 sono 10 (114, 123, 132, 141, 213, 222, 231,
312, 321, 411).
Generalizzando (con k>n ovvio) dovrebbe essere
(k-1)*(k-2)*...(k-n+1)/(n-1)*(n-2)*...(n-n+1).
Per esempio le quaterne a somma 6 (con ripetizione) sarebbero 5*4*3/3*2 =
10, cosa che in effetti sono (1113, 1122, 1131, 1212, 1221, 1311, 2112,
2121, 2211, 3111).
Le cinquine invece a somma 7 sarebbero 6*5*4*3/4*3*2 = 15 (e infatti sono
11113, 11122, 11131, 11212, 11221, 11311, 12112, 12121, 12211, 13111, 21112,
21121, 21211, 22111, 31111).
Saluti
Francesco

 312, 321, 411).
No, forse non mi sono spiegato bene, ma il problema prevede il computo delle 
combinazioni con ripetizione e non di disposizioni con ripetizione. Vale a 
dire che ad esempio per quanto riguarda le terne a somma 5 sono solo 2 
(113,122) perchč altrimenti ognuna di esse sarebbe contata 2 volte e 
analogamente quelle a somma 6 sono solo 3   (114,123,222). Pensavo di 
utilizzare il calcolo combinatorio ma se considero le combinazioni con 
ripetizione non so come escludere quelle che per somma danno numeri minori 
di k.
Grazie comunque, non č un problema semplice.
Ciao,
Claudio

 a(n) = 1 + a(n-2) + a(n-3) - a(n-5)
che risolta da Mathematica dà la formula esplicita:
(1/72) [6n^2 + 16 Cos(2n Pi/3) -7 - 9(-1)^n]
Maurizio

 Maurizio
Bello!
Io so solo usare carta e penna...
Ho provato con 4 partizioni e dovrebbe essere:
a(n)=a(n-2)+a(n-3)+a(n-4)-a(n-5)-a(n-6)-a(n-7)+a(n-9)+1
Riesci a trovare una formula che generalizza per n addendi?
Nino 

> (1/72) [6n^2 + 16 Cos(2n Pi/3) -7 - 9(-1)^n]
Potreste cortesemente spiegarmi come siete arrivati rispettivamente alle due 
formulazioni ?
Grazie
Claudio 


Io empiricamente.
Ho calcolato (è molto semplice...) il numero di casi possibili (somma di
tre interi) per i primi numeri, che riporto ancora:
    Numero          3   4   5   6   7   8   9    10    11    12   13   14 
15
n. terne addendi    1   1   2   3   4   5   7     8    10    12   14   16 
19
e per tentativi trovato  a(n) = 1 + a(n-2) + a(n-3) - a(n-5)
Se vuoi, con 4 addendi si può fare questa tabellina (salvo errori):
 Numero         4   5   6   7   8   9   10   11    12   13   14    15    16
n. quaterne     1   1   2   3   5   6    9   11    15   18   23    27    34

 Riesci a trovare una formula che generalizza per n addendi?
Non saprei proprio. Però c'è anche un modo diretto, non ricorsivo, di
attaccare il problema. Provo ad illustrarlo nel caso delle terne.
Supponiamo dunque che 
i + j + k = n
e per non contare due volte la stessa terna imponiamo che
i <= j <= k.
E' chiaro che i può assumere i valori da 1 fino alla parte intera di
n/3, cioè fino a
x = int[n/3],
mentre j può assumere i valori da i fino a int[(n-i)/2] e k è dato una
volta fissati i e j.
Si tratta quindi di valutare la sommatoria:
somma[ int[(n-i)/2] - i + 1 ] per i che va da 1 a x.
Sfruttando il fatto che
int[(n-i)/2] = (n-i)/2 - [1-(-1)^(n-i)]/4
la somma si calcola anche a mano e dà:
(2nx - 3x^2)/4 + (-1)^n ((-1)^x-1)/8
che è un'altra versione della formula che avevo dato nel mio post
precedente.
Teoricamente la stessa strada si può percorrere per qualunque valore di
n, anche se in pratica la strada si fa subito ardua...
Maurizio