Uguaglianza di somme
Sono alle prime armi con le sommatorie.
Potresti darmi una mano per dimostrare che:
\(\displaystyle \displaystyle\sum_{i=0}^{b}(-1)^i \displaystyle\binom {b}{i} (b-i)^b= \displaystyle\sum_{i=0}^{b}(-1)^{b+i}\displaystyle\binom{b}{i}i^b=b! \)
Dove il primo membro è la cardinalità dell'insieme delle funzioni surgettive \(\displaystyle f:\mathbb{A} \rightarrow \mathbb{B} \) quando la cardinalità dei due insiemi è la stessa, esso è uguale quindi ad \(\displaystyle b! \).
Il fatto è che non riesco a dimostrare l'uguaglianza delle somme potreste suggerirmi qualcosa?
Grazie mille.
Potresti darmi una mano per dimostrare che:
\(\displaystyle \displaystyle\sum_{i=0}^{b}(-1)^i \displaystyle\binom {b}{i} (b-i)^b= \displaystyle\sum_{i=0}^{b}(-1)^{b+i}\displaystyle\binom{b}{i}i^b=b! \)
Dove il primo membro è la cardinalità dell'insieme delle funzioni surgettive \(\displaystyle f:\mathbb{A} \rightarrow \mathbb{B} \) quando la cardinalità dei due insiemi è la stessa, esso è uguale quindi ad \(\displaystyle b! \).
Il fatto è che non riesco a dimostrare l'uguaglianza delle somme potreste suggerirmi qualcosa?
Grazie mille.
Risposte
Ciao!
Hai provato per induzione su b?
La base induttiva sarebbe vera,
ed inoltre gli operatori coinvolti in quest'uguaglianza sono particolarmente adatti ad un approccio ricorsivo:
dovrebbe funzionare..
Saluti dal web.
Hai provato per induzione su b?
La base induttiva sarebbe vera,
ed inoltre gli operatori coinvolti in quest'uguaglianza sono particolarmente adatti ad un approccio ricorsivo:
dovrebbe funzionare..
Saluti dal web.
"giannirecanati":
\(\displaystyle \displaystyle\sum_{i=0}^{b}(-1)^i \displaystyle\binom {b}{i} (b-i)^b= \displaystyle\sum_{i=0}^{b}(-1)^{b+i}\displaystyle\binom{b}{i}i^b=b! \)[...]
Il fatto è che non riesco a dimostrare l'uguaglianza delle somme potreste suggerirmi qualcosa?
L'induzione che suggerisce theras potrebbe anche andare ma io farei una cosa più diretta: un cambiamento di variabile. L'autore che stai leggendo usa \(i\) come variabile di sommazione in entrambi i membri della
\[\displaystyle \displaystyle\sum_{i=0}^{b}(-1)^i \displaystyle\binom {b}{i} (b-i)^b= \displaystyle\sum_{i=0}^{b}(-1)^{b+i}\displaystyle\binom{b}{i}i^b;\]
ma se provi a riscrivere
\[\displaystyle \displaystyle\sum_{i=0}^{b}(-1)^i \displaystyle\binom {b}{i} (b-i)^b= \displaystyle\sum_{j=0}^{b}(-1)^{b+j}\displaystyle\binom{b}{j}j^b\]
ti accorgi che la seconda somma si ottiene dalla prima ponendo \(j=b-i\) e sfruttando l'identità combinatoria
\[\binom{b}{j}=\binom{b}{b-j}.\]
Vi ringrazio tanto, era un po' che ci provavo! 
"dissonance":.
L'induzione che suggerisce theras potrebbe anche andare ma io farei una cosa più diretta: un cambiamento di variabile. L'autore che stai leggendo usa \(i\) come variabile di sommazione in entrambi i membri della
\[\displaystyle \displaystyle\sum_{i=0}^{b}(-1)^i \displaystyle\binom {b}{i} (b-i)^b= \displaystyle\sum_{i=0}^{b}(-1)^{b+i}\displaystyle\binom{b}{i}i^b;\]
ma se provi a riscrivere
\[\displaystyle \displaystyle\sum_{i=0}^{b}(-1)^i \displaystyle\binom {b}{i} (b-i)^b= \displaystyle\sum_{j=0}^{b}(-1)^{b+j}\displaystyle\binom{b}{j}j^b\]
ti accorgi che la seconda somma si ottiene dalla prima ponendo \(j=b-i\) e sfruttando l'identità combinatoria
\[\binom{b}{j}=\binom{b}{b-j}.\]
La tua verifica avrebbe più o meno lo stesso numero di passaggi del procedimento da me suggerito,
ma sarebbe di certo concettualmente più semplice:
non foss'altro perchè non richiede la laboriosità del metodo d'induzione e perchè usa una delle identità combinatorie
più intuitive,
mentre dimostrandola ricorsivamente salta fuori la necessità d'usare l'uguaglianza di Stiefel
(che sebbene concettualmente comprensibile,ed implicitamente nota dalle superiori,
quando si usa formalmente,vedi verifica per induzione della formula del binomio di Newton,
diventa davvero una "formulaccia"!).
Saluti dal web.
"theras":
[...]l'uguaglianza di Stiefel
(che sebbene concettualmente comprensibile,ed implicitamente nota dalle superiori,
quando si usa formalmente,vedi verifica per induzione della formula del binomio di Newton,
diventa davvero una "formulaccia"!)
Una formulaccia incomprensibile, sono pienamente d'accordo. A meno che uno non faccia un disegnino come questa bellissima animazione di Wikipedia:
e grosso modo tutte le identità combinatorie elementari con il coefficiente binomiale si possono esprimere graficamente in modo simile sul triangolo di Tartaglia, rendendole parecchio più trasparenti (in inglese, per esempio, leggevo di recente che si parla di "identità hockey stick").
Comunque, a parte questo, il fatto è che personalmente sono contrario ad usare la regola di induzione per dimostrare queste identità se non quando strettamente necessario. Una dimostrazione del genere condotta per induzione è formalmente ineccepibile ma lascia un senso di insoddisfazione: si conclude che "l'identità è vera perché lo dicono i calcoli" ma il meccanismo che ha condotto al risultato resta misterioso.
"dissonance":
(...)
Stupendo! adesso non scorderò più una di quelle uguaglianze che ogni volta non riuscivo a ricordare bene e dovevo andarmi a riguardare/ricalcolare
! E una volta che ci si pensa è così banale!!
"dissonance":
[quote="theras"][...]l'uguaglianza di Stiefel
(che sebbene concettualmente comprensibile,ed implicitamente nota dalle superiori,
quando si usa formalmente,vedi verifica per induzione della formula del binomio di Newton,
diventa davvero una "formulaccia"!)
Una formulaccia incomprensibile, sono pienamente d'accordo. A meno che uno non faccia un disegnino come questa bellissima animazione di Wikipedia:
e grosso modo tutte le identità combinatorie elementari con il coefficiente binomiale si possono esprimere graficamente in modo simile sul triangolo di Tartaglia, rendendole parecchio più trasparenti (in inglese, per esempio, leggevo di recente che si parla di "identità hockey stick").
Comunque, a parte questo, il fatto è che personalmente sono contrario ad usare la regola di induzione per dimostrare queste identità se non quando strettamente necessario. Una dimostrazione del genere condotta per induzione è formalmente ineccepibile ma lascia un senso di insoddisfazione: si conclude che "l'identità è vera perché lo dicono i calcoli" ma il meccanismo che ha condotto al risultato resta misterioso.[/quote]
Pericolo scampato:
credevo d'averti offeso senza volerlo..
Bella l'animazione:
d'altronde è quello che senza saperne bene il perchè si faceva al I° anno delle superiori,
e che ricordo benissimo mise al III° esplicitamente in evidenza la mia stupenda
(in tutti i sensi..)
prof. di Calcolo,Statistica e Probabilità,
quando le venne il dubbio che le nostre facce inebetite non fossero solo legate al nostro innamoramento collettivo ma pure all'incomprensibilità della formula che aveva appena scritto!
Saluti dal web.
P.S.Comunque la formula che tu hai usato s'usa ricordare con la frase
"I modi di scegliere k elementi tra n sono tanti quanti i modi di lasciarne fuori (n-k),
i quali a loro volta sono tanti quanti i modi di sceglier (n-k) elementi da lasciar fuori tra quegli n";
in fondo è una corrispondenza biunivoca semplice da vedere,
con successiva enumerazione dei due insiemi su cui essa opera ed ovvia imposizione della loro equicardinalità,
che rende più "simpatica",memorizzabile ed intuitiva quell'uguaglanza combinatoria:
non credi che qualche pensata del genere anche per quella formulaccia,
per non renderla subito odiosa,
non dev'essere troppo impossibile da trovare?
Saluti dal web.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo