Zliczanie podzbiorów
-
- 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
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!
-
- 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
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]
Powód: Tagi
-
- 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
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.
Daję pomógł, oczywiście.
-
- 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
Liczba Bella - liczba podziałów zbioru.
Podział to:
\(\displaystyle{ B_0 = 1 \\ \\B_1 = 1 \\ B_{n+1} = \sum_{k = 0}^{n} {n \choose k} B_{k}}\)
Podział to:
\(\displaystyle{ B_n}\) to l. podziałów zbioru n-elementowego.rodzina niepustych, rozłącznych podzbiorów danego zbioru dająca w sumie cały zbiór.
\(\displaystyle{ B_0 = 1 \\ \\B_1 = 1 \\ B_{n+1} = \sum_{k = 0}^{n} {n \choose k} B_{k}}\)
- Vardamir
- 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
Liczby Stirlinga II rodzaju:
\(\displaystyle{ S(n,k)}\) czyli liczba sposobów podziału zbioru n elementowego na k niepustych podzbiorów.
\(\displaystyle{ S(n,k)}\) czyli liczba sposobów podziału zbioru n elementowego na k niepustych podzbiorów.
-
- 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
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))}\)
\(\displaystyle{ !0 = 1 \\ !n = n(!(n-1)) + (-1)^n \\ !(n + 1) = n(!n + !(n-1))}\)