Symbol Newtona Trututu: Jak udowodnić symbol Newtona? Muszę udowodnić, wyjaśnić dlaczego (n nad k) = n!/(n − k)! * k! Kompletnie nie mam pojęcia jak się za to zabrać. Pani dała nam wskazówkę, zaczęła to rozpisywać na jakieś ciągi, n miejsc, k miejsc, jakieś podziały, nawet nie wiem jak to opisać, bo nic nie zrozumiałam z tego. Ma ktoś pomysł?

Basia: co udowodnić ? przecież to jest definicja

n k		n!
	=
		k!*(n−k)!

chyba czegoś nie zrozumiałeś, albo nie zapisałeś

Basia:

	n k
nie chodzi przypadkiem o to, że k elementów spośród n można wybrać na		sposobów

jeżeli ich kolejność nie ma znaczenia albo inaczej:

	n k
liczba k−elementowych podzbiorów zbioru n−elementowego (0≤k≤n) jest równa		?

Trututu: Wiem,że to definicja, ale mamy wyjaśnić skąd to się wzięło, coś z kombinatoryką chyba mówiła, że mamy to właśnie jakoś rozpisać czy coś. Najpierw było zadanie, żeby wykazać, że (n nad k) = 2ⁿ i że liczba podzbiorów k−elementowych zbioru n−elementowego to też 2ⁿ. I potem właśnie pani zaczęła o ttym mówić. Może faktycznie źle zrozumiałam, bo tego nie rozumiem, ale w takim razie co z tego zadania można udowodnić? Bo te oba zadania z 2ⁿ już mamy zrobione.

Basia: Totalny chaos zapanował w Twojej głowie. Jest tak:

	n k
1.		≠ 2n

	n 0		n 1		n n
2.		+		+....+		= 2n

3. 2ⁿ to liczba wszystkich podzbiorów zbioru n−elementowego

	n k
4.		to liczba k−elementowych podzbiorów zbioru n− elementowego gdzie 0≤k≤n

czy masz udowodnić (4) ?

Trututu: A właściwie, może chodzi o to drugie co napisałaś... Ale jak mamy, że n nad k = 2ⁿ i liczba tych podzbiorów to też 2ⁿ, to czy trzeba udowadniać, że liczba tych podzbiorów to n nad k?

Trututu: No dobra niech będzie numer 4, zaryzykuję punkty najwyżej. Dasz jakąś wskazówkę jak to zrobić?

Basia: (2) dowodzi się znacznie prościej

	n 0		n 1		n n
2n =(1+1)n =		*1n*10+		*1n−1*11+....+		*10*1n =

n 0		n 1		n n
	+		+....+

k nie może być = 2ⁿ, bo w symbolu Newtona 0≤k≤n a 2ⁿ > n dla każdego n∊N

	n k
to, że liczba k−elementowych podzbiorów zbioru n−elementowego =

dość łatwo da się udowodnić to, że liczba wszystkich podzbiorów zbioru n−elementowego = 2ⁿ też dość łatwo, ale jest to dowód indukcyjny to co w końcu masz udowodnić ?

Basia: (4) wybieram k elementów spośród n pierwszy na n sposobów drugi na n−1 sposobów .................................. k−ty na n − (k−1) = n−k+1 sposobów czyli mam n*(n−1)(n−2)*....*(n−k+1) sposobów ale tak licząc uwzględniam kolejność czyli liczę na przykład dla k=3: (a,b,c) i (a,c,b) i (b,a,c) i (b,c,a) i (c,a,b) i (c,b,a) a przecież mowa o zbiorach czyli powinnam {a,b,c} liczyć tylko raz no to muszę poprzedni wynik podzielić przez k! i mam

n*(n−1)*.....*(n−k+1)
k!

	n k
to, że on jest równy		już łatwo pokazać

n k		n!
	=
		k!(n−k)!

i skracam n! z (n−k)!

	(n−k+1)(n−k+2)*....*n
=
	k!

i koniec

Trututu: Wcześniejszy post napisałam zanim odpisałaś, przepraszam za zamieszanie. Numer 4 mamy udowodnione, numer 2 też, numer 3 chyba też, bo to są takie same obliczenia jak 2 tak? Coś takiego mam w notatkach. Chyba chodzi o numer 1, że n nad k nie równa się 2ⁿ, chociaż mam zapisane, że to się równa 2ⁿ. Ale może właśnie mam wykazać, że to się temu nie równa. No ale jeśli to wychodzi z założenia to co ona tam rozpisywała? Może narysuję taki schemat jaki był na tablicy, może będziesz wiedziała o co chodzi? Jeśli oczywiście Ci się chce, bo już tyle namieszałam, że szkoda gadać

Trututu: Ok dobra dzięki, już nie będę mieszać, napiszę ten 4. Dziękuję bardzo i podziwiam za cierpliwość do takich głąbów...

Basia: (3) dowodzi się indukcyjnie narysuj może się połąpię

Trututu: Ok dzięki za chęci, schemat jest pod tym linkiem http://zapodaj.net/images/3513a6e2e9b30.jpg niestety tylko tyle.

Trututu: A jeszcze, że A={1,2,...,n}

Basia: to jest (4); tylko inny sposób dowodu na ile mogę się domyślić to jest tak: biorę a₁,a₂,....,a_k (czyli k) utworzyłam pierwszy podzbiór zostały mi a_k+1,a_k+2....,a_n (czyli n−k) no i mogę sobie teraz przesuwać a₂,a₃,...,a_k,a_k+1 drugi podzbiór a₃,a₄,.....,a_k,a_k+1,a_k+2 trzeci podzbiór itd. aż do a_n−k+1, a_n−k+2,....,a_n−k+k = a_n n−k+1 podzbiór a_n−k+2,....,a_n, a₁ n−k+2 podzbiór ............................................. a_n, a₁,.....,a_k−1 n podzbiór tak widzę ten rysunek i nic więcej nie wymyślę bo nie wiem jaka to metoda a to co widzę nie jest dobre gdybym z {a,b,c,d} budowała tą metodą podzbiory dwuelementowe to miałabym ab bc cd da a gdzie ac i bd ? pewnie czegoś nie rozumiem, albo po prostu coś było jeszcze dodatkowo dopowiedziane

Trututu: Dziękuję bardzo, i tak mi to rozjaśniłaś, wcześniej nie wiedziałam o co chodzi i co z czego się bierze, teraz chociaż coś ogarniam. Naprawdę, gdyby nauczyciele byli tacy jak Ty, nauka byłaby prostsza. Dziękuję.