kombinatoryka kombinatoryka: Przypuśćmy, że mamy n ustawionych szeregowo klatek, w których chcemy rozmieścić k jednakowych lwów tak, by żadne lwy nie sąsiadowały ze sobą. Niech g(n, k) będzie liczbę takiego rozmieszczenia zwierząt. Uzasadnij, że: (1) g(6,3) = 4 (2) g(2k, k) = k + 1 (3) g(n,k) = g(n−2, k−1) + g(n−1, k) dla k = 2, 3, 4... No więc o ile (1) idzie rozrysować i w ten sposób pokazać, że są dokładnie 4 rozmieszczenia, to już (2) i (3) nie jest takie proste. Jakieś sugestie, jak można by to sobie wizualizować?

jc: Każdy lew, z wyjątkiem ostatniego, zajmuje dwie klatki.

	n−k+1 k
Mamy więc g(n,k)=		.

	6 3		4 3
(1)		=		=4

	k+1 k
(2)		=k+1

	n−k k−1		n−k k		n−k+1 k
(3)		+		=		, jak w trójkącie Pascala

jc:

	4 3
Oj, tam miało być g(6,3)=

Tu akurat łatwiej było podać gotowy wynik, niż uzasadniać regułę rekurencyjną. Zwykle jest odwrotnie. Obrazek. n=6, k=3. Za pierwszym i drugim lwem jest przyklejona klatka. LK LK L K LK LK K L LK K LK L K LK LK LK

kombinatoryka: Rozumiem, już to widzę Dziękuję.