OliForum Matematico

Spero non sia già stato postato: trovare una forma chiusa per $ \displaystyle \sum_{k=1}^{n}k^{2}\binom{n}{k} $

Può essere una cosa del genere: $ (n+n^2)2^{n-2} $?

Hawk ha scritto:Può essere una cosa del genere: $ (n+n^2)2^{n-2} $?

No, prendi $n=3$, ottieni $1^2 \cdot 1+ 2^2 \cdot 3 + 3^2 \cdot 3 + 4^2 \cdot 1 = 1 + 12 + 27 + 16 = 56$, mentre $(3+3^2)2^{3-2} = (12)\cdot 2^{3-2}= 12 \cdot 2 = 24$

Non capisco come hai svolto i conti a me viene:

$ \displaystyle\sum_{k=1}^{3} k^2\cdot\displaystyle\binom{3}{k} $

$ 1\cdot\displaystyle\binom{3}{1}=1\cdot\displaystyle\frac{3!}{(3-1)!1!}=3 $

$ 4\cdot\displaystyle\binom{3}{2}=4\cdot\displaystyle\frac{3!}{(3-2)!2!}=12 $

$ 9\cdot\displaystyle\binom{3}{3}=9\cdot\displaystyle\frac{3!}{(3-3)!3!}=9 $

$ 3+12+9=24 $

Hawk ha scritto:Non capisco come hai svolto i conti a me viene:

$ \displaystyle\sum_{k=1}^{3} k^2\cdot\displaystyle\binom{3}{k} $

$ 1\cdot\displaystyle\binom{3}{1}=1\cdot\displaystyle\frac{3!}{(3-1)!1!}=3 $

$ 4\cdot\displaystyle\binom{3}{2}=4\cdot\displaystyle\frac{3!}{(3-2)!2!}=12 $

$ 9\cdot\displaystyle\binom{3}{3}=9\cdot\displaystyle\frac{3!}{(3-3)!3!}=9 $

$ 3+12+9=24 $

mi sono accorto solo ora che c'è un $k$ da $1$ a $n$.. e non da $0$ a $n$ (per la precisione, ho svolto i conti con k da 0 a n nei coefficienti, e poi li ho moltiplicati per $(k+1)^2$ anzichè per $k$)..

Sonner ha scritto:Spero non sia già stato postato: trovare una forma chiusa per $ \displaystyle \sum_{k=1}^{n}k^{2}\binom{n}{k} $

$ \displaystyle \sum_{k=1}^{n}k^{2}\binom{n}{k}=n \sum_{k=1}^{n}k\binom{n-1}{k-1}=n \sum_{k=0}^{n-1}(k+1)\binom{n-1}{k}=n\left ( \sum_{k=0}^{n-1}k\binom{n-1}{k}+ \sum_{k=0}^{n-1}\binom{n-1}{k} \right )= $
$ \displaystyle =n\left ( \sum_{k=0}^{n-1}k\binom{n-1}{k}+ 2^{n-1} \right )=n\left ( \sum_{k=0}^{n-1}(n-1)\binom{n-2}{k-1}+ 2^{n-1} \right )=n(n2^{n-2}-2^{n-2}+2^{n-1})=n(n+1)2^{n-2} $
dove si è usato $ \displaystyle \sum _{i=0}^j \binom j i =2^j $ e $ \displaystyle \binom j i =\frac j i \binom {j-1} {i-1} $.
Rilancio per i novellini: trovate una dimostrazione combinatoria delle due identità che ho usato, e del risultato.

@<enigma>: per favore spezza l'espressione, che la fine non si vede neanche zoomando
Un metodo per risolverlo può essere in pura combinatoria: la somma vuol dire il numero di modi in cui scelgo un k, poi un insieme di k elementi e infine un capo e il suo vice, che eventualmente possono essere la stessa persona. Ora giro il conteggio: scelgo prima un capo e il suo vice e poi guardo il numero di sottoinsiemi dove posso metterli. Quindi distinguo i 2 casi:
-il capo e il vice coincidono: lo scelgo in n modi e li posso inserire in $2^{n-1}$ sottoinsiemi
-il capo è diverso dal vice: scelgo il capo in n modi e il vice in n-1 modi e ho $2^{n-2}$ sottoinsiemi in cui inserirli.
Quindi la somma fa $n\cdot 2^{n-1}+n(n-1)\cdot 2^{n-2}=n(n+1)\cdot 2^{n-2}$

L'avevo proposto visto che mi stavo interessando di generatrici e stavo appunto leggendo quella famosa dispensa "generatingfunctionology". Mi piaceva l'idea di fare in modo alternativo identità di questo tipo... in particolare questa qui, penso di essere riuscito a farla con le derivate, ma c'è un modo "elementare" (insomma un modo semplice con le generatrici, anche se queste non mi sembrano proprio elementari)?

<enigma> ha scritto:dove si è usato $ \displaystyle \sum _{i=0}^j \binom j i =2^j $ e $ \displaystyle \binom j i =\frac j i \binom {j-1} {i-1} $.
Rilancio per i novellini: trovate una dimostrazione combinatoria delle due identità che ho usato, e del risultato.

Per la seconda basta svolgere: $ \displaystyle{{j! \over i!(j-i)!} = {j \over i}\cdot{(j-1)! \over (i-1)![j-1-(i-1)]!}} $
Per l'altra ci penso un po'...

Provo l'altra, spero anche stavolta che sia corretto:

$ S_j=\displaystyle\sum_{i=0}^j\displaystyle\binom{j}{i}=\displaystyle\sum_{i=0}^j\displaystyle\binom{j-1}{i}+\displaystyle\binom{j-1}{i-1}= $

$ S_j=\displaystyle\sum_{i=0}^{j-1}\binom{j-1}{i}+\displaystyle\sum_{i=0}^{j-1}\binom{j-1}{i}=2\displaystyle\sum_{i=0}^{j-1}\binom{j-1}{i}= $

$ 2S_{j-1}=2^j $