Zliczanie podzbiorów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
zaklopotany93
Użytkownik
Użytkownik
Posty: 202
Rejestracja: 17 wrz 2012, o 08:21
Płeć: Mężczyzna
Podziękował: 57 razy
Pomógł: 9 razy

Zliczanie podzbiorów

Post autor: zaklopotany93 »

Załóżmy, że mamy zbiór \(\displaystyle{ \left\{ 1,2,...,n\right\}}\) . Jakie są narzędzia kombinatoryczne do zliczania podzbiorów o żądanej własności tzn. z czego można korzystać jak już scharakteryzuje tę własność i zauważy jakąś prawidłowość? Wszelkie sugestie mile widziane!
Glo
Użytkownik
Użytkownik
Posty: 684
Rejestracja: 6 lis 2009, o 21:00
Płeć: Mężczyzna
Podziękował: 59 razy
Pomógł: 101 razy

Zliczanie podzbiorów

Post autor: Glo »

To już zależy od określonej własności. Np. liczba wszystkich podzbiorów zbioru to \(\displaystyle{ 2^n}\), a liczba wszystkich podzbiorów trójelementowych to \(\displaystyle{ C^3_n}\). Nie ma ogólnego wzoru, gdyby był, kombinatoryka znacznie by się uprościła . Chyba że się nie zrozumieliśmy, wtedy proszę o sprostowanie.
Ostatnio zmieniony 24 paź 2012, o 16:47 przez pyzol, łącznie zmieniany 1 raz.
Powód: Tagi [latex][/latex]
zaklopotany93
Użytkownik
Użytkownik
Posty: 202
Rejestracja: 17 wrz 2012, o 08:21
Płeć: Mężczyzna
Podziękował: 57 razy
Pomógł: 9 razy

Zliczanie podzbiorów

Post autor: zaklopotany93 »

Wiem, że takie ogólniki jak napisałem niewiele mówią, ale chodzi mi głównie o narzędzia kombinatoryczne takie bardziej złożone, których nie ma w szkole średniej jak np. wzór włączeń i wyłączeń, kombinacje z powtórzeniami, permutacje z powtórzeniami, jakieś inne użyteczne do zliczania bijekcji, iniekcji, suriekcji, podzbiorów zbioru \(\displaystyle{ \left\{ 1,2,..,n\right\}}\) w których suma liczb jest kwadratem liczby naturalnej i wszelkie inne tego typu rzeczy, oprócz tych podstawowych szkolnych.

Daję pomógł, oczywiście.
gblablabla
Użytkownik
Użytkownik
Posty: 420
Rejestracja: 6 lis 2010, o 20:10
Płeć: Mężczyzna
Lokalizacja: Clausthal-Zellerfeld
Podziękował: 65 razy
Pomógł: 25 razy

Zliczanie podzbiorów

Post autor: gblablabla »

Liczba Bella - liczba podziałów zbioru.

Podział to:
rodzina niepustych, rozłącznych podzbiorów danego zbioru dająca w sumie cały zbiór.
\(\displaystyle{ B_n}\) to l. podziałów zbioru n-elementowego.

\(\displaystyle{ B_0 = 1 \\ \\B_1 = 1 \\ B_{n+1} = \sum_{k = 0}^{n} {n \choose k} B_{k}}\)
Awatar użytkownika
Vardamir
Użytkownik
Użytkownik
Posty: 1913
Rejestracja: 3 wrz 2010, o 22:52
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 410 razy

Zliczanie podzbiorów

Post autor: Vardamir »

Liczby Stirlinga II rodzaju:

\(\displaystyle{ S(n,k)}\) czyli liczba sposobów podziału zbioru n elementowego na k niepustych podzbiorów.
gblablabla
Użytkownik
Użytkownik
Posty: 420
Rejestracja: 6 lis 2010, o 20:10
Płeć: Mężczyzna
Lokalizacja: Clausthal-Zellerfeld
Podziękował: 65 razy
Pomógł: 25 razy

Zliczanie podzbiorów

Post autor: gblablabla »

Liczba nieporządków zbioru n-elementowego - posilnia, czyli liczba permutacji zbioru bez punktów stałych (np. \(\displaystyle{ 1}\) przechodzące w \(\displaystyle{ 1}\)) danego zbioru.
\(\displaystyle{ !0 = 1 \\ !n = n(!(n-1)) + (-1)^n \\ !(n + 1) = n(!n + !(n-1))}\)
ODPOWIEDZ