Numero di soluzioni di un'equazione
Siano \(n, k \in \mathbb{N} \) fissati. Trovare il numero di soluzioni dell'equazione
\[ x_1 + \ldots + x_k = n \ \ \ \ \ (\star)\]
tale che \( x_i \in \mathbb{Z}_{\geq 0} \), per \( i \in \{ 1, \ldots, k \} \)
Soluzione:
Il numero di soluzioni è dato da \( \binom{n+k-1}{k-1} \)
Dimostrazione:
Costruiamo una biiezione tra le soluzioni di \( (\star) \) e i sottoinsiemi di cardinalità \( k-1 \) in \( [n+k-1] \)
\( (x_1, \ldots, x_k) \to \{ x_1+1, x_1+x_2+2, \ldots, x_1 + \ldots + x_{k-1} + k-1 \} \)
Non ho capito diverse cose
1) il motivo per cui vuole costruire una biiezione tra le soluzioni di \( (\star) \) e i sottoinsiemi di cardinalità \( k-1 \) in \( [n+k-1] \), nel senso non ho capito come sceglie la cardinalità degli sottoinsiemi ne ho capito come sceglie la grandezza dell'insieme \( [n+k-1] \).
2) Non ho capito come è fatta questa biiezione, mi sembra che una soluzione è associata ad un sottoinsieme ma non vedo come fa a dire che c'è una biiezione tra il numero di soluzioni e tutti i sottoinsiemi di cardinalità \( k-1 \).
3) Pertanto non vedo come mai questo dimostra che il numero di soluzioni è \( \binom{n+k-1}{k-1} \)
\[ x_1 + \ldots + x_k = n \ \ \ \ \ (\star)\]
tale che \( x_i \in \mathbb{Z}_{\geq 0} \), per \( i \in \{ 1, \ldots, k \} \)
Soluzione:
Il numero di soluzioni è dato da \( \binom{n+k-1}{k-1} \)
Dimostrazione:
Costruiamo una biiezione tra le soluzioni di \( (\star) \) e i sottoinsiemi di cardinalità \( k-1 \) in \( [n+k-1] \)
\( (x_1, \ldots, x_k) \to \{ x_1+1, x_1+x_2+2, \ldots, x_1 + \ldots + x_{k-1} + k-1 \} \)
Non ho capito diverse cose
1) il motivo per cui vuole costruire una biiezione tra le soluzioni di \( (\star) \) e i sottoinsiemi di cardinalità \( k-1 \) in \( [n+k-1] \), nel senso non ho capito come sceglie la cardinalità degli sottoinsiemi ne ho capito come sceglie la grandezza dell'insieme \( [n+k-1] \).
2) Non ho capito come è fatta questa biiezione, mi sembra che una soluzione è associata ad un sottoinsieme ma non vedo come fa a dire che c'è una biiezione tra il numero di soluzioni e tutti i sottoinsiemi di cardinalità \( k-1 \).
3) Pertanto non vedo come mai questo dimostra che il numero di soluzioni è \( \binom{n+k-1}{k-1} \)
Risposte
[ot]Mi dispiace non poterti proprio aiutare in questo momento. Per curiosità, vorrei sapere se questi sono gli esercizi del corso di Maryna Viazovska. Solo una curiosità, dettata dal fatto che sto leggendo alcuni suoi articoli, come già ti ho detto.[/ot]
"dissonance":
[ot]Mi dispiace non poterti proprio aiutare in questo momento. Per curiosità, vorrei sapere se questi sono gli esercizi del corso di Maryna Viazovska. Solo una curiosità, dettata dal fatto che sto leggendo alcuni suoi articoli, come già ti ho detto.[/ot]
Scusa la tarda risposta, si comunque
"Martino":
Vedi qui.
Grazie mille!
Toglietemi una curiosità però, allora se io volessi sapere il numero di funzioni \( f: [n] \to [m] \) chiaramente ogni \(x \in [n] \) ha \( m \) possibilità dunque il numero di funzioni è dato da \( m^n \). E fin qui siamo d'accordo tutti immagino.
Ma il seguente ragionamento mi sembra corretto e non capisco dove sbaglio. Indichiamo con \( x_k \) con \( 1 \leq k \leq m \) la cardinalità di \(A_k:=\{ a\in [n] : f(a)=k \} \) allora è chiaro che
\[ x_1 + \ldots + x_m = n \]
Pertanto il numero di funzioni tra \( f:[n] \to [m] \) è dato da
\[ \binom{m+n-1}{m-1} = \binom{n+m-1}{n} \neq m^n \]
Che dovrebbe essere invece il numero di funzioni non decrescenti...
Ho capito! L'errore sta nel fatto che potrei non distinguere delle soluzioni, prendiamo l'esempio con \(n = 3 \) e \( m = 2 \)
Abbiamo in totale 8 funzioni, \( f_1,f_2,\ldots, f_8 \)
\( f_1 (1)= f_1 (2)= f_1 (3)=1\)
\( f_2 (1)= 1; f_2 (2)= f_2 (3)=2\)
\( f_3 (1)= f_3 (2)= 1;f_3 (3)=2\)
\( f_4 (1)= f_4 (3)= 1;f_4 (2)=2\)
\( f_5 (1)= f_5 (2)= f_5 (3)=2\)
\( f_6 (1)= 2; f_6 (2)= f_6 (3)=1\)
\( f_7 (1)= f_7 (2)= 2;f_7 (3)=1\)
\( f_8 (1)= f_8 (3)=2; f_8 (2)=1\)
Mentre le soluzioni dell'equazione
\[ x_1 + x_2 = 3 \]
Sono:
\( (a_1,b_1)= (0,3) \)
\( (a_2,b_2)= (1,2) \)
\( (a_3,b_3)= (2,1) \)
\( (a_4,b_4)= (0,3) \)
E chiaramente più funzioni corrispondono alla stessa soluzione dell'equazione... ad esempio la funzione \( f_1 \) corrisponde alla soluzione \( (a_1,b_1) \), la funzione \( f_5 \) corrisponde alla soluzione \( (a_4,b_4) \). Mentre alla soluzione \( (a_2,b_2) \) corrispondono le funzioni \( f_2, f_7, f_8 \) e alla soluzione \( (a_3,b_3) \) corrispondono le funzioni \( f_3,f_4,f_6 \)
Abbiamo in totale 8 funzioni, \( f_1,f_2,\ldots, f_8 \)
\( f_1 (1)= f_1 (2)= f_1 (3)=1\)
\( f_2 (1)= 1; f_2 (2)= f_2 (3)=2\)
\( f_3 (1)= f_3 (2)= 1;f_3 (3)=2\)
\( f_4 (1)= f_4 (3)= 1;f_4 (2)=2\)
\( f_5 (1)= f_5 (2)= f_5 (3)=2\)
\( f_6 (1)= 2; f_6 (2)= f_6 (3)=1\)
\( f_7 (1)= f_7 (2)= 2;f_7 (3)=1\)
\( f_8 (1)= f_8 (3)=2; f_8 (2)=1\)
Mentre le soluzioni dell'equazione
\[ x_1 + x_2 = 3 \]
Sono:
\( (a_1,b_1)= (0,3) \)
\( (a_2,b_2)= (1,2) \)
\( (a_3,b_3)= (2,1) \)
\( (a_4,b_4)= (0,3) \)
E chiaramente più funzioni corrispondono alla stessa soluzione dell'equazione... ad esempio la funzione \( f_1 \) corrisponde alla soluzione \( (a_1,b_1) \), la funzione \( f_5 \) corrisponde alla soluzione \( (a_4,b_4) \). Mentre alla soluzione \( (a_2,b_2) \) corrispondono le funzioni \( f_2, f_7, f_8 \) e alla soluzione \( (a_3,b_3) \) corrispondono le funzioni \( f_3,f_4,f_6 \)
È semplice: così stai solo contando gli elementi della preimmagine di $k$, mentre per definire una funzione devi anche dirmi quali sono questi elementi (e non solo quanti sono).
Si volevo dire questo, ma non trovavo il modo per dirlo 
"Martino":
Vedi qui.
Molto divertente l'idea dei segni di interpunzione vicini "|" per rappresentare anche gli zeri. Se le soluzioni sono strettamente maggiori di $0$ la formula invece diventa \( \binom{n-1}{k-1} \).
Ma se poi si volessero contare una sola volta le soluzioni simili in termini commutativi, non c'è una formula "abbastanza semplice" come queste per fare questa cosa?
Cerco di spiegarmi meglio. Bisognerebbe contare una sola volta soluzioni del genere...
$2 + 1 + 1 = 4$
$1 + 2 + 1 = 4$
$1 + 1 + 2 = 4$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo