Calcolo combinatorio

[eccelsius]

Ciao a tutti,
sulle slide c'è questo esercizio:
"Quanti sono i sottoinsiemi di un insieme di 12 elementi?"
Sulle slide è riportata la risposta $2^12$.
Secondo me però dovrebbe essere:
$\sum_{k=0}^12((12),(k))$
perchè ogni sottoinsieme può avere un numero variabile di elementi da 12 (l'insieme stesso) a 0 (l'insieme vuoto) e quindi devo calcolare le combinazioni semplici per ogni numero di elementi dei possibili sottoinsiemi.
Spero di essermi espresso nel modo corretto.
Grazie a chi mi risponderà

[tommik]

Secondo me però dovrebbe essere:
$\sum_{k=0}^12((12),(k))$

Grazie a chi mi risponderà

Non posso dire che tu abbia torto però osserva che, utilizzando lo sviluppo del binomio di Newton, ciò che hai scritto tu viene:

$sum_(k=0)^12 ((12),(k))=(1+1)^12=2^12$


... e quindi non vedo molte differenze fra la tua soluzione e quella delle slide.

Prego.

Ps: per gli argomenti di calcolo combinatorio abbiamo una sezione dedicata: Statistica e Probabilità, dove tra l'altro hai già scritto più volte....

[eccelsius]

Si, scusami devo aver sbagliato sezione.
Dopo la tua risposta mi sono andato ad informare in giro e ho scoperto la formula $\sum_{k=0}^{m}((n),(k))=2^m$ che prima non conoscevo quindi non avevo collegato il mio risultato con quello delle slide.
Grazie

[tommik]

... mi sono andato ad informare in giro e ho scoperto la formula $\sum_{k=0}^{m}((n),(k))=2^m$ che prima non conoscevo ...

Sì ma comel'hai scritta ora è sbagliata, devi mettere $((m),(k))$ non $((n),(k))$.

Inoltre dovresti notare come esce il risultato sviluppando la potenza di un binomio; non c'è nulla di arcano né da imparare a memoria, basta osservare che


$(a+b)^n= ((n),(0))a^n b^0+((n),(1))a^(n-1)b^1+...+((n),(n))a^0b^n$

Ora, se sviluppi

$(1+1)^n$ ottieni proprio

$((n),(0))+((n),(1))+...+((n),(n))=sum_(i=0)^n((n),(i))$

Appunto si chiamano coefficienti binomiali perché sono i coefficienti dello sviluppo della potenza del binomio.