L'Uno combinatorio

[vl4dster]

Dimostrare che per ogni $n\geq1$ si ha:

$\sum_{i=1}^n (\sum_{k=0}^{n-i} ((-1)^k) /(k!) )/((i-1)!) = 1$

[_luca.barletta]

Si può procedere per induzione su n:
per $n=1$ è verificato; vera per n (ipotesi induttiva), vediamo per $n+1$:
$sum_(i=1)^(n+1) (sum_(k=0)^(n-i+1)(-1)^k/(k!))/((i-1)!)=sum_(i=1)^(n) (sum_(k=0)^(n-i)(-1)^k/(k!)+(-1)^(n-i+1)/((n-i+1)!))/((i-1)!)+1/(n!)=sum_(i=1)^(n) (sum_(k=0)^(n-i)(-1)^k/(k!))/((i-1)!)+1/(n!)sum_(i=1)^n((n),(i-1))(-1)^(n-i+1)+1/(n!)=1+1/(n!)sum_(i=0)^(n-1)((n),(i))(-1)^(n-i)+1/(n!)=$
$=1+1/(n!)(1-1)^n-1/(n!)+1/(n!)=1$

[vl4dster]

Non e' combinatorioso, ma va certamente bene

Qui c'e' il modo combinatorioso con cui ho trovato la relazione sopra:

Prendiamo $n$ elementi distinti $a_1, ..., a_n$ e consideriamone le permutazioni.
Esprimendo il valore atteso per la variabile aleatoria $X="numero di punti fissi nella permutazione"$
in due modi diversi si ottiene la relazione sopra: in un caso si contano direttamente le permutazioni con $i$
punti fissi per $0<=i<=n$, nell'altro si considerano i punti della permutazione e si nota che ogni punto ha
probabilita' $1/n$ di essere un punto fisso (dunque il valore atteso e' $n(1/n)=1$).