Newsgroup: it.hobby.enigmi
Titolo: Quante somme ?

Ottime le soluzioni a "Terne di quadrati" Gianni,  "Quadrato nel
triangolo" Paolo e Massimo, "Esami" Fabio e Vinny.
--------------------------------
X+Y+Z+T = 13
Quante soluzioni ci sono (non orientate)  se X,Y,Z,T sono interi
positivi non necessariamente differenti?
Per non orientate si intende che 1+1+2+9 e' differente da 1+9+1+2.
Piu' in generale:
X+Y+......+Z+T = n ??
:) dario

X+Y+......+Z+T = n ??
spoiler
\V/
 V
\V/
 V
\V/
 V
\V/
 V
\V/
 V
\V/
 V
\V/
 V
\V/
 V
\V/
 V
\V/
 V
\V/
 V
Presumo tu intenda X_1+..+X_k=n, con k<=n fissato a priori.
Pensiamo ad una catena di n anelli: se apriamo la catena in k-1 punti
qualsiasi degli n-1 possibili avremo la nostra suddivisione in k catenelle
piu' corte.
Lo possiamo fare in C(n-1,k-1)=(n-1)!/((k-1)!(n-k)!) modi possibili.
Nel primo esempio (n=13 e k=4) ci sono 220 modi possibili.
Ciao, Silv:o)

 X+Y+......+Z+T = n ??
Boh !!!
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
Dovrebbero essere  212.
Dopo aver calcolato empiricamente le soluzioni *orientate* (sono 18),
per ciascuna di esse si possono calcolare le permutazioni possibili
che sono:
in assenza di ripetizioni                  = 4!                = 24
con una coppia di valori ripetuti     = 4!/2!            = 12
con due coppie di valori ripetuti     = 4!/(2! * 2!)  =   6
con una terna di valori ripetuti         = 4!/3!           =   4
con quattro valori uguali                   = 4!/4!           =   1
Nel nostro caso abbiamo:
  3 casi senza ripetizioni        =   3 * 24 =   72
10 casi con una coppia         = 10 * 12 = 120
  5 casi con una terna             =   5 *   4 =   20
Per un totale, appunto di 212.
Non sono a conoscenza di un metodo per calcolare *non* empiricamente
le soluzioni orientate, senza il quale non è possibile la
generalizzazione.
Ciao
Gianni

 X+Y+......+Z+T = n ??
)
)spoiler(
)
)
)
)
)
)
)
)
)
)
)
)
Il problema è solo in apparenza reso più difficile dal fatto che le
variabili possono assumere solo valori maggiori o uguali ad 1. In realtà,
dal momento che ogni variabile deve valere come minimo 1, ed essendo m il
numero di variabili, il problema si riduce a trovare le soluzioni di questa
equazione:
x1 + x2 + ... + xm = n-m
Con la generica variabile xi che può assumere valori interi positivi
compreso lo 0.
A questo punto la risposta è semplice: (n-1 m-1) intendendo così il
coefficiente binomiale.
Infatti, ragionando prima con 2 variabili, poi con 3, ecc... si ha che il
numero di soluzioni è pari a:
Si(0,n-m, Si(0,n-m, ... Si(0,n-m,i)..))
Con Si(a,b,f(i)) intendo la sommatoria con indice i da a a b di f(i). A
questo punto mi viene in aiuto il caro Tartaglia col suo bel triangolo...
ricordando infatti che data una colonna p, la somma dei primi q termini dava
il termina di posto (p+1, q+1), e da qui si arriva alla soluzione.
MaxArt

 Lo possiamo fare in C(n-1,k-1)=(n-1)!/((k-1)!(n-k)!) modi possibili.
Complimenti Silvio, la tua e' una soluzione *davvero brillante*!
Molto molto carina l'idea della catena di n anelli.
Hai una soluzione altrettanto bella anche per il caso in cui
l'ordine degli addendi non abbia importanza?
Saluti,
         iant

 Per un totale, appunto di 212.
A me risultano invece 
  3 casi senza ripetizioni
 11 casi con una coppia
  4 casi con una terna
