Una partizione di un numero intero $ \n\ge 1 $ è una decomposizione di n in addendi interi (parti) $ m_1,.....m_k $ tali che $ m_i\ge 1 $ e $ m_1+.....+m_k=n $.
Per esempio le partizioni di 3 sono 3,2+1,1+1+1 e quelle di 4 sono 4,3+1,2+2,2+1+1,1+1+1+1.
Si dimostri che il numero delle partizioni di un intero n in al più r parti è uguale al numero delle sue partizioni in perti ciascuna al massimo uguale a r.
Buon lavoro!!
sns 2004/2005 #6
-
pi_greco_quadro
- Messaggi: 158
- Iscritto il: 01 gen 1970, 01:00
- Località: Verona
Un bellissimo problema a mio parere! solamente che avendo pensato la soluzione sarei propenso a classificarlo come combinatoria...
Dunque le idee fondamentali sono queste
Diciamo che io voglia partizionare un $ n $ in al più $ k $ parti. Allora nessuno mi vieta di disegnare la mia partizione così come segue:
definisco una successione di righe $ r_0,r_1,\cdots, r_k $, ed in ognuna di queste coloro tante caselle quanto vale il valore dell'addendo che io desidero rappresentare in quella data riga. Chiaramente colorerò sempre un numero $ x\leq n $ di caselle e non è detto che sia obbligato ad utilizzare tutte le righe da me definite. Non importa: possiamo sempre pensare di associare ad una riga lasciata vuota l'addendo $ 0 $, assolutamente ininfluente nell'economia delle partizioni di un numero, e quindi del nostro problema.
Per spiegarmi, esemplifico con la partizione 4=3+1 e k=2
r_1= * * *
r_2= *
Ora, qui sta il giochino fighissimo di questo problema: per ogni partizione che abbiamo disegnato come sopra spiegato, supponiamo di ruotare il disegno corrispondente di $ 90° $ adottando come verso di rotazione quello antiorario. Bene, ci accorgiamo allora che tutte le righe sono diventate colonne e viceversa. Quindi ora avremo $ n $ righe ed al più $ k $ colonne, quindi potremmo disegnare solo addendi che valgono al più $ k $. Ora, per come noi abbiamo definito questa nostra applicazione, possiamo affermare che ad ogni disegno di partenza corrisponde uno ed uno solo disegno ruotato, ma quindi siamo in presenza di un'applicazione bigettiva, e questo conclude la dimostrazione del problema.
Dunque le idee fondamentali sono queste
Diciamo che io voglia partizionare un $ n $ in al più $ k $ parti. Allora nessuno mi vieta di disegnare la mia partizione così come segue:
definisco una successione di righe $ r_0,r_1,\cdots, r_k $, ed in ognuna di queste coloro tante caselle quanto vale il valore dell'addendo che io desidero rappresentare in quella data riga. Chiaramente colorerò sempre un numero $ x\leq n $ di caselle e non è detto che sia obbligato ad utilizzare tutte le righe da me definite. Non importa: possiamo sempre pensare di associare ad una riga lasciata vuota l'addendo $ 0 $, assolutamente ininfluente nell'economia delle partizioni di un numero, e quindi del nostro problema.
Per spiegarmi, esemplifico con la partizione 4=3+1 e k=2
r_1= * * *
r_2= *
Ora, qui sta il giochino fighissimo di questo problema: per ogni partizione che abbiamo disegnato come sopra spiegato, supponiamo di ruotare il disegno corrispondente di $ 90° $ adottando come verso di rotazione quello antiorario. Bene, ci accorgiamo allora che tutte le righe sono diventate colonne e viceversa. Quindi ora avremo $ n $ righe ed al più $ k $ colonne, quindi potremmo disegnare solo addendi che valgono al più $ k $. Ora, per come noi abbiamo definito questa nostra applicazione, possiamo affermare che ad ogni disegno di partenza corrisponde uno ed uno solo disegno ruotato, ma quindi siamo in presenza di un'applicazione bigettiva, e questo conclude la dimostrazione del problema.
Disco es cultura, metal es religion (Metal py)
"Ti credevo uno stortone.. e pure vecchio.. (Lei)"
"Ti credevo uno stortone.. e pure vecchio.. (Lei)"
un disegnino vale più di mille parole (come dice il mio relatore triennale)
Codice: Seleziona tutto
***** ****
*** **
* ---> **
* *
*