Zadanie kombinatoryczne

[kondzio34]

Niech \(\displaystyle{ n \ge 3.}\)
Na ile sposobów można podzielić zbiór \(\displaystyle{ \{1,2,..,n\}}\) na trzy niepuste i rozłączne podzbiory (przy czym kolejność zbiorów ogrywa rolę)?

Dokładniej więc pytamy, ile jest ciągów \(\displaystyle{ (X_1,X_2,X_3)}\), gdzie \(\displaystyle{ X_1,X_2,X_3}\) są takimi niepustymi i rozłącznymi zbiorami, że \(\displaystyle{ X_1\cup X_2\cup X_3=\{1,2,\dots,n\}.}\)

[strefa61]

Poszukaj 'współczynników multimianowych'. Zdaje się, że to było dokładnie to.

[matmatmm]

Załóżmy chwilowo, że podzbiór \(\displaystyle{ X_1}\) będzie miał \(\displaystyle{ k}\) elementów. Wtedy \(\displaystyle{ k\in\{1,\ldots, n-2\}}\) i podzbiór ten można wybrać na \(\displaystyle{ {n \choose k}}\) sposobów. Dalej podzbiór \(\displaystyle{ X_2}\) można wybrać na \(\displaystyle{ 2^{n-k}-2}\) sposobów, a ostatni podzbiór \(\displaystyle{ X_3}\) już tylko na \(\displaystyle{ 1}\) sposób.

[JHN]

Według mnie jest ich
\(\displaystyle{ 3^n-{3\choose2}\cdot2^n+{3\choose1}\cdot1^n}\)
bo kolejnym elementom zbioru przyporządkowuję indeks podzbioru, do którego ma należeć. Wobec niepustości podzbiorów, z reguły w/w mamy powyższe

Pozdrawiam

[Janusz Tracz]

Gdyby chwilowo zaniedbać kolejność to dostaniemy, że podziałów jest tyle ile

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Simple_identities

\(\displaystyle{ \left\{{n \atop 3}\right\}={\frac {{\frac {1}{1}}(3^{n-1}-2^{n-1})-{\frac {1}{2}}(3^{n-1}-1^{n-1})}{1!}}}\)

wzór jawny na liczb Stirlinga II rodzaju można wyznaczyć znajdując liczbę suriekcji oraz znajdując zależność pomiędzy podziałami a suriekcjami. Teraz jeśli mamy jakiś konkretny podział z to możemy zmieniać kolejność zbiorów na \(\displaystyle{ 3!}\) sposobów ponieważ na pewno element podziału są istotnie różne (a nawet pusto się kroją). Zatem uwzględniając kolejność mamy

\(\displaystyle{ \sharp \left\{ \left( X_1,X_2,X_3\right) : \text{ uporządkowane podziały }[n] \right\} = 3!\left\{{n \atop 3}\right\}.}\)

Przy czym w słowie podział kryje się już, że \(\displaystyle{ (\forall i=1,2,3)X_i \neq \varnothing}\) oraz \(\displaystyle{ X_1 \cup X_2 \cup X_3=[n]}\). Można też od razu doszukać się, że uporządkowane podziały jednoznacznie korespondują z suriekcjami \(\displaystyle{ \left[ \ [n]\ni n\mapsto i\in\left[ 3\right] \ \right] }\) na przykład w taki sposób, że element \(\displaystyle{ X_i}\) przechodzą zawsze na \(\displaystyle{ i}\). Zliczanie suriekcji i ich związek z liczbami Stirlinga II rodzaju można znaleźć na forum.