udowodnic algebraicznie lub kombinatorycznie MagdaS: Hej, tym razem chyba dałam radę ale proszę o sprawdzenie. mamy udowodnić, że m

	k n		m+1 n+1
∑		=

k=0 pomyślałam, że można by zrobić to indukcyjnie. Sprawdziłam dla założonego n i m, wyszło. Teraz sprawdzam, czy dla dowolnego n, i m+1, też to będzie zachodziło. m+1

	k n		m+2 n+1
∑		=

k m+1 m

	k n		k n		m+1 n
∑		= ∑		+

k k

	m+2 n+1		m+1 n+1		m+1 n
zatem		=		+

i to w sumie jest jedna z podstawowych zależności, którą udowodniłam. Po prostu krok po kroku wyprowadzając wzór. W efekcie końcowym było

m+2		m+1 n+1		m+1 n+1		m+1 n
	+		=		+
m−n+1

później po przekształceniu

	m+2		m+1 n+1		m+1 n
(		−1)		=
	m−n+1

n+1	m+1 n+1		m+1 n
		=
m−n+1

i w konsekwencji wychodzi

(m+1)!		m+1 n
	=
(m−n+1)!n!

można tak prostą drogą się do tego zabrać?

MagdaS: przepraszam, wszędzie powinno być k=0 w indeksach

MagdaS:

	m+2		m+1 n+1		m+2		m+1 n+1
zamiast		+		powinno być		*		. Nie ma na tym forum
	m−n+1				m−n+1

możliwości edycji prawda?

jc: Kombinatoryczne uzasadnienie jest oczywiste. Powinnaś napisać mniej więcej tak: Mamy pokazać równość

n n		n+1 n		m n		m+1 n+1
	+		+ ... +		=		, m≥n.

Indukcja względem m.

	n n		n+1 n+1
1. Dla m=n mamy		=1=		.

2. Załóżmy, że

n n		n+1 n		m n		m+1 n+1
	+		+ ... +		=		, m≥n.

Wtedy

n n

n+1 n

m n

m+1 n

m+1 n+1

m+1 n

m+2 n+1

+

+ ... +

+

=

+

=

−−− Wykorzystaliśmy tu dobrze znaną równość (z której nie musisz się tłumaczyć)

n k		n k+1		n+1 n+1
	+		=		.

Znów dowód kombinatoryczny jest banalny, dowód algebraiczny jest trudniejszy i zależy w pewnym stopniu od przyjętej definicji symbolu Newtona. Poza tym równość tę można uznać za jedną z definicji symbolu Newtona (należy dodać jeszcze wartości dla k=0 i k=n).

MagdaS: dla m+1 osób losujemy n+1 nagród. Ale (prawa strona) możemy to zrobić również w sposób taki, że wybieramy liczbę k kobiet w zbiorze osób i dodajemy po kolei na ile sposobów może to być spełnione, jeżeli kobiet w zbiorze będzie 0,1,2...m. Coś takiego jest dowodem kombinatorycznym? Przepraszam, w skrypcie mam od razu zadania bez wytłumaczenia, na wykładzie było trochę kiepsko, ogarniam to sobie na własną rękę i szczerze jak to pierwszy raz zobaczyłam to czarna magia.

MagdaS: Lewa strona* lol

MagdaS: i jeszcze wymaganie, że w zbiorze osób ma być przynajmniej jedna kobieta i jeden mężczyzna

jc: Nie bardzo zrozumiałem. Zaproponowałbym coś takiego. Z liczb 1,2,3,..,m+1 wybieramy n+1 liczb.

	m+1 n+1
Mamy oczywiście		możliwości,

które możemy podzielić wg największej liczby w wybranym podzbiorze. Może to być liczba n+1, n+2, n+3, ..., m+1.

	n k
Jeśli to jest liczba k+1, to pozostałe n liczb możemy wybrać na		sposobów.

Porównanie daje dowodzoną równość. Przykład. Ze zbioru {1,2,3,4,5,6,7} wybieramy 4 liczby. Największa = 4, jedna możliwość: {1,2,3}u{4} Największa = 5, 4 możliwości: {1,2,3}U{5}, {1,2,4}U{5}, {1,3,4}U{5}, {2,3,4}U{5} Największa = 6, 10 możliwości: {1,2,3}U{6}, ..., {3,4,5}U{6} Największa = 7, 20 możliwości: {1,2,3}U{7}, ..., {4,5,6}U{7} Razem 1+ 4 + 10 + 20 = 35 możliwości.

MagdaS: aha, w ten sposób, no nie jest to dla mnie takie oczywiste . Ale biorę się do roboty dalej, dzięki za wszystko.

jc: n=2, m=4

2 2		3 2		4 2		5 3
	+		+		=

1+3+6=10 Teraz na tym przykładzie spróbuj wyjaśnić, o co chodzi z tymi prezentami z wykładu.

MagdaS: nie nie, to była moja inwencja twórcza. W sumie teraz jak zaczęłam to sobie na wolno rozpisywać to widzę, że nie ma większego sensu. Też chodziło o to, że nie chciałam zwyczajnie poprosić o gotowe rozwiązanie tylko się wysilić+poprosić. Chodziło mi o zbiór m+1 osób (kbt i mżczzn) i n+1 prezentów do obdarowania ich.

	m+1 n+1
Wtedy liczba sposobów jakimi można to zrobić wynosi		.

	n k
Ale możemy też sobie to podzielić na podzbiory		, gdzie k to liczba kobiet które

otrzymały prezent. Ale po rozpisaniu tego na spokojnie w zeszycie widzę, że nie ma to większego sensu.