Sommatoria con coefficienti binomiali

[Raff_321]

Risolvendo un quesito di combinatoria, mi sono imbattuto in una sommatoria per cui vorrei trovare (se esiste) una formula chiusa. La sommatoria è la seguente:
$ sum_(2<= s <=k ) ( (k), (s-1) ) ( (n+k-s), (k-s) ) (-1)^s $
Tale sommatoria conta il numero di funzioni debolmente crescenti NON suriettive da un insieme $ A $ di $ n $ elementi a un insieme $ B $ di $ k $ elementi, e per arrivare a questa formula ho utilizzato il principio di inclusione-esclusione. Ho il risultato dell'esercizio, che deriva da un altro ragionamento, che consiste nel sottrarre alle funzioni debolmente crescenti da $ A $ a $ B $ quelle debolmente crescenti e suriettive sempre da $ A $ a $ B $. Essendo le funzioni debolmente crescenti $ ( (n+k-1), (k-1) ) $ e quelle debolmente crescenti e suriettive $ ( (n-1), (n-k) ) $, trovo che le funzioni debolmente crescenti e non suriettive sono $ ( (n+k-1), (k-1) ) -( (n-1), (n-k) ) $, che dovrebbe dunque essere il risultato della sommatoria (le due formule le ho trovate in altri esercizi che ho svolto). Ma come si può arrivare a questa formula chiusa a partire dalla sommatoria? Grazie mille in anticipo

[3m0o]

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.

[totissimus]

Testo nascosto, fai click qui per vederlo

$$S_{n}=\sum_{s=2}^{k}(-1)^{s}\binom{k}{s-1}\binom{n+k-s}{k-s}$$

Troviamo la funzione generatrice

$$f(x)=\sum_{n=0}^{\infty}S_{n}x^{n}=\sum_{n=0}^{\infty}\sum_{s=2}^{k}(-1)^{s}\binom{k}{s-1}\binom{n+k-s}{k-s}x^{n}=$$

$$=\sum_{s=2}^{k}\sum_{n=0}^{\infty}(-1)^{s}\binom{k}{s-1}\binom{n+k-s}{k-s}x^{n}=$$

$$\sum_{s=2}^{k}(-1)^{s}\binom{k}{s-1}\sum_{n=0}^{\infty}\binom{n+k-s}{k-s}x^{n}=$$

$$=\sum_{s=2}^{k}(-1)^{s}\binom{k}{s-1}\sum_{n=0}^{\infty}\frac{(n+k-s)\ldots(n+1)}{(k-s)!}x^{n}=$$

$$\sum_{s=2}^{k}(-1)^{s}\binom{k}{s-1}\frac{1}{(k-s)!}\sum_{n=0}^{\infty}(n+k-s)\ldots(n+1)x^{n}=$$

$$=\sum_{s=2}^{k}(-1)^{s}\binom{k}{s-1}\frac{1}{(k-s)!}\frac{d^{k-s}}{x^{k-s}}\sum_{n=0}^{\infty}x^{n+k-s}=$$

$$=\sum_{s=2}^{k}(-1)^{s}\binom{k}{s-1}\frac{1}{(k-s)!}\frac{d^{k-s}}{x^{k-s}}\sum_{n=0}^{\infty}x^{n}=$$

$$=\sum_{s=2}^{k}(-1)^{s}\binom{k}{s-1}\frac{1}{(k-s)!}\frac{d^{k-s}}{x^{k-s}}(\frac{1}{1-x})=$$

$$=\sum_{s=2}^{k}(-1)^{s}\binom{k}{s-1}\frac{1}{(k-s)!}(k-s)!(1-x)^{-k+s-1}=$$

$$=(1-x)^{-k-1}\sum_{s=2}^{k}(-1)^{s}\binom{k}{s-1}(1-x)^{s}=$$

$$=(1-x)^{-k-1}\sum_{s=2}^{k}\binom{k}{s-1}(x-1)^{s}=$$

$$=(1-x)^{-k-1}\sum_{s=1}^{k-1}\binom{k}{s}(x-1)^{s+1}=$$

$$=(1-X)^{-K}(X-1)^{-1}(X-1)\sum_{s=1}^{k-1}\binom{k}{s}(x-1)^{s}=$$

$$=-(1-X)^{-K}\left[\sum_{s=0}^{k}\binom{k}{s}(x-1)^{s}-1-(X-1)^{K}\right]=$$

$$=-(1-X)^{-K}\left[X^{K}-1-(X-1)^{K}\right]=$$

$$=(1-X)^{-K}-X^{K}(1-X)^{-K}+(-1)^{K}=$$

$$=\sum_{n=0}^{\infty}\binom{-k}{n}(-1)^{n}x^{n}-x^{k}\sum_{n=0}^{\infty}(-1)^{n}\binom{-k}{n}x^{n}=$$

$$=\sum_{n=0}^{\infty}\binom{-k}{n}(-1)^{n}x^{n}-\sum_{n=0}^{\infty}(-1)^{n}\binom{-k}{n}x^{n+k}+(-1)^{K}=$$

$$=\sum_{n=0}^{\infty}\binom{-k}{n}(-1)^{n}x^{n}-\sum_{n=k}^{\infty}(-1)^{n-k}\binom{-k}{n-k}x^{n}+(-1)^{K}$$

Quindi per $n\geq k$:

$$S_{n}=\binom{-k}{n}(-1)^{n}-(-1)^{n-k}\binom{-k}{n-k}$$

Tenuto conto che $$\binom{-a}{b}=(-1)^{b}\binom{a+b-1}{b}$$

$$S_{n}=\binom{k+n-1}{n}(-1)^{n}(-1)^{n}-(-1)^{n-k}(-1)^{n-k}\binom{k+n-k-1}{n-k}=\binom{k+n-1}{n}-\binom{n-1}{n-k}=\binom{k+n-1}{k-1}-\binom{n-1}{n-k}$$