algebra

[Ramo82]

dimostrare in almeno 3 modi diversi che dato un insieme A d n elementi il suo insieme delle parti P(A) ha 2^n elementi.
Un mio collega qlc anno fa è stato bocciato x averlo saputo dimostrare "solo" in 2 modi =__=

[Valerio Capraro]

1) liberamente tratta da una dimostrazione di Karl:
la somma dei coefficienti binomiali da n su 0 a n su n dà il numero dei sottoinsiemi di un insieme di n elementi; ma tale somma è lo sviluppo di newton di (1+1)^n = 2^n

2) per induzione. faccio solo il passo induttivo: supponiamo che un insieme di cardinalità n abbia come insieme delle parti un insieme di cardinalità 2^n; sia A un insieme di cardinalità n+1, fissato in A un elemento, ogni sottoinsieme di cardinalità n o contiene quell'elemento o non lo contiene; in entrambi i casi ci sono 2^n modi in cui può contenerlo o non contenerlo, dall'ipotesi induttiva. quindi la cardinalità di P(B)=2^n+2^n che equivale alla tesi

3) ragioniamo sempre coi coefficienti binomiali, ma dimostriamo questa volta per induzione. tralascio la dimostrazione che è piuttosto semplice e saprai sicuramente ricostruirla da sola.

ciao, ubermensch

[Ramo82]

nn conoscevo la seconda...
al suo posto facevo quella che utilizza la funzione caratteristica...

[Valerio Capraro]

se è quella che penso io credo siano equivalenti... però non mi è molto simpatica quella dimostrazione!

[Ramo82]

si è + o meno la stessa ma nn si fa x induzione... xchè t sta antipatica??? secondo me nn è male come dimostrazione..

[Valerio Capraro]

perchè me l'ha fatta quella di calcolo delle probabilità!<img src=icon_smile.gif border=0 align=middle>