zadanko z kombinatoryki Krzysiek95: Uwaga Trudne zadanie kombinatoryczne! Treść : Na ile sposobów można rozdzielić 8 zeszytów na 4 półki. a)zeszyty i półki nierozróżnialne b)zeszyty rozróżnialne

Basia: ad.a tyle ile razy uda się przedstawić 8 w postaci sumy czterech składników 8=8+0+0+0 8=7+1+0+0 8=6+2+0+0 8=6+1+1+0 8=5+3+0+0 8=5+2+1+0 8=5+1+1+1 8=4+4+0+0 8=4+3+1+0 8=4+2+1+1 i tyle (pozostałe już będą powtórzeniami, bo kolejność nie ma znaczenia)

Basia: ad.b 8=8+0+0+0 jedna możliwość

	8 1
8=7+1+0+0		=7

	8 2
8=6+2+0+0

	8 1		7 1
8=6+1+1+0		*

i tak dalej

Krzysiek95: A czy czasem w a) nie będzie jeszcze dodatkowo: 8=4+2+2+0 8=3+2+2+1 8=3+3+1+1 8=3+3+2+0 8=2+2+2+2 oraz czy mogłabyś rozszerzyć o co chodzi w podpunkcie b? Kombinacja 8 nad 1 to chyba wychodzi 8?

Mila: Podział liczby na składniki . a) Podział liczby 8 na składniki: P(8,1)=1− wszystkie zeszyty na jednej półce [8=8]

	8
P(8,2)=[		]=4
	2

[ 8=1+7, 8=2+6, 8=3+5, 8=4+4] P(8,3)=P(7,2)+P(8−3,3)=3+P(5,3)=3+P(4,2)+P(2,3)=3+2+0=5 P(8,4)=P(7,3)+P(4,4)=1+P(6,2)+P(4,3)=1+3+1=5 Razem: 1+4+5+5=15

Pytający: A w b) pewnie należy jeszcze uwzględnić kolejność zeszytów na poszczególnych półkach i wyjdzie:

	7 1	8!		7 2	8!		7 3	8!
8!+			+			+
		2!			3!			4!

abcdefgh // oznaczmy tak zeszyty Możemy je przemieszać na 8! sposobów (mamy 8! różnych ciągów) i na tyle sposobów możemy położyć zeszyty na 1 półce.

	7 1
Dla każdego takiego ciągu możemy podzielić go na dwie niepuste części (półki) na

sposobów (rysujesz kreskę gdzieś pomiędzy literami). Jednak półki są nierozróżnialne, więc dzielimy przez 2!, bo każde rozmieszczenie wystąpi w 2! różnych ciągach. Przykładowo: (ab)|(cdefgh) (cdefgh)|(ab) Analogicznie dla rozmieszczenia na 3 i 4 półkach.

Basia: tak oczywiście, pospieszyłam się, trzeba to uwzględnić mam podział 8+0+0+0 półki są nierozróżnialne, więc łapię te zeszyty wszystkie razem i rzucam na byle którą półkę − jedna możliwość

	8 1
podział 7+1+0+0 wybieram jeden zeszyt z ośmiu czyli		=8

	8 2
podział 6+2+0+0 wybieram dwa z ośmiu

	8 2
podział 6+1+1+0 też wybieram dwa z ośmiu tyle, że je rozrzucam po dwóch półkach

	8 1		7 1
i to nie to samo co		*		bo to już rozróżnia półki

no i tak dalej

Mila: Myślę, że na półkach nie trzeba uwzględniać kolejności ustawień. Chyba można zastosować liczby Stirlinga II rodzaju, czy student to miał na wykładach?

Mila: Oczywiście witam miło Basię i Pytającego

Pytający: Może trzeba, może nie trzeba. Również witam serdecznie. Jak nie trzeba, to tak jak Basia pisze, czy też liczbami Stirlinga właśnie.

Basia: też nie wiem, te zadania z kombinatoryki są coraz częściej niedoprecyzowane zrozumiałam, że nie trzeba uwzględniać kolejności na półkach czyli w każdej z tych już wyliczonych sytuacji podział zbioru ośmioelementowego na niepuste podzbiory (odpowiednio 1,2,3, lub 4) witajcie

Mila: Pytający, jak wpisać do wolframa S₂(8,4) ?

Krzysiek95: Tak, miałem liczby Strirlinga II rodzaju. Liczenie jest dosyć proste i schematyczne, problem tkwi w tym, żeby ocenić kiedy powinienem ich użyć w zadaniu, są jakieś określone typy zadań pod te liczby Stirlinga?

Pytający: Milu: stirlings2(n,k) Krzysiek, jak masz n rozróżnialnych elementów (zbiór) i dzielisz go na k niepustych grup (niepustych rozłącznych podzbiorów), to takich podziałów jest właśnie {n,k} (że tak oznaczę liczbę Stirlinga 2 rodzaju).

Mila: 1) Kule rozróżnialne , szuflady ( komórki) nierozróżnialne −liczby Stirlinga II rodzaju− S₂(n,k) podział n różnych elementów na k niepustych podzbiorów Jeżeli niektóre szuflady mogą byc puste to sumujesz wszystkie podziały, W twoim zadaniu: S₂(8,1)+S₂(8,2)+S₂(8,3)+S₂(8,4) 2) kule nierozróżnialne (n) , szuflady rozróżnialne(k) − kombinacje z powtórzeniami

n+k−1 k−1

3) Kule nierozróżnialne (n) , szuflady nierozróżnialne (k) − P(n,k)− podział liczby n na k składników. Jeżeli niektóre szuflady mogą być puste to sumujesz wszystkie podziały.

Mila: Liczby Stirlinga II rodzaju w wolframie Tabelka http://pracownik.kul.pl/files/103633/public/Matematyka_dyskretna/Liczby_Stirlinga.pdf trójkąt liczbowy https://pl.wikipedia.org/wiki/Liczby_Stirlinga#Liczby_Stirlinga_II_rodzaju Wzór znasz? S₂(8,1)+S₂(8,2)+S₂(8,3)+S₂(8,4)= =1+127+966+1701=2795

Mila: Dziękuję bardzo Pytający

Krzysiek95: Tak, wzór znam, tylko policzyłem do tej pory jedynie S₂(8,4)=1701, wyszło tyle samo. Czyli jak pozostawię tylko ten człon to znaczy, że 8 nierozróżnialnych zeszytów umieszczam do k=4 niepustych półek i nie uwzględniam możliwości, że niektóre półki pozostaną puste. Licząc S₂(8,3) zakładam, że jedna półka pozostaje pusta i reszta (3półki będą zajęte)?

Mila: Zgadza się.

Krzysiek95: Mila bardzo dziękuję za tą nieocenioną pomoc, szczere słowa podziwu za szerokie spektrum matematycznej wiedzy, jeszcze raz dzięki!

Mila: Dobranoc