Kombinatoryczny dowód równości
[tex]${n \choose 0} + {n \choose 1} + {n \choose 2} +\ldots + {n \choose n}=2^n$[/tex]
jest następujący. Weź zbiór [tex]A[/tex] o [tex]n\in\mathbb{N}[/tex] elementach. Powiedzmy, że chcesz zliczyć moc zbioru [tex]\{X:X\subset A\}[/tex] czyli zbioru potęgowego. Z jednaj strony ta moc to:
[tex]${n \choose 0} + {n \choose 1} + {n \choose 2} +\ldots + {n \choose n}$[/tex]
wszak mamy skończoną liczbę rozłącznych możliwości [tex]|X|=0[/tex] lub [tex]|X|=1[/tex] lub [tex]|X|=2[/tex] itd. aż do [tex]|X|=n[/tex]. Z drugiej strony [tex]X[/tex] można utożsamić z ciągiem [tex]0[/tex] oraz [tex]1[/tex] długości [tex]n[/tex]. Ciąg ten będzie [tex]0[/tex], gdy dany element z [tex]A[/tex] nie znajdzie się w [tex]X[/tex]. Wartość [tex]1[/tex] będzie, gdy się znajdzie. Takich ciągów jest [tex]2^n[/tex] bo na każdym miejscu mamy dwie opcje wyboru [tex]0[/tex] lub [tex]1[/tex]. Teraz wystarczy zauważyć to co w komentarzach było wspomniane
[tex]$ {n \choose k} = {n \choose n-k} $[/tex]
Ta równość kombinatorycznie oznacza jedynie tyle, że aby wybrać [tex]k[/tex] elementów z pośród [tex]n[/tex] równie dobrze można wybrać [tex]n-k[/tex] elektów które się odrzuci pozostawiając wybrane [tex]k[/tex]. Ostatecznie więc
[tex]$2 {41 \choose 1}+2 {41 \choose 2}+\ldots+ 2 {41 \choose 20}=$[/tex]
[tex]$ \Bigg({41 \choose 1}+{41 \choose 40}\Bigg)+\Bigg({41 \choose 2}+{41 \choose 39}\Bigg)+\ldots+ \Bigg({41 \choose 20}+{41 \choose 21}\Bigg)=$[/tex]
[tex]${41 \choose 1}+{41 \choose 2}+{41 \choose 3}+\ldots+{41 \choose 40}$[/tex]
gdyby w tym ostatnim napisie było gdzieś [tex]{41 \choose 0},{41 \choose 41}[/tex] to odpowiedzią było by [tex]2^{41}[/tex]. Ale nie ma... tylko, że [tex]{41 \choose 0}={41 \choose 41}=1[/tex] więc ostateczny wynik to [tex]2^{41}-2.[/tex]
