OliForum Matematico

Luca ha n amici. Quando esce con loro, ognuno di essi gli dà un euro. Se Luca esce con ogni possibile sottoinsieme di n, quanti euro avrà guadagnato alla fine?

Luca può uscire con un insieme di 1,2,3...n amici.
Quindi distinguiamo i casi...
-quando esce con 1 persona lo può fare in $n$ modi, quindi sono $n$ euro
-quando esce con 2 persone lo può fare in $\binom{n}{2}$ modi, ma ognuno di questi modi va moltiplicato per 2, dato che riceve 2 euro...
-questo ragionamento si applica per ogni $\binom{n}{k}$ con $k\leq n$, quindi il risultato è:
$\displaystyle \sum_{K=1}^{n} k \binom{n}{k}$

E il tuo risultato diventa...

Non ho capito il ragionamento di Drago perché sono arrivato alla soluzione attraverso un'altra strada... Comunque confermo che la formula è giusta, ma c'è un modo più stringato di scriverla

Provo a trovare una formula chiusa per la somma:
$ \displaystyle \sum_{k=0}^{n} k \binom{n}{k}=\displaystyle \sum_{k=0}^{n} k\cdot\binom{n-1}{k-1}+\displaystyle \sum_{k=0}^{n-1}k\cdot\binom{n-1}{k} $
Adesso sviluppiamo a parte le due somme:
$ \displaystyle \sum_{k=0}^{n} k\cdot\binom{n-1}{k-1}=\sum_{k=0}^{n-1}(k+1)\binom{n-1}{k}=\sum_{k=0}^{n-1}k\binom{n-1}{k}+ \sum_{k=0}^{n-1}\binom{n-1}{k}= $

$ \displaystyle\sum_{k=0}^{n-1}k\binom{n-1}{k}+ 2^{n-1}=\sum_{k=0}^{n-1}(n-1)\binom{n-2}{k-1}+ 2^{n-1}=n2^{n-2}-2^{n-2}+2^{n-1}=(n+1)2^{n-2} $

Sviluppiamo adesso l'altra formula:
$ \displaystyle \sum_{k=0}^{n-1} k\cdot\binom{n-1}{k}=\sum_{k=0}^{n-1}(n-1)\binom{n-2}{k-1}=n2^{n-2}-2^{n-2} $

Adesso sommiamo i due risultati ed otteniamo:
$ (n+1)2^{n-2}+(n-1)2^{n-2}=n2^{n-1} $

Un ringraziamento ad enigma!

Io avrei usato $\displaystyle{\binom n k=\frac n k\binom{n-1}{k-1}}$ e $\displaystyle{\sum_{i=0}^n\binom n i=2^n}$ ed in un paio di passaggi arrivavo alla tua soluzione...

Oppure, in quanti sottoinsiemi compare un certo amico? $2^{n-1}$, quindi il numero è proprio $n2^{n-1}$!

Però è anche ben che impariate ad usare le interpretazioni combinatorie: se da un lato con questo procedimento è solo questione di qualche conto e si è sicuri di arrivare in fondo, l'altro metodo è più elegante e si risparmia spazio.

Fico è geniale quell'approccio E chi ci avrebbe pensato? xD

Sonner ha scritto:Oppure, in quanti sottoinsiemi compare un certo amico? $2^{n-1}$

Sarebbe molto bello... se riuscissi a capire perchè...

Se tu assumi che un certo amico compare, gli altri n-1 amici possono o comparire o non comparire, quindi per ognuno dei rimanenti ci sono 2 possibilità.

xXStephXx ha scritto:Se tu assumi che un certo amico compare, gli altri n-1 amici possono o comparire o non comparire, quindi per ognuno dei rimanenti ci sono 2 possibilità.

Wow, geniale!

senza formule varie, usando solo il fatto che $\binom{n}{k}=\binom{n}{n-k}$.
arrivati alla somma $\sum^{n}_{i=0}i{\binom{n}{i}}$ e sfruttando il fatto sopra, vediamo che quella somma è uguale a $\frac{n}{2}\sum^n_{i=0}{\binom{n}{i}}+\frac{n}{2}$, e questa è uguale a $\frac{n(2^n-1)}{2}+\frac{n}{2}=n2^{n-1}$

Per chi conosce le derivate può essere anche carino osservare che

$ (1 + x)^n = \sum_{i = 0}^{n} \binom{n}{i}x^i $

e dunque, derivando,

$ n \cdot (1 + x)^{n - 1} = \sum_{i = 1}^{n} \binom{n}{i} \cdot i x^{i -1}. $

Per $ x = 1 $ si ottiene proprio $ n \cdot 2^{n - 1} = \sum_{i = 0}^{n} \binom{n}{i} \cdot i. $

ne approfitto per uppare un poco questo... Il secondo è una generalizzazione della sommatoria che si è dovuta risolvere in questo problema

Tanto per non farlo cadere nel dimenticatoio, visto che qualcuno mi aveva promesso una soluzione con le funzioni generatrici XD