Dimostrazione credo del coefficiente binomiale
Salve a tutti, il professore chiede la dimostrazione
$|{S sube [n] : |S|=k}|=((n),(k))$
per ogni $n>=k>=0$
Adesso la mia idea o almeno cerco di decifrare quello che sta scritto: devo trovare la cardinalità di quell'insieme, in modo che la classe di $n$ sia inclusa in $S$ tale che la cardinalità di $S$ sia uguale a $k$ e tutto questo deve essere uguale al coefficiente binomiale.
$|{S sube [n] : |S|=k}|=((n),(k))$
per ogni $n>=k>=0$
Adesso la mia idea o almeno cerco di decifrare quello che sta scritto: devo trovare la cardinalità di quell'insieme, in modo che la classe di $n$ sia inclusa in $S$ tale che la cardinalità di $S$ sia uguale a $k$ e tutto questo deve essere uguale al coefficiente binomiale.
Risposte
Sinceramente non ho capito nulla della tua frase. Io ti suggerirei di dimostrarlo per induzione.
come posso partire?
Segno con \(V(n,k)\) il valore che devi trovare.
Vale banalmente l'uguaglianza \(\displaystyle V(n,k) = V(n,n-k) \).
Risulta che \(V(n+1,k) = V(n,k) + V(n,k-1) \). Infatti se tu ingrandisci l'insieme totale con un nuovo elemento, i sottoinsiemi di cardinalità \(\displaystyle k \) sono i sottoinsiemi di cardinalità \(\displaystyle k \) dell'insieme più piccolo uniti ai sottoinsiemi di cardinalità \(\displaystyle k-1 \) a cui si è aggiunto l'elemento nuovo.
Risulta inoltre che \(\displaystyle V(n,k+1) = V(n,k)\frac{n-k}{k+1} \). Il ragionamento per arrivarci non è difficile. Se prendi un insieme di cardinalità \(\displaystyle k \) puoi scegliere l'elemento aggiuntivo tra \(n-k\) alternative. Ma così facendo ci saranno \(\displaystyle k+1 \) doppioni per ogni insieme così creato.
Usando queste proprietà li generi tutti.
Vale banalmente l'uguaglianza \(\displaystyle V(n,k) = V(n,n-k) \).
Risulta che \(V(n+1,k) = V(n,k) + V(n,k-1) \). Infatti se tu ingrandisci l'insieme totale con un nuovo elemento, i sottoinsiemi di cardinalità \(\displaystyle k \) sono i sottoinsiemi di cardinalità \(\displaystyle k \) dell'insieme più piccolo uniti ai sottoinsiemi di cardinalità \(\displaystyle k-1 \) a cui si è aggiunto l'elemento nuovo.
Risulta inoltre che \(\displaystyle V(n,k+1) = V(n,k)\frac{n-k}{k+1} \). Il ragionamento per arrivarci non è difficile. Se prendi un insieme di cardinalità \(\displaystyle k \) puoi scegliere l'elemento aggiuntivo tra \(n-k\) alternative. Ma così facendo ci saranno \(\displaystyle k+1 \) doppioni per ogni insieme così creato.
Usando queste proprietà li generi tutti.
$V(n+1,k)=V(n,k)+V(n,k−1)$ Stirling seconda specie?
"johack":
$V(n+1,k)=V(n,k)+V(n,k−1)$ Stirling seconda specie?
Non so a cosa tu stia facendo riferimento. Ho usato la scrittura \(V(n,k)\) per non dover scrivere \(\lvert\{ S\subseteq [n] : \lvert S\rvert = k\}\rvert\). Come ho scritto la si dimostra facendo considerazione sugli insiemi. È inoltre una proprietà piuttosto conosciuta dei coefficienti binomiali.
"vict85":
[quote="johack"]$V(n+1,k)=V(n,k)+V(n,k−1)$ Stirling seconda specie?
Non so a cosa tu stia facendo riferimento. Ho usato la scrittura \(V(n,k)\) per non dover scrivere \(\lvert\{ S\subseteq [n] : \lvert S\rvert = k\}\rvert\). Come ho scritto la si dimostra facendo considerazione sugli insiemi. È inoltre una proprietà piuttosto conosciuta dei coefficienti binomiali.[/quote]
Sto solo dicendo che quella formula che hai scritto, e la spiegazione che hai scritto, assomiglia tanto al numero di Stirling di seconda specie!
Non li conoscevo, non mi occupo di combinatoria. Comunque quella è la proprietà del coefficiente binomiale. Nella formula del numero di Stirling di seconda specie il primo addendo è moltiplicato per k.
capisco, allora mi sono sbagliato io 
faccio confusione molto spesso!!! quindi quella è la dimostrazione?
faccio confusione molto spesso!!! quindi quella è la dimostrazione?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo