45. Eulero alèohoh pure le partizioni

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

45. Eulero alèohoh pure le partizioni

Messaggio da 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).
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
matpro98
Messaggi: 479
Iscritto il: 22 feb 2014, 18:42

Re: 45. Eulero alèohoh pure le partizioni

Messaggio da matpro98 »

Ma ad esempio:
4+0+0+0
Sono da considerarsi 4 addendi o uno solo?
scambret
Messaggi: 734
Iscritto il: 23 mag 2012, 20:49
Località: Acquarica del Capo

Re: 45. Eulero alèohoh pure le partizioni

Messaggio da scambret »

Gottinger95 ha scritto: 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
Messaggi: 79
Iscritto il: 14 giu 2012, 11:06

Re: 45. Eulero alèohoh pure le partizioni

Messaggio da 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
Ultima modifica di nassus95 il 12 mar 2014, 13:43, modificato 1 volta in totale.
nassus95
Messaggi: 79
Iscritto il: 14 giu 2012, 11:06

Re: 45. Eulero alèohoh pure le partizioni

Messaggio da 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 :)
Avatar utente
Drago96
Messaggi: 1147
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: 45. Eulero alèohoh pure le partizioni

Messaggio da 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! :P
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
nassus95
Messaggi: 79
Iscritto il: 14 giu 2012, 11:06

Re: 45. Eulero alèohoh pure le partizioni

Messaggio da 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 :)
Ultima modifica di nassus95 il 12 mar 2014, 13:40, modificato 1 volta in totale.
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: 45. Eulero alèohoh pure le partizioni

Messaggio da 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 !
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Avatar utente
Drago96
Messaggi: 1147
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: 45. Eulero alèohoh pure le partizioni

Messaggio da 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) $
:D
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Rispondi