Ad esempio 5 = 5 = 4 + 1 = 3 + 2
Sia D(n) (dove D sta per "dispari") il numero di modi di scrivere n come somma di interi positivi dispari, senza contare l'ordine.
Ad esempio 5 = 5 = 3 + 1 + 1 = 1 + 1 + 1 + 1 + 1
Dimostrare che d(n) = D(n) !!
Partizioni dispari o distinte? E' uguale!
Partizioni dispari o distinte? E' uguale!
Sia d(n) (dove d sta per "distinte") il numero di modi di scrivere n (che è un intero) come somma di interi positivi distinti, senza contare l'ordine.
Ad esempio 5 = 5 = 4 + 1 = 3 + 2
Sia D(n) (dove D sta per "dispari") il numero di modi di scrivere n come somma di interi positivi dispari, senza contare l'ordine.
Ad esempio 5 = 5 = 3 + 1 + 1 = 1 + 1 + 1 + 1 + 1
Dimostrare che d(n) = D(n) !!
Ad esempio 5 = 5 = 4 + 1 = 3 + 2
Sia D(n) (dove D sta per "dispari") il numero di modi di scrivere n come somma di interi positivi dispari, senza contare l'ordine.
Ad esempio 5 = 5 = 3 + 1 + 1 = 1 + 1 + 1 + 1 + 1
Dimostrare che d(n) = D(n) !!
E' molto carino:
Infatti i due tipi di partizione sono in corrispondenza biunivoca.
Data una partizione a interi distinti posso associargli la partizione a interi dispari che si ottiene prendendo uno degli elementi e dividendolo in due elementi uguali e ripetendo questo fino a che non rimango con una partizione di elementi tutti dispari.
Questa corrispondenza è biunivoca, data una partizione in elementi dispari ne esiste una e soltanto una a interi distinti che può averla generata, come si vede facilmente dall'unicità della rappresentazione binaria.
Wow! Complimenti per la dimostrazione!
La mia era proprio bruttina... con le funzioni generatrici:
si riconosce facilmente che $ ~ (1+x)(1+x^2)(1+x^3)\ldots $ è la funzione generatrice per le partizioni in interi distinti e che $ ~ (1+x+x^2+\ldots)(1+x^3+x^6+\ldots)(1+x^5+x^10+\ldots)\ldots $ è la funzione generatrice per le partizioni in interi dispari.
Vogliamo dimostrare che sono uguali:
$ ~ (1+x)(1+x^2)(1+x^3)\ldots = \frac{1}{(1-x)(1-x^3)(1-x^5)\ldots} $
$ ~ (1+x)(1+x^2)(1+x^3)\ldots (1-x)(1-x^3)(1-x^5)\ldots = 1 $
Le riordino come:
$ ~ (1-x)(1+x)(1+x^2)(1+x^4)\ldots $$ (1-x^3)(1+x^3)(1+x^6)(1+x^{12})\ldots $$ (1-x^5)(1+x^5)(1+x^{10})(1+x^{20})\ldots \ldots $
E sfruttando l'identità $ ~ (1-x^a)(1+x^a) = (1-x^{2a}) $ si vede facilmente che quel prodotto fa 1
La mia era proprio bruttina... con le funzioni generatrici:
si riconosce facilmente che $ ~ (1+x)(1+x^2)(1+x^3)\ldots $ è la funzione generatrice per le partizioni in interi distinti e che $ ~ (1+x+x^2+\ldots)(1+x^3+x^6+\ldots)(1+x^5+x^10+\ldots)\ldots $ è la funzione generatrice per le partizioni in interi dispari.
Vogliamo dimostrare che sono uguali:
$ ~ (1+x)(1+x^2)(1+x^3)\ldots = \frac{1}{(1-x)(1-x^3)(1-x^5)\ldots} $
$ ~ (1+x)(1+x^2)(1+x^3)\ldots (1-x)(1-x^3)(1-x^5)\ldots = 1 $
Le riordino come:
$ ~ (1-x)(1+x)(1+x^2)(1+x^4)\ldots $$ (1-x^3)(1+x^3)(1+x^6)(1+x^{12})\ldots $$ (1-x^5)(1+x^5)(1+x^{10})(1+x^{20})\ldots \ldots $
E sfruttando l'identità $ ~ (1-x^a)(1+x^a) = (1-x^{2a}) $ si vede facilmente che quel prodotto fa 1
-
MindFlyer