Funzione partizione di un intero e funzione generatrice
Salve, qualcuno può aiutarmi a capire questa dimostrazione che ho trovato?
Dimostra che il numero di partizioni di un numero intero positivo \(n \) scrivibili con numeri distinti è uguale al numero di partizioni di \( n \) con numeri dispari.
Sia \( \mathcal{D}(n) \) il numero di partizioni di \(n \) con numeri distinti e \( \mathcal{O}(n) \) il numero di partizioni con numeri dispari allora abbiamo che
\[ \sum\limits_{n \geq0} \mathcal{D}(n)q^n = \prod\limits_{n=1}^{\infty} (1+q^n) = \prod\limits_{n=1}^{\infty} \frac{1-q^{2n}}{1-q^{n}} = \prod\limits_{n=1}^{\infty} \frac{1}{1-q^{2n-1}} =\sum\limits_{n \geq0} \mathcal{O}(n)q^n\]
In particolare non capisco il motivo per cui
\[ \sum\limits_{n \geq0} \mathcal{D}(n)q^n = \prod\limits_{n=1}^{\infty} (1+q^n) \]
e il motivo per cui
\[ \prod\limits_{n=1}^{\infty} \frac{1}{1-q^{2n-1}} =\sum\limits_{n \geq0} \mathcal{O}(n)q^n\]
Inoltre cos'è \( q \) ?
Ho cercato ma mi dice che è la funzione generatrice, ma non vedo il motivo, ne ho trovato una dimostrazione di queste uguaglianze. Grazie mille.
ps: spero sia la sezione giusta, l'esercizio ce lo ha dato il prof di analisi ma mi sembra più un esercizio di teoria dei numeri.
Dimostra che il numero di partizioni di un numero intero positivo \(n \) scrivibili con numeri distinti è uguale al numero di partizioni di \( n \) con numeri dispari.
Sia \( \mathcal{D}(n) \) il numero di partizioni di \(n \) con numeri distinti e \( \mathcal{O}(n) \) il numero di partizioni con numeri dispari allora abbiamo che
\[ \sum\limits_{n \geq0} \mathcal{D}(n)q^n = \prod\limits_{n=1}^{\infty} (1+q^n) = \prod\limits_{n=1}^{\infty} \frac{1-q^{2n}}{1-q^{n}} = \prod\limits_{n=1}^{\infty} \frac{1}{1-q^{2n-1}} =\sum\limits_{n \geq0} \mathcal{O}(n)q^n\]
In particolare non capisco il motivo per cui
\[ \sum\limits_{n \geq0} \mathcal{D}(n)q^n = \prod\limits_{n=1}^{\infty} (1+q^n) \]
e il motivo per cui
\[ \prod\limits_{n=1}^{\infty} \frac{1}{1-q^{2n-1}} =\sum\limits_{n \geq0} \mathcal{O}(n)q^n\]
Inoltre cos'è \( q \) ?
Ho cercato ma mi dice che è la funzione generatrice, ma non vedo il motivo, ne ho trovato una dimostrazione di queste uguaglianze. Grazie mille.
ps: spero sia la sezione giusta, l'esercizio ce lo ha dato il prof di analisi ma mi sembra più un esercizio di teoria dei numeri.
Risposte
Intuitivamente ho capito
\[ \sum\limits_{n \geq0} \mathcal{D}(n)q^n = \prod\limits_{n=1}^{\infty} (1+q^n) \]
quel polinomio con variabile \(q \) a destra per ottenere un grado \( q^n \) sommo i coefficienti dei gradi tutti distinti la cui somma mi da \(n \).
Ad esempio per \( \mathcal{D}(6)q^6 \) sommo \( q^{6} + q^{5+1} + q^{4+2}+q^{3+2+1} \) e siccome i coefficienti sono tutti 1 allora equivale a contare i modi di scrivere \(6 \) come somma di numeri distinti.
Mentre invece l'altro non l'ho mica capito dovrei avere lo stesso principio
\[ \prod\limits_{n=1}^{\infty} \frac{1}{1-q^{2n-1}}=\sum\limits_{n \geq0} \mathcal{O}(n)q^n \]
Se voglio il \( \mathcal{O}(6)q^6 \), dovrebbe essere uguale al modo di contare il numero di partizioni in numeri dispari quindi dovrebbe essere uguale a \( q^{5+1} + q^{3+3} + q^{3+1+1+1} + q^{ 1+1+1+1+1+1} \)
Ma non vedo come mai
\[ \sum\limits_{n \geq0} \mathcal{D}(n)q^n = \prod\limits_{n=1}^{\infty} (1+q^n) \]
quel polinomio con variabile \(q \) a destra per ottenere un grado \( q^n \) sommo i coefficienti dei gradi tutti distinti la cui somma mi da \(n \).
Ad esempio per \( \mathcal{D}(6)q^6 \) sommo \( q^{6} + q^{5+1} + q^{4+2}+q^{3+2+1} \) e siccome i coefficienti sono tutti 1 allora equivale a contare i modi di scrivere \(6 \) come somma di numeri distinti.
Mentre invece l'altro non l'ho mica capito dovrei avere lo stesso principio
\[ \prod\limits_{n=1}^{\infty} \frac{1}{1-q^{2n-1}}=\sum\limits_{n \geq0} \mathcal{O}(n)q^n \]
Se voglio il \( \mathcal{O}(6)q^6 \), dovrebbe essere uguale al modo di contare il numero di partizioni in numeri dispari quindi dovrebbe essere uguale a \( q^{5+1} + q^{3+3} + q^{3+1+1+1} + q^{ 1+1+1+1+1+1} \)
Ma non vedo come mai
Okay ho capito.
Il problema diventa simile a quest'altro, supponiamo di avere in un portafoglio 4 monete da 1 euro, 5 monete da 2 euro e 3 banconote da 5 euro. In quanti modi diversi possiamo pagare un oggetto che costa 15 euro, con il nostro portafoglio?
La soluzione di questo problema è data da
\[ x_1 + x_2 +x_3 = 15 \]
con \( x_1 \in \{ 0,1,2,3,4\} \), \( x_2 \in \{ 0,2,4,6,8,10\} \), \( x_3 \in \{ 0,5,10,15\} \).
Pertanto definendo \( p_1(x)= 1+x+x^2+x^3+x^4 \), \( p_2(x)= 1+x^2+x^4+x^6+x^8+x^{10} \) e \( p_3(x)= 1+x^5+x^{10}+x^{15} \) abbiamo che la risposta, in quanti modi diversi possiamo pagare un oggetto che costa 15 euro con il nostro portafoglio è dato dal coefficiente di \( x^{15} \) del polinomio \(p(x)= p_1(x) p_2(x) p_3(x) \).
In modo equivalente con le nostre partizioni dispari abbiamo un infinità di monete che valgono 1, un infinità di monete che valgono 3, un infinità di monete che valgono 5, etc..
Pertanto definendo
\[ p_1(x)= 1+x +x^2 +x^3 + \ldots\]
\[ p_3(x) = 1+x^3+x^6 +x^9 + \ldots \]
\[ \vdots\]
\[ p_{2n-1} (x) = 1+x^{2n-1} + x^{2(2n-1)} + \ldots \]
Dunque, con \( x \) sufficientemente piccolo tale che ciascun \(p_{2n-1}(x) \) converge, il numero delle partizioni dispari di \(k \) è dato dal coefficiente di \( x^{k} \) all'interno del polinomio
\[ \prod\limits_{n=1}^{\infty} p_n(x) = \left( 1+x +x^2 \ldots \right) \left( 1+x^3+x^6 + \ldots \right)\cdot \ldots= \frac{1}{1-x} \frac{1}{1-x^3} \frac{1}{1-x^5} \cdot \ldots = \prod\limits_{n=1}^{\infty} \frac{1}{1-x^{2n-1}} \]
Il problema diventa simile a quest'altro, supponiamo di avere in un portafoglio 4 monete da 1 euro, 5 monete da 2 euro e 3 banconote da 5 euro. In quanti modi diversi possiamo pagare un oggetto che costa 15 euro, con il nostro portafoglio?
La soluzione di questo problema è data da
\[ x_1 + x_2 +x_3 = 15 \]
con \( x_1 \in \{ 0,1,2,3,4\} \), \( x_2 \in \{ 0,2,4,6,8,10\} \), \( x_3 \in \{ 0,5,10,15\} \).
Pertanto definendo \( p_1(x)= 1+x+x^2+x^3+x^4 \), \( p_2(x)= 1+x^2+x^4+x^6+x^8+x^{10} \) e \( p_3(x)= 1+x^5+x^{10}+x^{15} \) abbiamo che la risposta, in quanti modi diversi possiamo pagare un oggetto che costa 15 euro con il nostro portafoglio è dato dal coefficiente di \( x^{15} \) del polinomio \(p(x)= p_1(x) p_2(x) p_3(x) \).
In modo equivalente con le nostre partizioni dispari abbiamo un infinità di monete che valgono 1, un infinità di monete che valgono 3, un infinità di monete che valgono 5, etc..
Pertanto definendo
\[ p_1(x)= 1+x +x^2 +x^3 + \ldots\]
\[ p_3(x) = 1+x^3+x^6 +x^9 + \ldots \]
\[ \vdots\]
\[ p_{2n-1} (x) = 1+x^{2n-1} + x^{2(2n-1)} + \ldots \]
Dunque, con \( x \) sufficientemente piccolo tale che ciascun \(p_{2n-1}(x) \) converge, il numero delle partizioni dispari di \(k \) è dato dal coefficiente di \( x^{k} \) all'interno del polinomio
\[ \prod\limits_{n=1}^{\infty} p_n(x) = \left( 1+x +x^2 \ldots \right) \left( 1+x^3+x^6 + \ldots \right)\cdot \ldots= \frac{1}{1-x} \frac{1}{1-x^3} \frac{1}{1-x^5} \cdot \ldots = \prod\limits_{n=1}^{\infty} \frac{1}{1-x^{2n-1}} \]
@3m0o
[ot]Bravo
, sei riuscito a "trasformare" quella soluzione terra-terra in una molto formale 
[/ot]
Cordialmente, Alex
[ot]Bravo
, sei riuscito a "trasformare" quella soluzione terra-terra in una molto formale [/ot]Cordialmente, Alex
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo