Dowód kombinatoryka Misanthrope: Wykorzystując metody kombinatoryczne uzasadnij równość: {n n−2}= (n+1 4) + 2*(n 4)

Jerzy: Popraw zapis.

xyz: N { n } { n−2 }

	n n−2
napisz bez spacji − o ten symbol ci chodzilo ?

Misanthrope: Chodziło o dowód, że n−2 podzbiorów z n jest równe sumie kombinacji 4 elementowej ze zbioru n+1 elementowego oraz podwojonej wartości kombinacji 4 elementowej ze zbioru n elementowego.

jc: Co to jest podzbiór z n? Co to jest kombinacja? Czym jest wartość kombinacji? Potrafiłbyś rzecz wyrazić zwykłym językiem?

Misanthrope: Liczba Stirlinga drugiego rodzaju {n n−2}

	n+1 4		n 4
{n n−2}=		+ 2*

jc: Dzielisz zbiór n elementowy na n−2 podzbiory. Jakie są możliwe typy podziałów? (1) n−4 podzbiory 1 elementowe plus 2 podzbiory 2 elementowe (2) n−3 podzbiory 1 elementowe plus pdzbiór 3 elemntowy

	n 4
(1) 3		możliwości

	n 3
(2)		możliwości

n+1 4		n 4		n 3
	=		+

n 4

n 3

n 4

n+1 4

n 4

n 4

n+1 4

3

+

= 3

+ [

−

] =2

+

Ostatni krok nie jest kombinatoryczny, więc trzeba szukać dalej.