kombi kamil: Podaj kombinatoryczną interpretację wzoru i uzasadnij jego prawdziwość:

n 0		n 1		n k		n n − 1		n n
	+		+ ... +		+ ... +		+		= 2n

czy tutaj trzeba wykorzystać indukcję matematyczną? n = 0, potem n = k i n = k + 1?

Janek191: Z wzoru dwumianowego Newtona mamy

	n 0		n 1		n k		n n −1		n n
2n = ( 1 + 1)n =		+		+ ... +		+ ... +		+

Nuti: Racja, ale pytanie było o interpretację kombinatoryczną. Chętnie ją podam. n nad k dla naturalnych n i k takich, że k jest mniejsze równe n jest liczbą k−elementowych podzbiorów zbioru n−elementowego. Czyli po lewej stronie mamy sumę, której składniki to:

n 0
	− liczba podzb. 0−elem. Tylko jeden (zbiór pusty)

n 1
	− liczba podzb. 1−elem. Jest ich tyle co elementów zbioru, czyli n

n 2
	− liczba podzb. 2−elem. Jest ich tyle ile par elementów zbioru n

...

n n−1
	− liczba podzb. n−1−elem. Jest ich n (oczywiste?)

n n
	− liczba podzb. n−elem. Jest tylko jeden taki podzbiór − cały zbiór.

Ich suma jest oczywiście totalną liczbą wszystkich możliwych podzbiorów zbioru n−elementowego. To była lewa strona. A prawa to 2ⁿ co, jak sam przed chwilą liczyłeś w innym zadaniu, jest liczbą wszystkich możliwych funkcji ze zbioru n−elementowego w zbiór dwuelementowy o elementach 0 i 1. Tym razem nie wykluczasz funkcji stałych, bo chcesz mieć WSZYSTKIE funkcje, a nie tylko surjekcje. I teraz nadchodzi grand finale: Twierdzę, że takich funkcji jak opisane przed chwilą jest dokładnie tyle samo co wszystkich możliwych podzbiorów zbioru n−elementowego. Dlaczego? Wystarczy pokazać bijekcję (tak!) ze zbioru wszystkich takich funkcji w zbiór wszystkich podzbiorów. Każda funkcja ze zbioru {1,2,3,...,n} w {0,1} jest ciągiem n zer i jedynek (na miejscu k w tym ciągu stoi zero albo jedynka, zależnie od tego ile jest równe f(k), a_k=f(k)). Każdej takiej funkcji, czyli ciągowi zer i jedynek, odpowiada dokładnie jeden podzbiór naszego zbioru n−elementowego. Ten zbiór opisujemy w następujący sposób: k należy do zbioru wtedy i tylko wtedy gdy a_k=1 Odwzorowanie takie jest w sposób ewidentny bijekcją czyli pokazaliśmy, że zbiór wszystkich podzbiorów zbioru n−elementowego (czyli zbiór o mocy wyrażonej przez lewą stronę równania do udowodnienia) jest równoliczny ze zbiorem wszystkich funkcji ze zbioru n−elementowego w zbiór dwuelementowy 0 i 1, którego moc jest 2ⁿ. To dowodzi równości. W sposób kombinatoryczny.

henrys: Hello U mnie na dyskretnej opowiadało się historyjki kombinatoryczne w ramach tego typu dowodów np. Na ile sposobów można wybrać grupę uczniów, wchodzących w skład reprezentacji szkoły z n−osobowej klasy?

	n 0
i tak:		−nikt z klasy nie wszedł w skład reprezentacji

	n 1
		− jedna osoba ( z klasy liczącej n osób) weszła w skład reprezentacji

	n 2
		− 2 osoby

.........

	n n
		−cała klasa weszła w skład reprezentacji szkoły

zatem ilość takich sposobów to

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

co jest równoważne z liczbą wszystkich podzbiorów zbioru n−elementowego = 2ⁿ (czyli z liczbą wszystkich możliwych grup utworzonych z n− osobowej klasy)

PW: Nuti ładnie nawiązał(a) do wczorajszych bojów kamila z suriekcją. Coraz bardziej podoba mi się to forum.