podzbiory karol: Na ile sposobów można zbiór {1,2,...,n}, gdzie n≥3, podzielić na trzy niepuste podzbiory? Proszę o pomoc.

Kacper: Studia?

karol: nie, klasa maturalna

PW: Najpierw rozwiążmy zadanie przy założeniu, że zbiory mają określony porządek (to znaczy odróżniamy sytuację (A₁, A₂, A₃) od np. (A₃, A₁, A₂), mimo że podzbiory A₁, A₂ i A₃ są identyczne). Mamy n rozróżnialnych elementów, każdemu z nich trzeba przyporządkować jeden z numerów {1, 2, 3} (numer podzbioru). Rozwiązaniem problemu byłaby liczba funkcji (1) f: {1,2,3,...,n} → {1,2,3}, to znaczy liczba 3ⁿ, gdyby nie fakt, że w ten sposób liczymy również takie przyporządkowania, w których osiągnięta jest tylko jedna wartość spośród 1, 2, 3 lub tylko dwie z nich. Byłby to podział na podzbiory, z których dwa lub jeden jest pusty. Wobec tego rozwiązaniem jest liczba k = 3ⁿ − 3·2ⁿ + 3 (od wszystkich wariacji 3−elementowych z powtórzeniami odjęliśmy wariacje 2−elementowe; w ten sposób otrzymaliśmy funkcje, które przyjmują wszystkie trzy wartości, opisujące podział na 3 niepuste podzbiory). Liczba +3 bierze sie stąd, że licząc 3·2ⁿ odjęliśmy m.in. 6 funkcji jednowartościowych, a powinniśmy odjąć tylko 3 takie funkcje. Liczba k to liczba podziałów z uwzględnieniem kolejności, wobec tego liczba podziałów na trzy niepuste podzbiory (bez uwzględniania kolejności) jest równa

	k		3n − 3·2n + 3		1
		=		=		(3n−1 − 2n + 1).
	3!		6		2

Rozwiązanie to jest rodzajem zabawy umysłowej, zdaję sobie sprawę z możliwości łatwiejszego wyliczenia.

Mila: Załóżmy, że mamy n różnych kul rozłożyć do 3 różnych szuflad A,B,C. 3ⁿ− liczba wszystkich możliwości, w tym: jedna pusta, wtedy :

3 1
	*(2n−2) kule rozłożone do dwóch szuflad, żadna nie jest pusta

Dwie puste, kule trafiają do jednej szuflady

3 2
	*1=3

Zatem: 3ⁿ−[3*(2ⁿ−2)+3] − liczba wszystkich możliwych umieszczeń n kul w trzech szufladach i żadna nie jest pusta, z tym, że nas nie ineresyją sytuacje: A,B,C oraz B,A,C, itp bo, to są te same podzbiory. Stąd Wynik:

3n−[3*(2n−2)+3]
3!

mozesz to doprowadzić do prostszej postaci.

PW: Karol dostał gotowe rozwiązanie na dwa sposoby, więc jako uczeń klasy o wysokim poziomie pomyśli nad twórczym rozwinięciem zadania. Już wie, że w gruncie rzeczy idzie o ustalenie liczby funkcji na f: {1,2,3,...,n} → {1,2,3}. Jak wygląda wzór na liczbę funkcji "na" zbiór {1,2,3,4}?

karol: dziękuję za pomoc nie jestem pewien, jak będzie wyglądał wzór na zbiór {1,2,3,4}, ale spróbuję więc 4ⁿ − liczba wszystkich możliwości, od tego trzeba odjąć: 4 − trzy puste szuflady, kule trafiają do jednej szuflady; 6*(2ⁿ−2) − kule rozłożone do dwóch szuflad (żadna nie jest pusta), dwie szuflady pozostają puste 4*[3ⁿ−3*(2ⁿ−2)−3] − kule rozłożone do trzech szuflad (żadna nie jest pusta), jedna szuflada pozostaje pusta otrzymaną różnicę należy podzielić przez 4!

Kacper: Ja pytałem, czy studia, bo na studiach taką sytuację przedstawiają liczby Stirlinga II rodzaju

Mila: PW, Kacper, czy to jest dobre rozwiązanie?

Mila: Wyniki zgadzają się z obliczonymi wg wzorów Stirlinga.

Kacper: Trochę ktoś przesadził z tymi zadaniami. To nie jest zadanie dla przeciętnego ucznia (taki ma zdać maturę).

cokolwiek: Bo to nie jest normalne zadanie tylko z olimpiady organizowanej przez agh.