Partizione di un numero intero maggiore di 2

[dorothyhung]

Dimostrare che per ogni intero $ n $ maggiore o uguale a due, metà delle partizioni di $ n $ in potenze di 2 hanno un numero pari di parti.

[Tibor Gallai]

Se una partizione contiene almeno tanti addendi 1 quanto è il valore dell'addendo massimo, si uniscono più 1 possibile in un unico addendo (che sia potenza di 2). Altrimenti, si prende l'addendo massimo e lo si trasforma in una somma di 1. Questa trasformazione è involutoria ed inverte la parità della partizione (se n>1).

[dorothyhung]

potresti spiegarmi meglio? come faccio a dimostrarlo analiticamente. Leggendo la tua risposta intuisco la soluzione, ma non riesco a formalizzarla! Grazie

[Tibor Gallai]

Fissato n>1, ho costruito una bigezione tra le partizioni di n in potenze di 2 con un numero pari di parti e quelle con un numero dispari di parti. Poiché (lemma) le parti sono o pari o dispari, segue che quelle pari sono la metà.

Cosa intendi con "analiticamente"? Con le funzioni generatrici?

[dorothyhung]

non riesco a capire quale è la bigezione che consideri! Scusami..

[Tibor Gallai]

Immagina di partizionare n=22 come 8+4+4+4+1+1. Quello che ti disegno qua sotto si chiama diagramma di Ferrer della partizione (ebbene sì, 'sta cagata ha un nome...):

oooooooo
oooo
oooo
oooo
o
o

La mia trasformazione fa questo: se gli addendi uguali a 1 sono almeno tanti quanto il valore dell'addendo massimo, ovvero 8, ne unisce il più possibile in un unico addendo e lo mette in cima al diagramma (in modo che il nuovo addendo sia una potenza di 2). Ma in questo caso gli addendi 1 sono solo 2, quindi fa il contrario: prende l'addendo massimo e lo spezza in tanti addendi 1, mettendoli in fondo al diagramma. Il diagramma trasformato è così:

oooo
oooo
oooo
o
o
o
o
o
o
o
o
o
o

Se provi a riapplicare la trasformazione, vedi che l'addendo massimo adesso è 4, e gli addendi 1 sono 10. Quindi sono abbastanza per essere raggruppati, ne prendi 8 (che è la massima potenza di 2 che non supera 10), li unisci in un unico addendo e lo metti in cima al diagramma. Così ritorni alla configurazione di partenza.

Puoi dimostrare che, qualunque sia la partizione in potenze di 2, questa trasformazione cambia sempre la sua parità (nell'esempio, si passa da 6 addendi a 13), ed inoltre applicandola 2 volte ti riporta alla partizione iniziale. L'unica eccezione è quando n=1, che giustamente escludi nel testo.

Quindi, è come se stessi accoppiando in modo univoco partizioni di diversa parità, e questo determina una bigezione.