Podziały i surjekcje

$ \def\RR{\mathbb{R}} \def\NN{\mathbb{N}} \def\CC{\mathbb{C}} \def\QQ{\mathbb{Q}} \def\ZZ{\mathbb{Z}} \def\dint{\mathop{\int\!\!\int}} \def\tint{\mathop{\int\!\!\int\!\!\int}} \def\rot{\hbox{rot\hskip2truept }} \def\div{\hbox{div\hskip2truept }} \def\grad{\hbox{grad\hskip2truept }} \def\zad#1{\noindent {\bf #1. }} \def\zadp#1{\mbox{\hspace{1em} {\bf #1) }}} \def\zadpa{\zadp{a} } \def\zadpb{\zadp{b} } \def\zadpc{\zadp{c} } \def\zadpd{\zadp{d} } \def\stylm{\displaystyle } $

Podziały i surjekcje (kolokwium 3)
spisał K.O. na podstawie sprawdzanych rozwiązań

Zadanie 1. Na ile sposobów możemy podzielić 12 osób na 4 zespoły 3-osobowe?

przed rozwiązaniami
$\ \ \bullet\ \ $ Osoby mają numery (np. w dzienniku) $1,2,\ldots,12$, zatem
wystarczy zliczać podziały zbioru $[12]=\{1,2,\ldots,12\}$ na 4 podzbiory 3-elementowe.
Uwaga: Podziałem zbioru $X$ nazywamy zbiór podzbiorów zbioru $X$ taki, że:
(i)    podzbiory te są niepuste,
(ii)    podzbiory te są parami rozłączne,
(iii)    suma ich wszystkich jest równa $X$.
Innymi słowy:
podziałem zbioru $X$ nazywamy zbiór klas abstrakcji pewnej relacji równoważności określonej na $X$.
Tu, w tm zadaniu, relacja jest następująca:
$a \sim b \iff a,b$ są w tym samym zespole.

$\ \ \bullet\ \ $ Przykłady DWÓCH 'dobrych' podziałów zbioru $[12]=\{1,2,\ldots,12\}$:
$\ \ \ \mathcal{P}=\{ \{1,2,3\},\; \{4,5,6\},\;\{7,8,9\},\;\{10,11,12\} \}$,
$\ \ \ \mathcal{Q'}=\{ \{1,3,5\},\; \{2,4,6\},\;\{7,8,9\},\;\{10,11,12\} \}$,
$\ \ \ \mathcal{Q''}=\{ \{2,4,6\},\; \{1,3,5\},\;\{7,8,9\},\;\{10,11,12\} \}$,
$\ \ \ \mathcal{Q'''}=\{ \{1,5,3\},\; \{2,4,6\},\;\{7,8,9\},\;\{10,11,12\} \}$;
dwóch, bowiem $\mathcal{Q'}=\mathcal{Q''}=\mathcal{Q'''}$ jest TYM SAMYM podziałem.

Rozwiązanie, sposób (I)
Dla $n\ge 1$ niech $a_n$ oznacza liczbę podziałów zbioru $\{1,2,3,\ldots,3n-2,3n-1,3n\}$ na $n$ zespołów 3-elementowych.
Oczywiście $a_1=1$.
Zachodzi $\ \ \ (*) \ \ \ a_n={3n-1\choose 2}\cdot a_{n-1},\ $ dla $\ n\ge 2$.
Bowiem liczba 1 (osoba o numerze 1) ma mieć w zespole jeszcze dwie osoby, które można dookoptować na ${ 3n-1\choose 2}$ sposoby.
Pozostałe $3n-3$ osoby można podzielić na $n-1$ zespołów 3-elementowych na $a_{n-1}$ sposobów; co kończy dowód wzoru (*)
Dalej wystarczy kolejno stosować (*):
$a_4={11\choose 2}\cdot a_3= {11\choose 2}\cdot {8\choose 2}\cdot a_2= {11\choose 2}\cdot {8\choose 2}\cdot {5\choose 2} \cdot a_1= {11\choose 2}\cdot {8\choose 2}\cdot {5\choose 1}\cdot 1.$
Zatem
Odp.: $\frac{11\cdot 10}{2!}\cdot \frac{8\cdot 7}{2!}\cdot \frac{5\cdot 4}{2!} \cdot 1=...=15400.$

Rozwiązanie, sposób (II)
Pierwszy zespół można wybrać na ${12\choose 3}$ sposoby,
drugi zespół można wybrać z pozostałych 9 osób na ${9\choose 3}$ sposoby,
trzeci zespół można wybrać z pozostałych 6 osób na ${6\choose 3}$ sposoby,
ostatni zespół można wybrać z pozostałych 3 osób na ${3\choose 3}=1$ sposób.
Iloczyn ${12\choose 3}\cdot{9\choose 3}\cdot{6\choose 3}\cdot{3\choose 3}$ nie jest szukaną liczbą,
bowiem w tym zliczaniu nie powinniśmy uwzględniać numerów zespołów.
(Na przykład oddzielnie liczymy:
$\ \ \langle \{1,3,5\},\; \{2,4,6\},\;\{7,8,9\},\;\{10,11,12\} \rangle$ i
$\ \ \langle \{2,4,6\},\; \{1,3,5\},\;\{7,8,9\},\;\{10,11,12\} \rangle$,
choć to daje jeden, ten sam sposób podziału; por. def. podziału.)
Dlatego odpowiedź otrzymamy dzieląc ów iloczyn przez wszystkie możliwe sposoby numeracji zaspołów
czyli
Odp.: ${ {12\choose 3}\cdot{9\choose 3}\cdot{6\choose 3}\cdot{3\choose 3} \over 4!}=...=15400.$

Rozwiązanie, sposób (III)
Zapis liczb naturalnych $\le 12$ w pewnej kolejności (czyli pewna permutacja zbioru [12])
po wstawieniu 'wąsów' po co trzeciej liczbie (nawiasy $\},\{$ oraz dodatkowe na końcach),
tworzy zapis pewnego podziału zbioru [12] na 4 podzbiory 3-elementowe.
$\{ \{{}_{-}, {}_{-}, {}_{-}\}, \{{}_{-}, {}_{-}, {}_{-}\}, \{{}_{-}, {}_{-}, {}_{-}\}, \{{}_{-}, {}_{-}, {}_{-}\} \}$
TEN SAM PODZIAŁ dostaniemy:
po dowolnym spermutowaniu trzech liczb w każdej z tych 4 grup,
po dowolnym spermutowaniu całych tych 4 grup.
Zatem
Odp.: $\frac{12!}{(3!)^4\cdot 4!}=...=15400.$

przed rozwiązaniami
$\ \ \bullet\ \ $ Wszystkich funkcji $\ f:X \to Y\ $ jest $\ |Y|^{|X|}$.
$\ \ \bullet\ \ $ Surjekcja $f:X \to Y$, to funkcja o obrazie $Y$; mówimy, że $f:X \to Y$ jest surjekcją, gdy $f[X]=Y$.

Rozwiązanie, sposób (I)
Skorzystamy z zasady włączeń i wyłączeń przy zliczaniu funkcji $f:\{1,2,3,4\}\to\{1,2,3\}$, które nie są surjekcjami.
Dla $k\in\{1,2,3\}$ niech $A_k=\{f:\{1,2,3,4\}\to\{1,2,3\}: k\notin f[\{1,2,3,4\}]\}$.
Mamy: $f:\{1,2,3,4\}\to\{1,2,3\}$ nie jest surjekcją wtedy i tylko wtedy, gdy $f\in A_1\cup A_2\cup A_3$.
Ponadto: $|A_k|=2^4,\ $ $|A_i\cap A_j|=1\ $ dla $\ i,j,k\in\{1,2,3\}, \;i\neq j\ \ $ oraz $\ \ A_1\cap A_2\cap A_3=\emptyset.$
Zatem $|A_1\cup A_2\cup A_3|= |A_1|+|A_2|+|A_3|-|A_1\cap A_2|-|A_1\cap A_3|-|A_2\cap A_3|+|A_1\cap A_2\cap A_3|=3\cdot2^4-3\cdot 1+0=45.$
Stąd
Odp.: |surjekcje z $\{1,2,3,4\}$ na $\{1,2,3\}$| = $3^4-45=36.$

Rozwiązanie, sposób (II)
Funkcja $f:\{1,2,3,4\}\to\{1,2,3\}$, która nie jest surjekcją jest:
surjekcją na dwuelementowy zbiór $B_k=\{1,2,3\}\setminus\{k\}$, dla pewnego $k\in\{1,2,3\}$
ALBO
surjekcją na jednoelementowy zbiór $C_j=\{j\}$ dla pewnego $j\in\{1,2,3\}$.
Ponieważ surjekcji na $B_k$ jest $(2^4-2)$ (odejmujemy dwie funkcje stałe)
oraz jest jedna surjekcja na $C_j$ (f. stała),
więc $\ \ |\{f:\{1,2,3,4\}\to\{1,2,3\}: f\mbox{ nie jest surjekcją}\}|= {3\choose 2}\cdot(2^4-2)+{3\choose 1}\cdot1 = 3\cdot 14+3=45$.
Stąd
Odp.: |surjekcje z $\{1,2,3,4\}$ na $\{1,2,3\}$| = $3^4-45=36.$

Rozwiązanie, sposób (III)
Niech $f:\{1,2,3,4\}\to\{1,2,3\}$ będzie surjekcją.
Zbiór przeciwobrazów punktów, czyli $\ \{ f^{-1}[\{1\}], f^{-1}[\{2\}], f^{-1}[\{3\}] \}\ $, jest podziałem (partycją) zbioru $\{1,2,3,4\}$,
w której jeden element podziału jest 2-elementowy, a pozostałe są 1-elementowe.
Liczba RÓŻNYCH podziałów zbioru $\{1,2,3,4\}$, w których jeden element podziału jest 2-elementowy, a pozostałe są 1-elementowe jest równa ${4\choose 2}$
(bowiem wybierając podzbiór 2-elementowy pozostałe są zdeterminowane).

Dalej zauważmy, że
surjekcje $f,g:\{1,2,3,4\}\to\{1,2,3\}$ dają ten sam podział zbioru $\{1,2,3,4\}$ wtedy i tylko wtedy,
gdy istnieje permutacja $h:\{1,2,3\}\to\{1,2,3\}$ taka, że $g=h\circ f$.
Stąd
Odp.: |surjekcje z $\{1,2,3,4\}$ na $\{1,2,3\}$| = ${4\choose 2}\cdot 3!=36.$

Zadanie 1 a) Na ile sposobów możemy podzielić $5n$ osób na $n$ zespołów 5-osobowych?

Zadanie 1 b) Na ile sposobów możemy podzielić 9 osób na 3 zespoły 2-osobowe i 3 zespoły 1-osobowe?

Zadanie 1 c) Na ile sposobów możemy podzielić 20 osób na 4 zespoły 2-osobowe i 4 zespoły 3-osobowe?