OliForum Matematico

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

Sbaglio o ve lo facciamo ad ogni stage?
A parte questo, fatelo perché è un esercizio simpatico.

A questo punto la tentazione di cancellare tutto è alta, però... tanto vale mettersi alla gogna

Scusa edriv, ma che vuol dire quanto fa? Io direi che fa se stesso.. Oppure bisogna trovare una formula senza sommatoria (e in tal caso, cosa sarebbe lecito mettere in quella formula?)

Grazie in anticipo...

Se provavi con n=1,2,3,4 potevi accorgerti che quella roba fa n!
Se ho messo questo problema vuol dire che quella sommatoria fa qualcosa di sensato oltre che se stessa, volevo lasciare a voi il lavoro di trovare cos'era!

Fra, a me così ben noto non sembra. Hai visto bene quell'$ i^n $ ?

btw... così com'è scritta fa $ (-1)^n n! $.

[edit] Mi ha fatto notare Francesco che effettivamente è un conteggio ben noto... si vede che quest'anno ho fatto combinatoria 2

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 ).

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 ).

carissimi,
sapete se esiste una generalizzazione di quanto scritto sopra?

$ ~\displaystyle\sum_{i=0}^n (-1)^{i}{n\choose i}(n-i)^M $

grazie!

Giulia

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??

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!

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!

Per adesso la mia meta è Cesenatico (ed è già tanto se passo le provinciali perchè è il primo anno che le faccio)...comunque,grazie mille!!!

Però qualcuno potrebbe anche farlo sto esercizio ... (nn costringetemi a postare una soluzione di combinatoria... non voglio rendermi ridicolo).

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.

Beh, mi spiaceva che rimanesse qui senza soluzione... e mi spiaceva anche che nessuno si mettesse a farla.. le lezioni di combinatoria degli stage non le ho mai guardate, ma l'idea (credo sia poi sempre la stessa) con cui farla è carina.

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! $.