Sulla funzione di partizione!
Sera forum, ho una domanda molto semplice da porre 
:
E' possibile calcolare il numero di partizioni di un numero, conoscendo le partizioni dei numeri precedenti?
Esempio, se voglio calcolare le partizioni di $20$, posso arrivarci partendo dalle partizioni di tutti i numeri precedenti?;
2° Esempio: se voglio calcolare le partizioni di $8$, posso arrivarci conoscendo le partizioni di $1,2,3,4,5,6,7$?;
Oppure "attualmente" ogni nuova partizione deve ancora essere fatta una per una?
Grazie a quelli che risponderanno
[size=150]P.S.[/size]
Questa invece è la mia formula, che permette di calcolare le partizioni di un qualunque numero $n$ conoscendo le partizioni di tutti i numeri fino a $n-2$... un esempio col numero $12$:
$P(12)=sum_(k=6)^(10)(P(k))- sum_(k=0)^(4)(P(k))- sum_(k=0)^(3)(P(k))- sum_(k=0)^(1)(P(k)) - (P(7,3)+P(6,4)+P(5,4)) +1$
$P(12)=(11+15+22+30+42)-(1+1+2+3+5)-(1+1+2+3)-(1+1)-(8+9+6)+1$
$P(12)=120-12-7-2-23+1=77$
(Dove $P(a,b)$ è il numero di partizioni di $a$ in cui non compaiono interi maggiori di $b$)
Come potete notare, ho calcolato le partizioni di $12$ senza nemmeno citare quelle di $11$ o di $12$ stesso: la formula ancora non la posto, perché è intricata, e vorrei prima semplificarla: posso però dirvi, che funziona per qualunque $n$
Qui sotto spoiler anche quella del $10$:
(E qui appunto richiedo: esisteva già una formula che permette di trovare le partizioni di un numero, senza usare il numero stesso o partizioni successive? )
[size=150]P.P.S.[/size]
Ho cercato meglio, ed ho scoperto che ne esiste già una simile
e vabbeh
:E' possibile calcolare il numero di partizioni di un numero, conoscendo le partizioni dei numeri precedenti?
Esempio, se voglio calcolare le partizioni di $20$, posso arrivarci partendo dalle partizioni di tutti i numeri precedenti?;
2° Esempio: se voglio calcolare le partizioni di $8$, posso arrivarci conoscendo le partizioni di $1,2,3,4,5,6,7$?;
Oppure "attualmente" ogni nuova partizione deve ancora essere fatta una per una?
Grazie a quelli che risponderanno
[size=150]P.S.[/size]
Questa invece è la mia formula, che permette di calcolare le partizioni di un qualunque numero $n$ conoscendo le partizioni di tutti i numeri fino a $n-2$... un esempio col numero $12$:
$P(12)=sum_(k=6)^(10)(P(k))- sum_(k=0)^(4)(P(k))- sum_(k=0)^(3)(P(k))- sum_(k=0)^(1)(P(k)) - (P(7,3)+P(6,4)+P(5,4)) +1$
$P(12)=(11+15+22+30+42)-(1+1+2+3+5)-(1+1+2+3)-(1+1)-(8+9+6)+1$
$P(12)=120-12-7-2-23+1=77$
(Dove $P(a,b)$ è il numero di partizioni di $a$ in cui non compaiono interi maggiori di $b$)
Come potete notare, ho calcolato le partizioni di $12$ senza nemmeno citare quelle di $11$ o di $12$ stesso: la formula ancora non la posto, perché è intricata, e vorrei prima semplificarla: posso però dirvi, che funziona per qualunque $n$
Qui sotto spoiler anche quella del $10$:
(E qui appunto richiedo: esisteva già una formula che permette di trovare le partizioni di un numero, senza usare il numero stesso o partizioni successive? )
[size=150]P.P.S.[/size]
Ho cercato meglio, ed ho scoperto che ne esiste già una simile
e vabbeh
Risposte
"Luca97":
Andre' non è che ti riferisci a questo http://it.wikipedia.org/wiki/Partizione_di_un_intero
si, ma c'è solo la stima asintotica su wikipedia: volevo sapere, se esiste una formula esatta
Non lo sò; però se non ci fosse meglio per te . Daje sotto
. Daje sotto
Ecco il meglio che sono riuscito a fare:
Estendiamo questa "funzione di partizione" in questa funzione più generale:
Sia $P(n,k)$ il numero di partizioni dell'intero $n$ in cui NON compaiono interi maggiori di $k$ ($n,k \in \mathbb{N}$).
Allora ho che:
$P(n,k)= { ( 1 \qquad\text{se}\qquad n=k=0 ),( 0 \qquad\text{se}\qquad n>0 \quad\text{ e }\quad k=0 ),( P(n,n) \qquad\text{se}\qquad n=k ):} $
Il perché di questo è abbastanza intuitivo, quindi mi risparmio di spiegarvelo
(ma se me lo chiedete sarò felice di farlo )
Così se vogliamo sapere il numero delle partizioni di $20$ (per esempio) dobbiamo andare a calcolarci $P(20,20)$. Come fare?
Semplicemente si calcolano, in ordine, i valori di
$P(0,0), P(0,1), P(0,3), ... , P(0,19), P(0,20)$
$P(1,0), P(1,1), P(1,3), ... , P(1,19), P(0,20)$
$P(2,0), P(2,1), P(2,3), ... , P(2,19), P(2,20)$
$...$
$P(18,0), P(18,1), P(18,3), ... , P(18,19), P(18,20)$
$P(19,0), P(19,1), P(19,3), ... , P(19,19), P(19,20)$
$P(20,0), P(20,1), P(20,3), ... , P(20,19), P(20,20)$
Il calcolo di ognuno di essi è facile perché si basa su valori già calcolati.
(In realtà poi non c'è bisogno di calcolarli proprio tutti se sei furbo, infatti quelli veramente necessari sono circa la metà. Poi se sei veramente in gamba puoi ridurti a calcolarne solo un po' più di un quarto...)
Insomma, da fare a mano magari è un po' noiosetto, ma come algoritmo da fare eseguire al computer mi sembra decente, e soprattutto più veloce che andare a trovare tutte le partizioni possibili.
Estendiamo questa "funzione di partizione" in questa funzione più generale:
Sia $P(n,k)$ il numero di partizioni dell'intero $n$ in cui NON compaiono interi maggiori di $k$ ($n,k \in \mathbb{N}$).
Allora ho che:
$P(n,k)= { ( 1 \qquad\text{se}\qquad n=k=0 ),( 0 \qquad\text{se}\qquad n>0 \quad\text{ e }\quad k=0 ),( P(n,n) \qquad\text{se}\qquad n
Il perché di questo è abbastanza intuitivo, quindi mi risparmio di spiegarvelo
(ma se me lo chiedete sarò felice di farlo
)Così se vogliamo sapere il numero delle partizioni di $20$ (per esempio) dobbiamo andare a calcolarci $P(20,20)$. Come fare?
Semplicemente si calcolano, in ordine, i valori di
$P(0,0), P(0,1), P(0,3), ... , P(0,19), P(0,20)$
$P(1,0), P(1,1), P(1,3), ... , P(1,19), P(0,20)$
$P(2,0), P(2,1), P(2,3), ... , P(2,19), P(2,20)$
$...$
$P(18,0), P(18,1), P(18,3), ... , P(18,19), P(18,20)$
$P(19,0), P(19,1), P(19,3), ... , P(19,19), P(19,20)$
$P(20,0), P(20,1), P(20,3), ... , P(20,19), P(20,20)$
Il calcolo di ognuno di essi è facile perché si basa su valori già calcolati.
(In realtà poi non c'è bisogno di calcolarli proprio tutti se sei furbo, infatti quelli veramente necessari sono circa la metà. Poi se sei veramente in gamba puoi ridurti a calcolarne solo un po' più di un quarto...)
Insomma, da fare a mano magari è un po' noiosetto, ma come algoritmo da fare eseguire al computer mi sembra decente, e soprattutto più veloce che andare a trovare tutte le partizioni possibili.
"milizia96":
Ecco il meglio che sono riuscito a fare:
Estendiamo questa "funzione di partizione" in questa funzione più generale:
Sia $P(n,k)$ il numero di partizioni dell'intero $n$ in cui NON compaiono interi maggiori di $k$ ($n,k \in \mathbb{N}$).
Allora ho che:
$P(n,k)= { ( 1 \qquad\text{se}\qquad n=k=0 ),( 0 \qquad\text{se}\qquad n>0 \quad\text{ e }\quad k=0 ),( P(n,n) \qquad\text{se}\qquad n=k ):} $
Il perché di questo è abbastanza intuitivo, quindi mi risparmio di spiegarvelo
(ma se me lo chiedete sarò felice di farlo
Così se vogliamo sapere il numero delle partizioni di $20$ (per esempio) dobbiamo andare a calcolarci $P(20,20)$. Come fare?
Semplicemente si calcolano, in ordine, i valori di
$P(0,0), P(0,1), P(0,3), ... , P(0,19), P(0,20)$
$P(1,0), P(1,1), P(1,3), ... , P(1,19), P(0,20)$
$P(2,0), P(2,1), P(2,3), ... , P(2,19), P(2,20)$
$...$
$P(18,0), P(18,1), P(18,3), ... , P(18,19), P(18,20)$
$P(19,0), P(19,1), P(19,3), ... , P(19,19), P(19,20)$
$P(20,0), P(20,1), P(20,3), ... , P(20,19), P(20,20)$
Il calcolo di ognuno di essi è facile perché si basa su valori già calcolati.
(In realtà poi non c'è bisogno di calcolarli proprio tutti se sei furbo, infatti quelli veramente necessari sono circa la metà. Poi se sei veramente in gamba puoi ridurti a calcolarne solo un po' più di un quarto...)
Insomma, da fare a mano magari è un po' noiosetto, ma come algoritmo da fare eseguire al computer mi sembra decente, e soprattutto più veloce che andare a trovare tutte le partizioni possibili.
Molto, molto interessante
Ma vedo che comunque, alla fine, hai fatto uso della partizione del numero che stavi cercando
Io cercavo un modo senza utilizzare il numero stesso, altrimenti è inutile Io, invece, ho trovato un modo per calcolare le partizioni di un numero $n$, se conosco tutte le partizioni fino a $n-2$ (per calcolare le partizioni di $20$, mi basta sapere le partizioni di tutti i numeri fino a $18$), per far capire meglio, è possibile calcolare le partizioni di un numero $n$ partendo da:
$P(n)=sum_(k=0)^(n-2)(P(k))$
e poi aggiungendo valori calcolabili con la formula che sto ancora semplificando (la tua funzione più generale mi sta aiutando molto)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo