Kombinatoryka Marny uczeń: Na półce stoi 12 książek. Na ile sposobów można wybrać 5 książek z półki, tak aby nie zabierać żadnych dwóch stojących obok siebie?

	12 5		12 6		13 6
Mam pomysł by zrobić to w ten sposób:		+		=

Ale szczerze kompletnie nie wiem czy dobrze to rozumiem, stąd prosiłbym o pomoc (ewentualnie wytłumaczenie jeżeli ten to rozumowania jest poprawny)

Marny uczeń: pomyłka − miało być:

7 5		7 6		8 6
	+		=

Jerzy:

12 5
	− 11

Od wzystkich kombinacji odejmujemy 11 par książęk stojących obok siebie

Marny uczeń: Bardzo dziękuję! Jeśli mógłbym spytać, skąd wzięło się to 11? Niezbyt rozumiem dlaczego jest ich akurat tyle.

Jerzy:

	12 5		11 2
Przepraszam, to jest źle. Powinno być:		−

Musimy odjąć przypadki, gdzie wyciągamy dwie pary spośród 11. Mamy 11 par książek stojących obok siebie : (1,2) (2,3) (3,4) ...... (11,12)

Jerzy:

	11 2
Dalej źle. Musimy odjąć przypadki,gdy wylosowano dwie pary		oraz wylosowano tylko jedną

	11 1
parę

wredulus_pospolitus: Rysunek podaje PRZYKŁADOWE rozłożenie dla każdej z możliwości (oczywiście x to te wybierane przez nas książki) xooo Możliwość 1:

	4 0
wszystkie wybrane mają jedną odstępu od siebie:		*4

Możliwość 2:

	4 1
dokładnie pomiędzy dwoma są dwie odstępu (pozostałe − pojedyncze odstępy):		*3

Możliwość 3:

	4 1
dokładnie pomiędzy dwoma są trzy odstępu (pozostałe − pojedyncze odstępy):		*2

Możliwość 4:

	4 1
dokładnie pomiędzy dwoma są cztery odstępu (pozostałe − pojedyncze odstępy):		*2

Możliwość 5:

	4 2
dokładnie pomiędzy dwoma PARAMI są dwie odstępu (pozostałe − pojedyncze odstępy):		*2

Możliwość 6:

	4 3
dokładnie pomiędzy trzema PARAMI są dwie odstępu (pozostałe − pojedyncze odstępy):		*1

Możliwość 7: dokładnie pomiędzy dwoma są dwie odstępu, a pomiędzy dwoma trzy odstępu (pozostałe − pojedyncze

	4 1		3 1
odstępy):		*		*1

I dodajemy: 4 + 4*(3+2+1) + 4*3 + 4 + 4*3 = 56 możliwości Dodatkowo zauważ, że:

4 a
	oznacza ile będzie 'odstępów innych niż pojedynczy' pomiędzy książkami (uwaga na

możliwość 7)

wredulus_pospolitus: No i chuj .... rysunku nie dodaje

wredulus_pospolitus:

Marny uczeń: W sensie pojawiło się dużo nieco sprzecznych odpowiedzi, choć za wszystkie jestem wdzięczny.

	12 5
Czy dobrze rozumiem, że mam brać:		a potem odejmować od tego wszystkie możliwości z

odstępami między tymi książkami? Niezbyt rozumiem też dlaczego Jerzy i wredulus_pospolitus operują na innych liczbach w dwumianie Newtona? (odpowiednio 11 i 4)?

wredulus_pospolitus: Marny uczeń −−− patrz co ja podałem ... ja nie odejmuję 'niesprzyjających' możliwości od ogólnej liczby Ja liczę wprost ile jest możliwości dla każdej z możliwości którą wcześniej opisuję

Marny uczeń: Ja rozumiem i bardzo wdzięczny jestem za ten sposób, ale jeżeli liczba książek mocno urośnie, to nie będzie to realne zrobienie tym sposobem. Stąd moje pytanie.

wredulus_pospolitus: Jeżeli 'liczba książek mocno urośnie' to ani jeden ani drugi sposób nie będzie zbyt dobry

Marny uczeń: Rozumiem, czyli nie istnieje żaden uniwersalny wzór na takie sytuacje? W każdym razie bardzo dziękuję za pomoc i rozrysowanie wszystkie. Biorę się do analizy tego sposobu.

wredulus_pospolitus:

	12 5
Jeżeli chciałbyś odejmować od wszystkich przypadków czyli od		to musisz odjąć sytuacje:

1) dokładnie jedna para książek sąsiaduje ze sobą (czyli np.: xx o x o x o x o o o o) 2) dokładnie dwie pary książek sąsiaduje ze sobą (czyli np.: xx o o xx o x o o o o) 3) dokładnie trójka książek sąsiaduje ze sobą (czyli np.: xxx o o x o x o o o o) 4) dokładnie trójka i osobno para książek sąsiaduje ze sobą (czyli np.: xxx o o o xx o o o o) 5) dokładnie czwórka książek sąsiaduje ze sobą (czyli np.: xxxx o o o x o o o o) 6) wszystkie sąsiadują ze sobą (czyli np.: o o o xxxxx o o o o)

Pytający: Można uogólnić. Prostsza wersja zadania: n = 5 książek na półce, wybierasz k = 2 tak, żeby nie zabierać żadnych dwóch stojących obok siebie. Możesz na to spojrzeć w ten sposób: x₀ + 1 + (x₁ + 1) + 1 + x₂ = 5, x_i ≥ 0 gdzie: x₀ // liczba książek na lewo od pierwszej wybranej książki 1 // pierwsza wybrana książka (x₁ + 1) // liczba książek pomiędzy 1−szą a 2−gą wybraną książką 1 // druga wybrana książka x₂ // liczba książek na prawo od ostatniej wybranej książki 5 // liczba wszystkich książek Po uproszczeniu otrzymujesz: x₀ + x₁ + x₂ = 5 − 2 − (2 − 1) = 5 − 2 * 2 + 1 = 2, x_i ≥ 0

	(3 − 1) + 2 3 − 1
a to równanie ma		= 6 rozwiązań całkowitych nieujemnych.

Uogólniając dla n książek i k wybranych książek otrzymasz równanie: ∑_i=0^k (x_i) = n − 2k + 1, x_i ≥ 0

	(k + 1 − 1) + (n − 2k + 1) k + 1 − 1		n − k + 1 k
które ma		=		rozwiązań całkowitych

	n + 1
nieujemnych (oczywiście tylko dla k ≤ n − k + 1 ⇒ k ≤		).
	2

	(6 − 1) + (12 − 5 − 4) 6 − 1		12 − 5 + 1 5
W przypadku Twojego zadania		=		= 56.

Marny uczeń: Rozumiem, jeszcze raz bardzo dziękuję za odpowiedzi!

Marny uczeń: @Pytający

	n−k+1 k+1
Zapytam jeszcze, czy przypadkiem w tym równaniu ogólnym nie powinno być		ponieważ

wtedy zgadza się z odpowiedzą, którą otrzymałem do zadania?

Pytający: Nie, dobrze napisałem.

	12 − 5 + 1 5 + 1		8 6
Poza tym przecież		=		= 28 jest błędną odpowiedzią, wredulus

nawet rozbił Ci na przypadki wszystkie 56 możliwości.

Marny uczeń : Rozumiem, w takim razie jeszcze raz dziękuję