Somma di binomiali

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

Somma di binomiali

Messaggioda Gizeta » 12/12/2013, 22:46

Dimostrare

1) [tex]\displaystyle \sum_{k=0}^n {n \choose k}=2^n[/tex]

2) [tex]\displaystyle \sum_{k=0}^n {(-1)^k {n \choose k}}=0[/tex]

3) [tex]\displaystyle \sum_{k=1}^n {k{n \choose k}}=n2^{n-1}[/tex]

4) [tex]\displaystyle {n \choose k}+{n \choose k+1}={n+1 \choose k+1}[/tex]

Trovare delle argomentazioni combinatorie per dimostrare

5) [tex]\displaystyle {2n \choose n}=2{n \choose 2}+n^2[/tex]

6) [tex]\displaystyle {2n+2 \choose n+1}={2n \choose n+1}+2{2n \choose n}+{2n \choose n-1}[/tex]

p.s. i primi quattro possono essere risolti sia "algebricamente" che "combinatoriamente", sarebbe più istruttivo farlo in entrambi i modi. Notate, inoltre, che il quinto ed il sesto problema sono figli del quarto per quanto riguarda le argomentazioni da trovare (ed ho hintato anche troppo) :D
Gizeta
 
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Somma di binomiali

Messaggioda Archimede » 13/12/2013, 14:39

Spero soluzione del primo

Testo nascosto:
Aristotele ha[tex]n[/tex] caramelle numerate che vanno messe in due confezioni distinte, in quanti modi può farlo?

-Essendo caramelle numerate io le ordino nella seguente maniera [tex]a_1,a_2,a_3,...,a_n[/tex].
Questo significa che per ogni caramella io posso scegliere se metterla in una confezione o nell'altra. In totale avrò quindi [tex]2^n[/tex] modi per disporle.

-Essendo caramelle ordinate io le ordino nuovamente nella seguente maniera [tex]a_1,a_2,a_3,...,a_n[/tex].
Questo vuol dire che se le metto tutte nella confezione A potrò farlo in[tex]n \choose k[/tex] modi, se ne metto [tex]n-1[/tex] nella confezione A e [tex]1[/tex] nella confezione B potrò farlo in [tex]n \choose n-1[/tex]; e via dicendo fino a quando ne metterò [tex]0[/tex] nella confezione A e[tex]n[/tex] nella confezione B e a quel punto potrò farlo in [tex]n\choose 0[/tex] modi.
In totale avrò quindi[tex]\sum_{k=0}^n {n\choose k}[/tex] modi per farlo

Quindi quello che ho fatto, è stato fornire la stessa soluzione dello stesso problema in due maniere differenti. quindi posso dire che

[tex]\sum_{k=0}^n {n\choose k}=2^n[/tex]


Spero di essere stato chiaro e anche corretto dal punto di vista formale.
Archimede
 
Messaggi: 313
Iscritto il: 27/11/2013, 14:33

Re: Somma di binomiali

Messaggioda Archimede » 13/12/2013, 15:07

Spero soluzione del terzo:

Testo nascosto:
[tex]\sum_{k=1}^n k{n\choose k}=\sum_{k=0}^n k{n\choose k}=\sum_{k=0}^n (n-k){n\choose k}[/tex]

Quindi

[tex]\sum_{k=1}^n k{n\choose k}=\frac{1}{2}\sum_{k=0}^n (k{n\choose k}+(n-k){n\choose k})=[/tex]
[tex]=\frac{n}{2}\sum_{k=0}^n {n\choose k}=\frac{n}{2}2^n=n2^{n-1}[/tex]
Archimede
 
Messaggi: 313
Iscritto il: 27/11/2013, 14:33

Re: Somma di binomiali

Messaggioda afullo » 13/12/2013, 17:47

Il 5 è falso per n=3, più in generale non può essere semplicemente un polinomio quadratico...
afullo
 
Messaggi: 1741
Iscritto il: 13/03/2013, 22:06

Re: Somma di binomiali

Messaggioda Gizeta » 13/12/2013, 19:38

@Archimede.

La prima è corretta, del resto noterai che quel che hai fatto altro non è che contare il numero di sottoinsiemi di un insieme di [tex]n[/tex] elementi in due modi diversi.
La tua riformulazione del problema è un punto di vista alternativo su quello che gli americani chiamano "encoding": per costituire un sottoinsieme di un insieme di [tex]n[/tex] elementi è sufficiente dire per ognuno degli elementi se esso sta o meno nel sottoinsieme, ossia indichiamo tutti gli elementi dell'insieme con una stringa di [tex]n[/tex] [tex]x[/tex], adesso per ogni elemento sostituiamo la [tex]x[/tex] con [tex]y[/tex] se l'elemento sta nel sottoinsieme e con [tex]n[/tex] se non ci sta. Conseguentemente il numero di sottoinsiemi sarà dato dal numero di modi in cui posso costituire la stringa, ossia [tex]2^n[/tex] visto che ho due possibilità per ogni elemento.

Hint per la soluzione algebrica (e anche per il secondo problema):
Testo nascosto:
[tex]\displaystyle (x+y)^n=\sum_{k=0}^n{n \choose k}x^{n-k}y^k[/tex].
Puoi sostituire degli opportuni valori ad [tex]x[/tex] e [tex]y[/tex] per ottenere le somme desiderate?
:D

Nella seconda non è molto chiaro un passaggio

[tex]\displaystyle \sum_{k=0}^n k{n\choose k}=\sum_{k=0}^n (n-k){n\choose k}[/tex]

potresti spiegare perché è vero?

[dovrebbe andare bene la soluzione, comunque].

Te ne propongo una alternativa (ancora algebrica, quindi qualcuno si getti su quella mediante riformulazione del problema :mrgreen: )

Testo nascosto:
Utilizziamo l'utile identità [tex]\displaystyle {n \choose k }=\frac{n}{k}{n-1 \choose k-1}[/tex], allora il testo si traduce in

[tex]\displaystyle n \sum_{k=1}^{n}{n-1 \choose k-1}[/tex] e la sommatoria ha valore [tex]2^{n-1}[/tex], come segue dal primo problema



@Afullo

Non capisco: ho una dimostrazione di questo punto, evidentemente o è fallata oppure presenta qualche particolare nascosto che non ho considerato.
Gizeta
 
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Somma di binomiali

Messaggioda Gizeta » 13/12/2013, 19:42

Non posso modificare più il primo post, in ogni caso il testo del quinto problema è errato. Quello corretto è

[tex]\displaystyle {2n \choose 2}=2{n \choose 2} +n^2[/tex]

Ringrazio Afullo per avermelo fatto notare :mrgreen:
Gizeta
 
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Somma di binomiali

Messaggioda RyzePHi » 13/12/2013, 19:50

Proviamo con il 2) ..Nella formula

[tex]\displaystyle (x+y)^n=\sum_{k=0}^n{n \choose k}x^{n-k}y^k[/tex] poniamo [tex]x=1 \wedge y=-1[/tex] ottenendo così

[tex]\displaystyle \sum_{k=0}^n{n \choose k}(-1)^k=(1-1)^n=0[/tex] dovrebbe essere dimostrata
RyzePHi
 
Messaggi: 119
Iscritto il: 27/11/2013, 12:50

Re: Somma di binomiali

Messaggioda Gizeta » 13/12/2013, 19:59

Ben fatto.
Adesso che vi siete scaldati procedete con gli ultimi tre :P
Gizeta
 
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Somma di binomiali

Messaggioda Archimede » 13/12/2013, 20:15

Gizeta ha scritto:
Nella seconda non è molto chiaro un passaggio

[tex]\displaystyle \sum_{k=0}^n k{n\choose k}=\sum_{k=0}^n (n-k){n\choose k}[/tex]

potresti spiegare perché è vero?



Ok, il ragionamento che ho fatto è il seguente:

Il primo membro equivale alla somma di tutti questi elementi

[tex]n\choose n[/tex] ... [tex]n\choose 2[/tex] [tex]n\choose 1[/tex]
[tex]n\choose n[/tex] ... [tex]n\choose 2[/tex]
.
.
[tex]n\choose n[/tex]

Mentre il secondo alla somma di questi:

[tex]n\choose 0[/tex] ... [tex]n\choose n-2[/tex] [tex]n\choose n-1[/tex]
[tex]n\choose 0[/tex] ... [tex]n\choose n-2[/tex]
.
.
[tex]n\choose 0[/tex]

Quindi l'equivalenza dovrebbe essere stata dimostrata per la seguente identità [tex]{n\choose k}={n\choose n-k}[/tex]
Archimede
 
Messaggi: 313
Iscritto il: 27/11/2013, 14:33

Re: Somma di binomiali

Messaggioda Archimede » 13/12/2013, 21:01

Quarto:

[tex]{n\choose k} + {n\choose {k+1}}=\frac{n!}{k!(n-k)!}+\frac{n!}{(k+1)!(n-k-1)!}=\frac{n!(k+1)+n!(n-k)}{(k+1)!(n-k)!}=[/tex][tex]=\frac{(n+1)!}{(k+1)!(n-k)!}=[/tex][tex]{n+1}\choose {k+1}[/tex]
Archimede
 
Messaggi: 313
Iscritto il: 27/11/2013, 14:33

Prossimo

Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti