kombinatoryka karolina: Na ile sposobów można podzielić zbiór [n]={1,2,...,n} na dwa niepuste i rozłączne zbiory? nie mam pojęcia jak to zrobić ..

PW: Zbudować model matematyczny takiego podziału. Może to być następująca "konstrukcja myślowa": − Każdemu elementowi zbioru przyporzadkujemy jedną z liczb: 0 lub 1. Przyporządkowanie jedynki oznacza, że element trafił do zbioru A, zaś przyporządkowanie zera − że element trafił do zbioru B. Podziałów jest więc tyle ile funkcji f: {1, 2, 3, ..., n} → {0, 1}, przy czym należy odrzucić dwie funkcje (przyjmujące tylko jedną wartość). Przy takim rozumowaniu uwzględniamy kolejność zbiorów A i B, a ponieważ nie należy tak robić, uzyskany wynik trzeba podzielić przez 2.

Pytający: Inne podejście: te 2 podzbiory możemy rozróżnić np. ze względu na jakiś element, przykładowo jedynkę. Niech: A⊂[n], B⊂[n] // A, B to podzbiory [n] i: A≠∅, B≠∅ // są niepuste, A∩B=∅ // są rozłączne, A∪B=[n] // sumują się do [n], 1∊A // 1 należy do A Wtedy każdy z pozostałych (n−1) elementów należy do A lub do B (2 możliwości). Jednak zbiór B nie może być pusty, więc trzeba odjąć przypadek, gdy wszystkie pozostałe (n−1) elementów miałoby trafić do A. Stąd takich podziałów jest 2ⁿ⁻¹−1 (rzecz jasna wynik ten sam, co u PW).