45. Eulero alèohoh pure le partizioni

[Gottinger95]

E' un problema abbastanza classico, probabilmente parecchi lo conosceranno, ma non mi pare di averlo visto sul forum (almeno recentemente) e quindi lo propongo perchè piuttosto figo.

Chiamiamo partizione di un numero \(n\) un modo di scrivere \(n\) come somma di numeri positivi, dove l'ordine degli addendi è irrilevante. Per esempio le partizioni di 4 sono
1+1+1+1
2+1+1
2+2
3+1
4

Dimostrare che
1. Il numero di partizioni di \(n\) in esattamente \(k\) addendi è uguale al numero di partizioni di \(n\) dove l'addendo maggiore è esattamente \(k\).
2. Il numero di partizioni di \(n\) in numeri dispari non necessariamente distinti è uguale al numero di partizioni di \(n\) in numeri distinti (Eulero).

[matpro98]

Ma ad esempio:
4+0+0+0
Sono da considerarsi 4 addendi o uno solo?

[scambret]

Chiamiamo partizione di un numero \(n\) un modo di scrivere \(n\) come somma di numeri positivi, dove l'ordine degli addendi è irrilevante.

P.S. Mi pare che in qualche lezione di Combinatoria del Senior si faceva. Comunque è davvero carino

[nassus95]

ci provo
1. Chiamo $f(n)$ la funzione che mi dà il numero di partizioni di $n$. Quindi le partizioni di $n$ in cui l'addendo maggiore è $k$ sono $f(n-k)$. Calcolo ora il numero di partizioni di $n$ in cui ho esattamente $k$ addendi. Parto con $k$ numeri $1$ e ora devo distribuire gli altri $n-k$ numeri $1$ sui $k$ precedenti e lo posso fare in $f(n-k)$ modi. Pertanto il numero di partizioni di $n$ in esattamente $k$ addendi è uguale al numero di partizioni di $n$ dove l'addendo maggiore è esattamente $k$ (ovvero $f(n-k)$).
2. Voglio costruire un metodo per passare in modo biunivoco da una partizione di $n$ in numeri dispari ad una partizione di $n$ in numeri distinti. Prendo una partizione in numeri distinti (quindi devo arrivare ad una in numeri dispari):
a. se ho solo numeri dispari ho finito
b. se ho dei numeri pari li divido per due
c. se ho ancora numeri pari li divido per due
...
Continuo in questo modo fino ad ottenere solo numeri dispari. In questo modo, partendo da un numero del tipo $2^{\alpha} \prod p_{i}^{\alpha _i}$ (= scomposizione in fattori primi), ottengo $\alpha$ numeri dispari $\prod p_{i}^{\alpha _i}$.
Questo metodo mi dà una biezione perché posso creare il "metodo inverso" che da ogni partizione in numeri dispari ottengo una e una sola partizione in numeri diversi, ovvero se ho $h=[a_ka_{k-1}...a_2a_1a_0]_2$ (con $a_i \in \{0,1\}$ ) numeri dispari uguali $d$ li sostituisco con $\sum_{i=0} ^k a_i2^{i}d$

P.S.: mi sono appena accorto di aver scritto una cavolata. Vedrò di correggerla

[nassus95]

in effetti la prima parte della dimostrazione valeva, se non sbaglio, solo per i $k>\frac{n}{2}$
Anche qui allora creo un "metodo" per passare da una partizione all'altra. Se ho una partizione dove l'addendo massimo è $k$ procedo in questo modo:
a. scrivo $k$ $1$
b. prendo il secondo addendo e scompongo anche questo in "$1$" che vado a sommare a quelli precedenti (quelli del punto a)
...
In questo modo ho una partizione in $k$ addendi
Analogamente posso fare il procedimento contrario.
Adesso che mi viene in mente posso considerare $n$ come un insieme di $n$ quadratini unitari e pensare una partizione come un insieme di colonne/righe in cui divido questi quadratini. Quindi se guardo da una parte vedo la partizione in $k$ addendi mentre se guardo dall'altra ho una partizione dove l'addendo maggiore è $k$. Forse risolverlo in quest'ultimo modo è più rapido e chiaro

[Drago96]

Ok, bene l'ultima parte con i quadratini (chiamasi diagrammi di Young)
Per il b, non ho ben capito cosa vuoi fare... probabilmente esiste una dimostrazione con i disegni (che ora non ho voglia di cercare), ma la strada più rapida è ricordarsi che è stato proposto da Cottinger!

[nassus95]

Mi sono spiegato male. Forse è meglio che faccia un esempio del "metodo inverso" (sperando che l'altro sia chiaro) con un numero ($18$)
$18=9+9$
$17+1=17+1$
$16+2=(1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1)+(1+1)$
$15+3=15+3$
$15+2+1=15+1+1+1$
$14+4=7+7+1+1+1+1$
$14+3+1=7+7+3+1$
...
Allo stesso modo posso fare il procedimento contrario, ovvero per esempio
$3+3+3+3+3+3=6(3)=[110]_2(3)=(1)2^2(3)+(1)2^1(3)+(0)2^0(3)=12+6$
$1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=18(1)= [1010]_2 (1)=16+2$
$15+1+1+1=15+3(1)=15+[11]_2(1)=15+2+1$
...
Sostanzialmente cosa faccio: prendo una partizione in numeri dispari
a. se ha tutti i numeri diversi ho finito
b. se ha dei numeri uguali, prendo coppie uguali e le sommo
c. se rimangono numeri uguali continuo in questo modo
Esempio
$1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=2+2+2+2+2+2+2+2+2=4+4+4+4+2=8+8+2=16+2$
Questo "metodo inverso" passa da una partizione in numeri dispari ad una ed una sola in numeri diversi (perchè la scrittura in base $2$ è unica e numeri diversi non mi possono dare risultati uguali).
Spero di aver chiarito un po' la dimostrazione anche se sono certo che ce ne siano di più rapide e semplici

[Gottinger95]

Complimenti! Questo era proprio il modo in cui lo ha risolto Eulero! Se lo hai fatto da te, bene bene Vai con il prossimo nassus95 !

[Drago96]

Ok, bene! non avevo ben capito dalla tua formula alla fine...
Anyway, metodo interessante:
Chiamiamo $ a_n $ il numero di partizioni in interi distinti di $ n $ e $ b_n $ il numero di partizioni in dispari. Vogliamo dimostrare che $ a_n=b_n $; per farlo dimostriamo che $ A(x)=a_0+a_1x+a_2x^2+\dots $ e $ B(x) $ definita similmente sono uguali.
Vediamo che $ A (x)=(1+x)(1+x^2)(1+x^3)\dots $, infatti ogni esponente deriva dalla somma degli esponenti nelle parentesi, che sono distinti.
Poi $ B (x)=(1+x+x^2+\dots)(1+x^3+x^6+\dots)(1+x^5+\dots)\dots $, in quanto dalla prima parentesi prendiamo un po' di uni, dalla seconda un po' di tre, eccetera. Possiamo poi riscrivere $ B (x)=\dfrac1 {(1-x)(1-x^3)(1-x^5)\dots} $.
Riscriviamo B moltiplicando sorpra e sotto per $(1-x^2)(1-x^4)\dots$ e otteniamo $ B (x)=\dfrac {(1-x^2)(1-x^4)(1-x^6)\dots}{(1-x)(1-x^2)(1-x^3)\dots} $
Ma $\dfrac {1-x^{2n}}{1-x^n}=1+x^n $, e quindi alla fine $ B (x)=(1+x)(1+x^2)\dots=A (x) $