Metodo del cerchio...
Determinare $r_k(n)=|{(a_1,a_2,...,a_k) \in NN^k|n=a_1+a_2+...+a_k}|$, in altre parole in quanti modi posso scrivere $n$ come somma di esattamente $k$ naturali considerando l'ordine?
Risposte
Beh, se ci pensi si tratta di inserire $n$ palline indistinguibili in $k$ contenitori, e cioè di combinazioni con ripetizione, quindi semplicemente $C_{k,n}^r = ((k+n-1),(n))$
Inoltre immagino che i contenitori siano indistinguibili (perché non conta l'ordine del vettore $(a_1,a_2,...,a_k)$, vero?), quindi bisogna ulteriormente dividere per $P_k$, sicché i modi in cui puoi effettuare l'operazione sono
$\frac{C_{k,n}^r}{P_k}$
Ho incluso la possibilità di usare lo 0 come addendo. Se non vuoi includerlo devi evidentemente mettere $k$ delle $n$ palline nei $k$ contenitori, sicché te ne restano altre $n-k$ da inserire, quindi.
$\frac{C_{k,n-k}^r}{P_k}$
Inoltre immagino che i contenitori siano indistinguibili (perché non conta l'ordine del vettore $(a_1,a_2,...,a_k)$, vero?), quindi bisogna ulteriormente dividere per $P_k$, sicché i modi in cui puoi effettuare l'operazione sono
$\frac{C_{k,n}^r}{P_k}$
Ho incluso la possibilità di usare lo 0 come addendo. Se non vuoi includerlo devi evidentemente mettere $k$ delle $n$ palline nei $k$ contenitori, sicché te ne restano altre $n-k$ da inserire, quindi.
$\frac{C_{k,n-k}^r}{P_k}$
Non si conosce la formula esatta, Hardy e Ramanujan (e 2 anni dopo Uspensky indipendentemente) hanno trovato un'approssimazione asintotica, vedi qui.
Il numero di partizioni di $n$ è uguale al numero di classi di coniugio del gruppo simmetrico $S_n$.
Il numero di partizioni di $n$ è uguale al numero di classi di coniugio del gruppo simmetrico $S_n$.
@Martino
Non si chiedeva il numero di partizione di $n$, a riguardo comunque ho letto che (non ricordo bene sinceramente) recentemente hanno trovato una formula.
@Aster
Si pure, ma c'è un metodo alternativo, il metodo del cerchio appunto. Questo metodo fu descritto per la prima volta in un articolo di Hardy e Ramanujan, e in seguito ripreso dallo stesso Hardy e dal collega Littlewood per affrontare vari problemi additivi tra cui la congettura di Goldbach.
In breve il metodo del cerchio consiste (nel nostro caso) nel trovare i coefficienti della serie di Laurent (o Taylor) di $f(z)=(\sum_{n=0}^{+\infty}z^n)^k$ centrata in $z=0$, questo lo si può fare proprio usando la definizione di coefficiente di Laurent.
Non si chiedeva il numero di partizione di $n$, a riguardo comunque ho letto che (non ricordo bene sinceramente) recentemente hanno trovato una formula.
@Aster
Si pure, ma c'è un metodo alternativo, il metodo del cerchio appunto. Questo metodo fu descritto per la prima volta in un articolo di Hardy e Ramanujan, e in seguito ripreso dallo stesso Hardy e dal collega Littlewood per affrontare vari problemi additivi tra cui la congettura di Goldbach.
In breve il metodo del cerchio consiste (nel nostro caso) nel trovare i coefficienti della serie di Laurent (o Taylor) di $f(z)=(\sum_{n=0}^{+\infty}z^n)^k$ centrata in $z=0$, questo lo si può fare proprio usando la definizione di coefficiente di Laurent.
I coefficienti di quella serie pero' sono dei binomiali facili da calcolare (perche' gli esponenti sono sempre positivi).
Viene proprio il coefficiente binomiale scritto da Aster nel secondo post.
In effetti, il numero di modi di scrivere $n$ come somma di $k$ naturali ($0$ compreso), considerandoli ordinati, e' proprio uguale al numero di monomi di grado $n$ in $k$ indeterminate, e questo numero e' $((k+n-1),(n))$.
Se ci si vuole dimenticare dell'ordine, la questione diventa molto piu' complicata e, come diceva Martino, non e' nota una formula chiusa. E' nota la funzione generatrice.
Viene proprio il coefficiente binomiale scritto da Aster nel secondo post.
In effetti, il numero di modi di scrivere $n$ come somma di $k$ naturali ($0$ compreso), considerandoli ordinati, e' proprio uguale al numero di monomi di grado $n$ in $k$ indeterminate, e questo numero e' $((k+n-1),(n))$.
Se ci si vuole dimenticare dell'ordine, la questione diventa molto piu' complicata e, come diceva Martino, non e' nota una formula chiusa. E' nota la funzione generatrice.
"Aster89":[/quote]
...quindi bisogna ulteriormente dividere per $ P_k $, sicché i modi in cui puoi effettuare l'operazione sono...
[quote="dan95"]@Aster
Si pure...
Non mi pare sia così: dividere per $ P_k $ sarebbe corretto solo se nelle k-ple non vi fossero ripetizioni.
Ciao
B.
Sinceramente credo che ci sia bisogno (almeno per far capire a me) di chiarire un po' la domanda. Io ho risposto come se fosse una cosa facile, ma evidentemente non ho colto pienamente la questione. Qualcuno può spiegarmi un po' meglio di che si sta parlando?
"dan95":Invece si parlava proprio di quello
@Martino
Non si chiedeva il numero di partizione di $n$
Ah forse no, la differenza è che tu conti l'ordine in cui sono disposti gli addendi. E' così?a riguardo comunque ho letto che (non ricordo bene sinceramente) recentemente hanno trovato una formula.Sarei curioso di vederla. Dove l'hai letto?
"Martino":Invece si parlava proprio di quello
[quote="dan95"]@Martino
Non si chiedeva il numero di partizione di $ n $
Ah forse no, la differenza è che tu conti l'ordine in cui sono disposti gli addendi. E' così?a riguardo comunque ho letto che (non ricordo bene sinceramente) recentemente hanno trovato una formula.Sarei curioso di vederla. Dove l'hai letto?[/quote]
Scusate sono stato poco preciso, intendevo dire somma di esattamente $k$ termini considerando l'ordine. Esempio:
4 può essere scritto in 5 modi come somma di due naturali, infatti 4=3+1=1+3=4+0=0+4=2+2.
La formula trovata con il metodo del cerchio è $((n+k-1),(k-1))$ naturalmente se non si considera l'ordine la questione si complica.
L'ho letto su Wiki nella voce Partizione di un intero verso la fine.
"orsoulx":[/quote]
[quote="Aster89"]...quindi bisogna ulteriormente dividere per $ P_k $, sicché i modi in cui puoi effettuare l'operazione sono...
[quote="dan95"]@Aster
Si pure...
Non mi pare sia così: dividere per $ P_k $ sarebbe corretto solo se nelle k-ple non vi fossero ripetizioni.
Ciao
B.[/quote]
Giusto
E sarebbe quindi questo il motivo per cui non c'è soluzione in forma chiusa?
"Aster89":
E sarebbe quindi questo il motivo per cui non c'è soluzione in forma chiusa?
Non stiamo cercando un colpevole. Riassumendo:
a) è semplice, basta un opportuno coefficiente binomiale, stabilire in quante maniere un intero n si può scrivere come somma di k naturali, a patto di considerare distinte due k-ple che differiscono solamente per la posizione occupata dagli addendi, chiamiamole d(n,k);
b) è complicato calcolare quante sono le partizione di n.
Supponiamo che sia semplice passare dalle d(n,k) alle u(n,k) dove le k-ple che differiscono solo per la posizione degli addendi sono conteggiate una sola volta.
Visto che fra le partizioni di n e u(n,n) esiste una corrispondenza biunivoca (basta aggiungere a ciascuna partizione quanti zeri servono per arrivare ad n addendi), la b sarebbe falsa.
Ciao
B.
Credo di essere stato io a generare confusione, scusate.
Comunque segnalo anche questo, che è collegato.
Comunque segnalo anche questo, che è collegato.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo