Matematyka dyskretna Kalasznikov: Udowodnij następującą własność:
 
nawias
n
nawias
nawias
k
nawias
 
nawias
2n
nawias
nawias
n
nawias
 
nk=0
2=
   
Stawiam browara za pomoc emotka
30 lis 20:20
jc: Na ile sposobów możesz wybrać n elementowy podzbiór ze zbioru 2n elementowego? Oczywista odpowiedź jest po prawej stronie równość. Możesz też podzielić zbiór 2n elementowy na 2 równe podzbiory, a potem wybierać podzbiory n elementowe wybierając k elementów z pierwszgo podzbioru, a pozostałe n−k z drugiego, k=0,1,2,...,n. Mówi o tym suma po lewej stronie. Stąd równość.
30 lis 20:28
AdamP: "Oczywista odpowiedź jest po prawej stronie równość." No tak, ale jestem w tym zielony ponieważ to moje jedne z pierwszych zajęć z tym tematem. Jak mam to udowodnić?
30 lis 21:40
jc: rysunekWybierasz n elementów ze zbioru 2n elementowego (rysunek). Zbiór 2n elementowy dzielisz wcześniej na 2 równoliczne podzbiory. Aby wybrać n elementów, wybierasz k elementów z lewego podzbioru, a pozostałe n−k z prawego. Dla danego k (k=0,1,2,...)
 
nawias
n
nawias
nawias
k
nawias
nawias
n
nawias
nawias
n−k
nawias
 
nawias
n
nawias
nawias
k
nawias
 
możesz to zrobić na
+
2 sposobów.
   
Sumujesz względem k i to samo, co byś miał wybierając od razu n elementów
 
nawias
2n
nawias
nawias
n
nawias
 
ze zbioru
elementowowego.
  
Oczywiście, co ważne, dla każdego dla różnych k otrzymujesz rozłączne rodziny podzbiorów.
30 lis 21:47
jc: Tam zamiast + powinno być =, popraw sobie.
30 lis 21:48