Sommatoria con coefficienti binomiali

rafz123
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

Risposte
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

totissimus

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.