kombinatoryka maciek: Witam. Prosze o pomoc w zrozumieniu czegoś. Problem jest z kombinatoryką. Np takie zadanie: Ile jest calkowitoliczbowych rozwiazan rownania x₁ + x₂ + x₃ + x₄ = 32 jesli x₁,x₂,x₃,x₄ > 0 , wiem, że istnieje taki wzor na kombinacje z powtorzeniami. i teraz tutaj n=4, ale nie wiem jak z k, bo tam sie bralo k po znaku =. ale tu jest ten przypadek ze wszystkie maja byc wieksze od 0. a w zalozeniu wzoru na kombinacje z powtorzeniami (n+k−1) po (k) x_i >=0 1<=i<=n. takze jak podejsc do tego przypadku?

MQ: To jest równoważne zagadnieniu: Masz 32 kulki i 4 pudełka. 4 kulki umieszczasz w każdym pudełku, bo w każdym musi być co najmniej jedna (musisz mieć liczby >0). Zostają ci 32−4=28 kulek. Na ile sposobów można je powkładać do tych 4 pudełek.

Patronus: Wyobraź sobie że x₁ ... do x₄ to oddzielne szuflady do których chowamy kulki. 1 oznaczam końce szuflad, 0 to kulki które tam wkładamy: 0000 ... 1 000...1 0000.. 1 0000... czyli mamy ciag 35 cyfr (3 jedynek i 32 zer) i liczymy ile jest takich ciągów:

35 3		35*34*33
	=		= 35*11*17 = 6545
		2*3

Patronus: a widzisz MQ oczywiście zrobił lepiej bo ja nie uwzględniłem tego że w każdej szufladzie musi być przynajmniej 1 kulka

maciek: aha dziekuje na kulkach to przyjemniej brzmi.... czyli np jakby miala byc tylko x₁ >0 to wkladam kulke do x₁ a reszte robie normalnie?

Patronus: to w takim razie u mnie jest:

31 3		31*30*29
	=		= 31*5*29 = 4495
		2*3

maciek: zgadza sie

maciek: a cos takeigo ze x₁+x₂+x₃+x₄ = 18 warunek: 7>= x_i>0 i=1...4

PW: (1+1+1+...+1) = 32 Sumę po lewej stronie można zapisać w postaci czterech składników dodatnich zamieniając 3 spośród 31 znaków "+" znakami ")+(". Na przykład (1+1+1+1+1)+(1+1+1+1+1+1+1+1+1+1+1)+(1+1+1+1)+(1+1+1+1+1+1+1+1+1+1+1+1) = 32 oznacza rozwiązanie 5+11+4+12 = 32. Stąd wzór na liczbę rozwiązań

	31 3

− na tyle sposobów można dokonać wyboru 3 spośród 31 znaków "+". Ogólnie:

	n−1 k
		,

jeśli n oznacza sumę, a k − liczbę dodatnich składników.

PW:

	n−1 k−1
Chochlik: