$ ~ \displaystyle \sum_{i=0}^n (-1)^i {n \choose i} i^n $
Questo forse è uno dei primi problemi di mia invenzione che posto sul forum... però non so quanto è nuovo
Valutare una somma con binomiali
Valutare una somma con binomiali
Trovare quanto fa:
$ ~ \displaystyle \sum_{i=0}^n (-1)^i {n \choose i} i^n $
Questo forse è uno dei primi problemi di mia invenzione che posto sul forum... però non so quanto è nuovo
$ ~ \displaystyle \sum_{i=0}^n (-1)^i {n \choose i} i^n $
Questo forse è uno dei primi problemi di mia invenzione che posto sul forum... però non so quanto è nuovo
-
FrancescoVeneziano
- Site Admin
- Messaggi: 606
- Iscritto il: 01 gen 1970, 01:00
- Località: Genova
- Contatta:
Sbaglio o ve lo facciamo ad ogni stage?
(e in tal caso, cosa sarebbe lecito mettere in quella formula?)
Ah ok, scusami eldriv ma avevo fatto un paio di errori di calcolo, e mi veniva che quella cosa facesse: -1, 3, -6, 0, -120,.. e mi sembrava improbabile che esistesse una formula bella per una cosa simile tutto qui...
Quindi la tesi ora e' che per ogni n intero positivo:
$ ~\displaystyle\sum_{i=0}^n (-1)^{i}{n\choose i}(n-i)^n=n! $
Comunque e' un problema carino, non lo avevo mai visto prima (anche perche' altrimenti non avrei fatto quell'intervento idiota
).
Quindi la tesi ora e' che per ogni n intero positivo:
$ ~\displaystyle\sum_{i=0}^n (-1)^{i}{n\choose i}(n-i)^n=n! $
Comunque e' un problema carino, non lo avevo mai visto prima (anche perche' altrimenti non avrei fatto quell'intervento idiota
).Fondatore dell'associazione "Non uno di meno", per lo sterminio massiccio dei nani e affini.
-
giulia.sim
- Messaggi: 6
- Iscritto il: 21 giu 2007, 23:20
carissimi,Febo ha scritto: Quindi la tesi ora e' che per ogni n intero positivo:
$ ~\displaystyle\sum_{i=0}^n (-1)^{i}{n\choose i}(n-i)^n=n! $
Comunque e' un problema carino, non lo avevo mai visto prima (anche perche' altrimenti non avrei fatto quell'intervento idiota
sapete se esiste una generalizzazione di quanto scritto sopra?
$ ~\displaystyle\sum_{i=0}^n (-1)^{i}{n\choose i}(n-i)^M $
grazie!
Giulia
giulia.sim
Re: Valutare una somma con binomiali
edriv ha scritto:Trovare quanto fa:
$ ~ \displaystyle \sum_{i=0}^n (-1)^i {n \choose i} i^n $
Questo forse è uno dei primi problemi di mia invenzione che posto sul forum... però non so quanto è nuovo
Forse è una domanda banale ,ma la faccio lo stesso...per le olimpiadi bisogna saperle fare queste qua??"Tutti sanno che una cosa è impossibile da realizzare,poi arriva uno sprovveduto che non lo sa e la inventa" A.Einstein
Per adesso la mia meta è Cesenatico (ed è già tanto se passo le provinciali perchè è il primo anno che le faccio)...comunque,grazie mille!!!edriv ha scritto:Wei, non è che se non ti viene un problema [neanche facile] non puoi fare le olimpiadi
Ovviamente la risposta alla domanda è: dipende a cosa punti!
Se punti ad arrivare a Cesenatico, la risposta è decisamente no!
"Tutti sanno che una cosa è impossibile da realizzare,poi arriva uno sprovveduto che non lo sa e la inventa" A.Einstein
Non occorre rifarla. C'è già.
Fa parte della lezione di Combinatoria 1 dello stage senior di Pisa (ad esempio è in fondo a quella che ho tenuto io nel 2006).
Bisogna andare sulla pagina del coach, schegliere Video, e poi cercare pdf e avi (metto anche i link diretti).
Segnalo la disponibilità di questo materiale, così magari qualche giovane nuovo è incentivato a scaricarsi anche le altre lezioni e metterle a frutto.
Fa parte della lezione di Combinatoria 1 dello stage senior di Pisa (ad esempio è in fondo a quella che ho tenuto io nel 2006).
Bisogna andare sulla pagina del coach, schegliere Video, e poi cercare pdf e avi (metto anche i link diretti).
Segnalo la disponibilità di questo materiale, così magari qualche giovane nuovo è incentivato a scaricarsi anche le altre lezioni e metterle a frutto.
Vabbeh ... mi scoccia, sta cosa ... con la certezza di postare inutilmente, ecco.
In fondo, si tratta semplicemente di farci un po' d'abitudine: se mai c'è un conteggio sotto, ci sono di solito alcuni caratteri rivelatori, che si impara a conoscere... e tutti ovvi, presi singolarmente.
1) i segni alterni : l'unica cosa che sputa segni alterni, tra i conteggi elementari, è il principio di inclusione-esclusione
2) il risultato $ n! $: stiamo contando le permutazioni di un insieme di n elementi
3) i binomiali: stiamo scegliendo sottoinsiemi
Ora, per contare le permutazioni tramite l'inclusione-esclusione abbiamo due possibilità: vederle come unione di sottoinsiemi non disgiunti, oppure vederle come complementare (in qualche insieme più grande) di un'unione.
Nel primo modo dovremo decidere una caratteristica della permutazione (ad es. il numero di punti fissi) e contare secondo quella, ma tendenzialmente così rispuntano allegramente fattoriali, non potenze n-esime dell'indice di somma, in quanto ci si riduce di solito alle permutazioni di insiemi più piccoli.
Nel secondo modo, dobbiamo decidere in quale "ambiente" operare... il primo termine è $ n^n $, che è il numero di funzioni da {1,...,n} in sé; le permutazioni sono le funzioni bigettive. Ora, perché una funzione da un insieme finito in sé sia bigettiva, basta provare una tra iniettività e surgettività; ad esempio, se escludiamo tutte le funzioni che non sono surgettive, ci rimarranno solo le funzioni bigettive.
Qui interviene la scelta di un sottoinsieme: togliamo quelle che non contengono un certo elemento nella propria immagine, ovvero scegliamo un sottoinsieme di n-1 elementi in cui sia contenuta l'immagine: abbiamo $ {n\choose n-1} $ modi di scegliere l'insieme e abbiamo, per ciascuna scelta, $ (n-1)^n $ funzioni da {1,...,n} in lui. Ovviamente, ora parte l'I-E perché abbiamo contato più volte quelle escludono dalla propria immagine più di un elemento.
Le funzioni da {1,...,n} in sé che hanno immagine di k elementi o meno sono $ {n \choose k} k^n $ e dunque il numero delle permutazioni è
$ \displaystyle{n^n-{n\choose n-1}(n-1)^n+{n\choose n-2}(n-2)^n-\ldots(-1)^{n-1}{n\choose 1}1^n} $
che è la nostra sommatoria moltiplicata per $ (-1)^n $.
Dunque tale sommatoria fa $ (-1)^nn! $.
In fondo, si tratta semplicemente di farci un po' d'abitudine: se mai c'è un conteggio sotto, ci sono di solito alcuni caratteri rivelatori, che si impara a conoscere... e tutti ovvi, presi singolarmente.
1) i segni alterni : l'unica cosa che sputa segni alterni, tra i conteggi elementari, è il principio di inclusione-esclusione
2) il risultato $ n! $: stiamo contando le permutazioni di un insieme di n elementi
3) i binomiali: stiamo scegliendo sottoinsiemi
Ora, per contare le permutazioni tramite l'inclusione-esclusione abbiamo due possibilità: vederle come unione di sottoinsiemi non disgiunti, oppure vederle come complementare (in qualche insieme più grande) di un'unione.
Nel primo modo dovremo decidere una caratteristica della permutazione (ad es. il numero di punti fissi) e contare secondo quella, ma tendenzialmente così rispuntano allegramente fattoriali, non potenze n-esime dell'indice di somma, in quanto ci si riduce di solito alle permutazioni di insiemi più piccoli.
Nel secondo modo, dobbiamo decidere in quale "ambiente" operare... il primo termine è $ n^n $, che è il numero di funzioni da {1,...,n} in sé; le permutazioni sono le funzioni bigettive. Ora, perché una funzione da un insieme finito in sé sia bigettiva, basta provare una tra iniettività e surgettività; ad esempio, se escludiamo tutte le funzioni che non sono surgettive, ci rimarranno solo le funzioni bigettive.
Qui interviene la scelta di un sottoinsieme: togliamo quelle che non contengono un certo elemento nella propria immagine, ovvero scegliamo un sottoinsieme di n-1 elementi in cui sia contenuta l'immagine: abbiamo $ {n\choose n-1} $ modi di scegliere l'insieme e abbiamo, per ciascuna scelta, $ (n-1)^n $ funzioni da {1,...,n} in lui. Ovviamente, ora parte l'I-E perché abbiamo contato più volte quelle escludono dalla propria immagine più di un elemento.
Le funzioni da {1,...,n} in sé che hanno immagine di k elementi o meno sono $ {n \choose k} k^n $ e dunque il numero delle permutazioni è
$ \displaystyle{n^n-{n\choose n-1}(n-1)^n+{n\choose n-2}(n-2)^n-\ldots(-1)^{n-1}{n\choose 1}1^n} $
che è la nostra sommatoria moltiplicata per $ (-1)^n $.
Dunque tale sommatoria fa $ (-1)^nn! $.