Per dimostrare che
\[ \sum_{s=2}^{k} (-1)^s \binom{k}{s-1} \binom{n+k-s}{k-s} = \binom{n+k-1}{k-1} - \binom{n-1}{n-k} \]
L'unico modo che vedo io è tramite un argomentazione combinatoria. Ovvero dimostriamo che effettivamente il membro di sinistra e quello di destra contano gli stessi oggetti.
Notazione \( [n]= \{1,\ldots,n\} \)
Per il membro di destra:È noto che il numero di soluzioni intere positive dell'equazione \( x_1 + \ldots + x_k = n \) è dato da \( \binom{n+k-1}{k-1} \). Chiamiamo \( \mathcal{S}_{n,k} \) il numero di queste soluzioni. Inoltre chiamiamo
\[ \mathcal{F}_{n,k} := \{ f: [n] \to [k] : f \ \text{non decrescente} \} \]
Vogliamo trovare una biiezione \( \phi : \mathcal{S}_{n,k} \to \mathcal{F}_{n,k} \). Tale che ad una \(k\)-upla \(\mathcal{S}_{n,k} \ni (x_1,\ldots,x_k) \mapsto \phi( (x_1,\ldots,x_k)) = f \in \mathcal{F}_{n,k} \), tale che l'immagine di \(f\) è determinata interamente dalla \(k\)-upla
Possiamo fare un'argomentazione intuitiva per dimostrare che questa biiezione esiste.
Possiamo vedere \( x_m \) per \( 1\leq m \leq k \) come il numero \( x_m \in [n] \) tale che \( f(x_m)=m \), e siccome \(f\) è non decrescente, questo vuol dire esiste un'unica funzione che corrisponde ad una particolare soluzione. Per vederlo immagina di avere \(k\) scatole, e numerale dal \(1 \) al \(k\), queste corrispondono quindi ai tuoi \(x_1,\ldots, x_k\). Inoltre immagina di avere \(n\) palline. Prendiamo la prima scatola non vuota e diciamo che questa scatola è la numero \(m_1\), diciamo che contiene \(x_{m_1} \) palline. Siccome \(f\) è non decrescente, abbiamo che \( f(1)=f(2)=\ldots=f(x_{m_1}) = m_1 \). E così via troviamo dunque una biiezione \( \phi \) tra \( \mathcal{S}_{n,k} \) e \( \mathcal{F}_{n,k} \).
Se ti interessa la costruzione esplicita di \( \phi \) te la lascio in spoiler con la dimostrazione che è effettivamente una biiezione. Te la lascio in spoiler alla fine della risposta poiché la costruzione e la dimostrazione formale è un po' tecnica e quindi potrebbe risultare difficile, ma l'intuizione che c'è dietro è esattamente questa con le scatole. Quindi \[ \operatorname{card}(\mathcal{F}_{n,k}) = \binom{n+k-1}{k-1} \]
Ora da \( \mathcal{F}_{n,k} \) dobbiamo togliere tutte le funzioni non decrescenti che sono suriettive per rimanere con il numero totale di funzioni che sono non decrescenti e non suriettive. Contiamo dunque tutte le funzioni non decrescenti che sono suriettive. Questo equivale a fissare per ogni elemento \(a \in [k]\) un elemento di \(b\in [n]\) tale che \(f(b)=a\) dunque equivale a contare il numero di funzioni non decrescenti \(f:[n-k] \to [k] \) e quindi abbiamo che il numero totale di funzioni non decrescenti e non suriettive è dato da
\[ \binom{n+k-1}{k-1} - \binom{(n-k)+k-1}{k-1} = \binom{n+k-1}{k-1} - \binom{n-1}{k-1} = \binom{n+k-1}{k-1} - \binom{n-1}{n-k} \]
E questo dimostra che il membro di destra conta il numero di funzioni non decrescenti e non suriettive tra \([n]\) e \([k]\).
Per il membro di sinistra:Vogliamo contare il numero di funzioni non decrescenti e non suriettive \( f: [n] \to [k] \). Siccome \(f\) non può essere suriettiva per ipotesi sappiamo che almeno un elemento tra \([k]:= \{1,\ldots,k\} \) non è preso. Questo vuol dire che scelti \(1\leq i_1< \ldots < i_s \leq k \) elementi di \([k] \) questi non sono mappati dalla funzione \(f\). Fissiamo \(1 \leq s \leq k \) elementi di \( [k] \) e chiamiamo come prima
\[ \mathcal{F}_{n,k} := \{ f: [n] \to [k] : f \ \text{non decrescente} \} \]
Abbiamo che \( \operatorname{card}(\mathcal{F}_{n,k})= \binom{n+k-1}{k-1} \)
\[ \mathcal{F}_{i_1,\ldots,i_s} := \{ f: [n] \to [k] : f \ \text{non decrescente e i numeri} \ i_1,\ldots,i_s \ \text{non sono mappati da} \ f \} \]
Nota che questo equivale a contare il numero di funzioni crescenti \( f: [n] \to [k-s] \), dunque
\[ \operatorname{card} \left( \mathcal{F}_{i_1,\ldots,i_s} \right) = \operatorname{card} \left( \mathcal{F}_{n,k-s} \right) \]
Ora in quanti modi possiamo scegliere \(s \) elementi di \([k ]\)? Beh questo è facile e possiamo scegliere \(s\) elementi di \([k] \) in esattamente \( \binom{k}{s} \) modi.
Ora abbiamo che il numero di funzioni non decrescenti e non suriettive è dato dunque da:
\[ \operatorname{card} \left( \bigcup_{1 \leq i_1 < \ldots < i_s \leq k} \mathcal{F}_{i_1,\ldots,i_s} \right) = \sum_{s=1}^{k} (-1)^{s-1} \left( \sum_{1 \leq i_1 < \ldots < i_s \leq k} \operatorname{card}(\mathcal{F}_{i_1,\ldots,i_s} ) \right) \]
Pertanto abbiamo che
\[\sum_{s=1}^{k} (-1)^{s-1} \left( \sum_{1 \leq i_1 < \ldots < i_s \leq k} \operatorname{card}(\mathcal{F}_{n,k-s} ) \right) =\sum_{s=1}^{k} (-1)^{s-1}\binom{k}{s} \binom{n+(k-s)-1}{(k-s)-1} \]
\[= \sum_{s=1}^{k} (-1)^{s-1}\binom{k}{s} \binom{n+k-(s+1)}{k-(s+1)} = \sum_{s=2}^{k} (-1)^{s}\binom{k}{s-1} \binom{n+k-s}{k-s}\]
Questo dimostra che il membro di sinistra conta il numero di funzioni non decrescenti e non suriettive tra \([n]\) e \([k]\).
E siccome il membro di sinistra e quello di destra contano la stessa cosa allora sono uguali.
Costruzione esplicita di \( \phi \) e la dimostrazione che è una biiezione
Testo nascosto, fai click qui per vederlo
Sia \(m_1 := \min_{1 \leq j \leq k} \{ j : x_j \neq 0 \} \) e quindi, recursivamente, \( m_i := \min_{m_{i-1} < j \leq m } \{ j : x_j \neq 0 \} \), per \( i \in I \subset [k] \) e \(i > 1 \). Qui \( I \) denota l'insieme \( I:= [ \operatorname{card}( \{ i : 1 \leq i \leq k, x_i \neq 0 \} ) ] \).
Dunque diciamo che \( \operatorname{card}( \{ i : 1 \leq i \leq k, x_i \neq 0 \} ) = : r \leq k \) abbiamo dunque \( I = [r] = \{ 1 ,\ldots, r\} \). Sia \( (x_1,\ldots,x_k) \in \mathcal{S}_{n,k} \) e definiamo l'immagine di \(f \) tramite un'applicazione \( \phi ((x_1,\ldots,x_k))=f\), in questo modo.
\[ f(1) = f(1+1)=\ldots = f(x_{m_1})=m_1 \]
\[ f(x_{m_1} +1) = f(x_{m_1} +1+1)=\ldots = f(x_{m_1}+x_{m_2})=m_2 \]
\[ f(x_{m_1}+x_{m_2} +1) = f(x_{m_1} +x_{m_2}+1+1)=\ldots = f(x_{m_1}+x_{m_2}+x_{m_3})=m_3 \]
\[ \vdots\]
\[ f(x_{m_1}+\ldots+x_{m_{r-1}} +1) = f(x_{m_1}+\ldots+x_{m_{r-1}} +1+1)=\ldots = f(x_{m_1}+\ldots+x_{m_{r-1}}+x_{m_r})=m_r \]
Ad esempio se \(k=4 \) ed \(n=5\) abbiamo che \( (2,0,2,1) \) è una soluzione dell'equazione \(x_1+x_2+x_3+x_4 = 5 \), e dunque \( \phi((2,0,2,1)\) definisce \(f\) tramite la sua immagine che è \( f(1)=f(2)=1\); \( f(3)=f(4)=3\) e \(f(5)=4\). Questa \(f\) è unicamente determinata da \( (2,0,2,1)\) tramite l'applicazione \( \phi\). In particolare in questo esempio abbiamo \(m_1=1\), \(m_2=3\) e \(m_3=4\). Ed effettivamente \(f(1)=f(x_1)=f(2)=1\), \( f(x_1 +1)=f(3)=f(x_1 + x_3) = f(2+2)=3 \) e \( f(x_1+x_3+1)=f(x_1+x_3+x_4)=5 \).
Dimostriamo che \( \phi \) è una biiezione.
Per la suriettività:
Sia \( f \in \mathcal{F}_{n,k} \) allora per \( 1 \leq m \leq k \) definiamo \( x_m := \operatorname{card}(A_m) \) dove \( A_m := \{ a \in [n] : f(a) = m \} \), allora abbiamo che \( x_1 + \ldots + x_k = n \) per ogni \( f \in \mathcal{F}_{n,k} \).
Dunque esiste \( (x_1,\ldots,x_k) \in \mathcal{S}_{n,k} \) tale che \( \phi(x_1,\ldots,x_k) = f \), e dunque \( \phi \) è suriettiva.
Per l'iniettività:
Prendiamo \( (x_1,\ldots,x_k) , (y_1,\ldots,y_k) \in \mathcal{S}_{n,k} \) tale che \( (x_1,\ldots,x_k) \neq (y_1,\ldots,y_k) \). E diciamo che \( \phi((x_1,\ldots,x_k))=f \) e rispettivamente \( \phi((y_1,\ldots,y_k) )
=g \).
Siccome le due soluzioni sono differenti esiste un indice, che scegliamo essere minimale, \(m\) tale che \( x_m \neq y_m \). Se uno tra \(x_m\) e \(y_m \) è uguale a zero, senza perdità di generalità diciamo \(x_m=0\), abbiamo che \(y_m \neq 0 \), questo significa che \( \forall a \in [n] \) abbiamo che \( f(a) \neq m \), ma per costruzione abbiamo che esiste \( b \in [n] \) tale che \(g(b) = m \), e quindi concludiamo che \(f \neq g \).
Supponiamo ora che \(x_m \) e \(y_m \) sono entrambi differenti da zero. Senza perdità di generalità supponiamo \(x_m < y_m \). Per minimalità di \(m \), scegliamo il più piccolo \( a \in [n] \) tale che \( f(a) = m = g(a) \), e quindi abbiamo che \( \forall b< a \in [n] \) risulta che \(f(b) \neq m \) e \( g(b) \neq m \). In questo caso abbiamo che \( f(a) = \ldots = f(a+ x_m -1) = m \) e \( f(a+x_m) \neq m \) e abbiamo anche che
\( g(a) = \ldots = g(a+y_m - 1) = m \) ma siccome \( x_m < y_m \) allora abbiamo che \( f(a + y_m -1 ) \neq m \) e quindi \( f \neq g \). Dunque \( \phi \) è iniettiva. E dunque è biiettiva.