Partizioni di $n$ in al più $r$ parti e in parti $\leq r$
- Federico II
- Messaggi: 230
- Iscritto il: 14 mag 2014, 14:56
- Località: Roma
Partizioni di $n$ in al più $r$ parti e in parti $\leq r$
Siano $n,r$ due interi positivi, con $n\geq r$. Dimostrare che le partizioni di $n$ in al più $r$ parti sono tante quante le partizioni di $n$ in parti minori o uguali a $r$. Chi già conosce la soluzione è pregato di non spoilerarla agli altri.
Il responsabile della sala seminari
- Federico II
- Messaggi: 230
- Iscritto il: 14 mag 2014, 14:56
- Località: Roma
Re: Partizioni di $n$ in al più $r$ parti e in parti $\leq r
Up!
Il responsabile della sala seminari
- Gerald Lambeau
- Messaggi: 335
- Iscritto il: 17 mag 2015, 13:32
- Località: provincia di Lucca
Re: Partizioni di $n$ in al più $r$ parti e in parti $\leq r$
Mi trovo a fare necroposting .
Tra gli esercizi di allenamento di Torino di quest'anno troviamo un esercizio che ci fa intuire che vale qualcosa di più forte: le partizione di $n$ in esattamente $r$ parti sono tante quante le partizioni di $n$ tali che la massima tra quelle parti è esattamente $r$ (dimostrare che questa cosa implica il problema originale è un esercizio lasciato al lettore).
Dimostrazione: prendiamo una partizione in esattamente $r$ parti: $x_1+x_2+\dots+x_r=n$ con $x_1 \ge x_2 \ge \dots \ge x_r$ interi positivi. Coloriamo sul piano cartesiano i seguenti punti:
$(1, 1), (1, 2) \dots (1, x_1)$
$(2, 1), (2, 2) \dots (2, x_2)$
$\vdots$
$(r, 1), (r, 2) \dots (r, x_r)$.
Facciamo una simmetria di questi punti rispetto alla retta $x=y$ e troviamo una bella bigezione, perché otteniamo una partizione dove la massima tra le parti è esattamente $r$ e possiamo fare l'operazione inversa, il che associa le due quantità richieste in maniera, appunto, biunivoca.
Tra gli esercizi di allenamento di Torino di quest'anno troviamo un esercizio che ci fa intuire che vale qualcosa di più forte: le partizione di $n$ in esattamente $r$ parti sono tante quante le partizioni di $n$ tali che la massima tra quelle parti è esattamente $r$ (dimostrare che questa cosa implica il problema originale è un esercizio lasciato al lettore).
Dimostrazione: prendiamo una partizione in esattamente $r$ parti: $x_1+x_2+\dots+x_r=n$ con $x_1 \ge x_2 \ge \dots \ge x_r$ interi positivi. Coloriamo sul piano cartesiano i seguenti punti:
$(1, 1), (1, 2) \dots (1, x_1)$
$(2, 1), (2, 2) \dots (2, x_2)$
$\vdots$
$(r, 1), (r, 2) \dots (r, x_r)$.
Facciamo una simmetria di questi punti rispetto alla retta $x=y$ e troviamo una bella bigezione, perché otteniamo una partizione dove la massima tra le parti è esattamente $r$ e possiamo fare l'operazione inversa, il che associa le due quantità richieste in maniera, appunto, biunivoca.
"If only I could be so grossly incandescent!"
- Federico II
- Messaggi: 230
- Iscritto il: 14 mag 2014, 14:56
- Località: Roma
Re: Partizioni di $n$ in al più $r$ parti e in parti $\leq r$
Ok, buona
Il responsabile della sala seminari