e precisamente:
 10  1  1  1
  7  2  2  2
  4  4  4  1
  4  3  3  3   con   4! / 3! = 4   disposizioni
  9  2  1  1
  8  3  1  1
  8  2  2  1
  7  4  1  1
  6  5  1  1
  6  3  3  1
  6  3  2  2
  5  5  2  1
  5  4  2  2
  5  3  3  2
  4  4  3  2   con   4! / 2! = 12   disposizioni
  7  3  2  1
  6  4  2  1
  5  4  3  1   con   4! / 1! = 24   disposizioni
Quindi la soluzione e'  4*4 + 11*12 + 3*24 = 220
come brillantemente anticipato da Silvio.
Saluti,
         iant

 l'ordine degli addendi non abbia importanza?
Magari !!
Le partizioni non orientate sono semplici da calcolare. Ad es. Quante
sono tutte le possibili partizioni di 10 ?
Come ha fatto Silvio , scrivo 10 cifre "1"
1 1 1 1 1 1 1 1 1 1
Supponiamo che il segno | serva a spezzare la catena, allora questa
notazione:
1 1|1 1 1|1 1 1 1 1  corrisponde a 2+3+5.
Se consideriamo che nei nove spazi posso mettere o non mettere il segno
di separazione, ho 2^9 possibili partizioni.
In generale per il numero n sono 2^(n-1).
Il computo delle partizioni orientate, invece ha dato filo da torcere ai
grandi, Eulero, Gauss.... Credo ci siano solo funzioni piuttosto
complesse che approssimano il risultato, date da Ramanujan, Rademacher
ed altri.
ciao :)dario

 wrote in message
38787d36...@news.libero.it...

Hai ragione, l'ora tarda, a volte, gioca brutti scherzi.
Ciao
Gianni

ed altri.
Per dare un'idea, ecco l'approssimazione di Ramanujan:
              _____
        e^pi*V2*n/3
p(n) = ---------_----
           4*n*V3
cosa centri pi greco o e lo sa solo lui. Mi risulta che Rademacher abbia
dato una formula esatta, che non riporto perche' ci vorrebbe un editor
avanzato, e poi la meta' dei simboli neanche li capisco, ci sono derivate,
funzioni iperboliche e radici 24esime dell'unita'...
Comunque il problema di dario era leggermente diverso, perche' si chiedevano
le partizioni in un numero k fissato di addendi. Magari e' piu' semplice, ci
pensero'.
Ciao, Silv:o)

pensero'.
Come non detto:non puo' essere molto piu' semplice, perche' altrimenti il
problema delle partizioni sarebbe risolto sommando su tutti i possibili k da
1 a n, e vi assicuro che nel formulone di Rademacher c'e' molto di piu' di
una sommatoria di cose semplici.
Ciao, Silv:o)

 wrote in message
85efm4$s2v$1...@news.mclink.it...

Comecome?
Stiamo parlando della stessa cosa?
Io credo di aver risposto correttamente al quesito di Dario.
MaxArt

 Io credo di aver risposto correttamente al quesito di Dario.
Forse ti sei perso qualche messaggio.
Dario chiedeva il numero di partizioni possibili "non orientate" (nel senso
che l'ordine degli addendi discrimina) del 13 utilizzando 4 addendi.
Sia tu che io abbiamo risposto correttamente, seppur con metodi leggermente
differenti. E' risultato che nel caso generico di k addendi che sommati
danno n, ci sono (n-1,k-1) (coeff. binomiale) possibili partizioni.
Poi si e' passati al problema di contare le partizioni "orientate", ovvero
quelle nelle quali l'ordine degli addendi non conta, e Dario ha ricordato
che e' un problema *tosto* che ha dato del filo da torcere a eminenti
matematici.
Lui parlava del caso di partizioni in un numero qualsiasi di addendi, al che
mi e' venuto il dubbio che forse fissando il numero di addendi (4 per
formare il 13 dell'esempio), le cose sarebbero state magari piu' semplici.
Ma ho subito fatto retromarcia, visto che avevo visto scritto su un libro un
formulone davvero terribile (esponenziali, derivate, pi grechi, omeghe e
pure un seno iperbolico) per il calcolo nel caso generale, e se fosse
risultato possibile risolvere in termini semplici il problema con un numero
fisso di addendi, allora sarebbe bastata una sommatoria di cose semplici.
Ciao, Silv:o)