Ile jest podziałów n-elementowego zbioru na r rozłącznych
-
- Użytkownik
- Posty: 64
- Rejestracja: 6 sty 2015, o 18:56
- Płeć: Mężczyzna
- Lokalizacja: Mazowsze
- Podziękował: 1 raz
Ile jest podziałów n-elementowego zbioru na r rozłącznych
Proszę o pomoc z zadaniem:
Ile jest podziałów n-elementowego zbioru na r rozłącznych podzbiorów \(\displaystyle{ A_{1},A_{2},...,A_{r}}\), o mocach odpowiednio \(\displaystyle{ t_{1}, t_{2}, t_{3}, ... , t{r}}\), gdzie \(\displaystyle{ t_{1} + ... + t_{r} = n}\)?-- 14 lis 2018, o 20:37 --Jest ktoś w stanie pomóc?
Ile jest podziałów n-elementowego zbioru na r rozłącznych podzbiorów \(\displaystyle{ A_{1},A_{2},...,A_{r}}\), o mocach odpowiednio \(\displaystyle{ t_{1}, t_{2}, t_{3}, ... , t{r}}\), gdzie \(\displaystyle{ t_{1} + ... + t_{r} = n}\)?-- 14 lis 2018, o 20:37 --Jest ktoś w stanie pomóc?
- Peter Zof
- Użytkownik
- Posty: 585
- Rejestracja: 30 cze 2012, o 16:07
- Płeć: Mężczyzna
- Lokalizacja: Warszawa (MIMUW) / Pułtusk
- Podziękował: 88 razy
- Pomógł: 66 razy
Ile jest podziałów n-elementowego zbioru na r rozłącznych
Do pojemnika \(\displaystyle{ A_1}\) wrzucamy \(\displaystyle{ t_1}\) elementów z \(\displaystyle{ n}\) możliwych. Możemy to zrobić na \(\displaystyle{ {n \choose t_1}}\) sposobów. Następnie mamy pojemnik \(\displaystyle{ A_2}\) do którego chcemy wrzucić \(\displaystyle{ t_2}\) elementów, ale dostępnych jest jeszcze \(\displaystyle{ n-t_1}\) elementów. Zatem odpowiedzią jest iloczyn: \(\displaystyle{ {n \choose t_1} \cdot {n-t_1 \choose t_2} \cdot \dots \cdot {n - (t_1+\dots+t_{i-1})\choose t_i} \cdot \dots \cdot {n - (t_1+\dots + t_{r-1}) \choose t_r}}\). Zauważ, że ostatni składnik w tym iloczynie wynosi \(\displaystyle{ 1}\).
- arek1357
- Użytkownik
- Posty: 5703
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 129 razy
- Pomógł: 524 razy
Re: Ile jest podziałów n-elementowego zbioru na r rozłącznyc
Ten wzór się już sypie dla:
\(\displaystyle{ n=4, t_{1}=2,t_{2}=2}\)
\(\displaystyle{ {4 \choose 2} \cdot {2 \choose 2}=6}\)
a jest ich.: \(\displaystyle{ 3}\)
\(\displaystyle{ n=4, t_{1}=2,t_{2}=2}\)
\(\displaystyle{ {4 \choose 2} \cdot {2 \choose 2}=6}\)
a jest ich.: \(\displaystyle{ 3}\)
- Peter Zof
- Użytkownik
- Posty: 585
- Rejestracja: 30 cze 2012, o 16:07
- Płeć: Mężczyzna
- Lokalizacja: Warszawa (MIMUW) / Pułtusk
- Podziękował: 88 razy
- Pomógł: 66 razy
Ile jest podziałów n-elementowego zbioru na r rozłącznych
Okej, racja. Jednak powinien przeżyć przy dodatkowym założeniu, że liczy się kolejność zbiorów \(\displaystyle{ A_1,\dots,A_r}\). Tzn, przykładowo dla \(\displaystyle{ X=\{a,b,c.d\}}\) rozróżniamy układ \(\displaystyle{ (\{a,b\},\{c,d\})}\) od układu \(\displaystyle{ (\{c,d\},\{a,b\})}\).
- Peter Zof
- Użytkownik
- Posty: 585
- Rejestracja: 30 cze 2012, o 16:07
- Płeć: Mężczyzna
- Lokalizacja: Warszawa (MIMUW) / Pułtusk
- Podziękował: 88 razy
- Pomógł: 66 razy
Ile jest podziałów n-elementowego zbioru na r rozłącznych
Tak więc zapewne trzeba ten wzór który napisałem znormalizować przez dopisanie czynnika \(\displaystyle{ \frac{1}{r!}}\).
- Peter Zof
- Użytkownik
- Posty: 585
- Rejestracja: 30 cze 2012, o 16:07
- Płeć: Mężczyzna
- Lokalizacja: Warszawa (MIMUW) / Pułtusk
- Podziękował: 88 razy
- Pomógł: 66 razy
Ile jest podziałów n-elementowego zbioru na r rozłącznych
Oznaczając przez \(\displaystyle{ \lambda_{n,r}}\) liczbę którą napisałem w pierwszym poście, teraz mówię żeby ją poprawić do \(\displaystyle{ \frac{1}{r!} \lambda_{n,r}}\).
- Peter Zof
- Użytkownik
- Posty: 585
- Rejestracja: 30 cze 2012, o 16:07
- Płeć: Mężczyzna
- Lokalizacja: Warszawa (MIMUW) / Pułtusk
- Podziękował: 88 razy
- Pomógł: 66 razy
Ile jest podziałów n-elementowego zbioru na r rozłącznych
Okk, znów masz rację ^^ Pomyślę czy da się to jakoś poprawić.
@edit
Problem pojawia się, gdy dla różnych \(\displaystyle{ i,j}\) zachodzi \(\displaystyle{ t_i=t_j}\). Ciąg liczb \(\displaystyle{ (t_1,\dots,t_r)}\) trzeba podzielić na inne ciągi. Może opiszę to na przykładzie, aby uniknąć zbędnej znaczkologii. Jeśli przykładowo \(\displaystyle{ (t_1,t_2,t_3,t_4,t_5)=(2,5,3,5,5)}\) to dzielimy ten ciąg na takie grupy: \(\displaystyle{ (2),(3),(5,5,5)}\). Teraz patrzymy na ilość elementów w każdej z tych grup i bierzemy iloczyn silni tych liczb, to znaczy w tym wypadku to będzie \(\displaystyle{ 1!\cdot 1! \cdot 3!}\). Wydaje mi się, że przez właśnie tę liczbę należy podzielić \(\displaystyle{ \lambda_{n,r}}\).
@edit
Problem pojawia się, gdy dla różnych \(\displaystyle{ i,j}\) zachodzi \(\displaystyle{ t_i=t_j}\). Ciąg liczb \(\displaystyle{ (t_1,\dots,t_r)}\) trzeba podzielić na inne ciągi. Może opiszę to na przykładzie, aby uniknąć zbędnej znaczkologii. Jeśli przykładowo \(\displaystyle{ (t_1,t_2,t_3,t_4,t_5)=(2,5,3,5,5)}\) to dzielimy ten ciąg na takie grupy: \(\displaystyle{ (2),(3),(5,5,5)}\). Teraz patrzymy na ilość elementów w każdej z tych grup i bierzemy iloczyn silni tych liczb, to znaczy w tym wypadku to będzie \(\displaystyle{ 1!\cdot 1! \cdot 3!}\). Wydaje mi się, że przez właśnie tę liczbę należy podzielić \(\displaystyle{ \lambda_{n,r}}\).
Ostatnio zmieniony 1 gru 2018, o 18:59 przez Peter Zof, łącznie zmieniany 1 raz.
- Peter Zof
- Użytkownik
- Posty: 585
- Rejestracja: 30 cze 2012, o 16:07
- Płeć: Mężczyzna
- Lokalizacja: Warszawa (MIMUW) / Pułtusk
- Podziękował: 88 razy
- Pomógł: 66 razy
Ile jest podziałów n-elementowego zbioru na r rozłącznych
Co rozumiesz przez pomyłkę w zapisie? Postaram się zapisać generyczny wzór w wolnym czasie, jednak idea wydaje się być sensowna. Zgadza się to również z Twoimi wcześniejszymi kontrprzykładami.
- arek1357
- Użytkownik
- Posty: 5703
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 129 razy
- Pomógł: 524 razy
Re: Ile jest podziałów n-elementowego zbioru na r rozłącznyc
\(\displaystyle{ (2,5,3,5,5)}\)
\(\displaystyle{ (2)(3)(5,5)}\)
jest tu jakaś kolizja chyba...
\(\displaystyle{ (2)(3)(5,5)}\)
jest tu jakaś kolizja chyba...
- Peter Zof
- Użytkownik
- Posty: 585
- Rejestracja: 30 cze 2012, o 16:07
- Płeć: Mężczyzna
- Lokalizacja: Warszawa (MIMUW) / Pułtusk
- Podziękował: 88 razy
- Pomógł: 66 razy
Ile jest podziałów n-elementowego zbioru na r rozłącznych
Tak, trzy piątki miały być oczywiście, tzn zamiast: \(\displaystyle{ (2)(3)(5,5)}\) miało być \(\displaystyle{ (2)(3)(5,5,5)}\). Dziękuję.
- arek1357
- Użytkownik
- Posty: 5703
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 129 razy
- Pomógł: 524 razy
Re: Ile jest podziałów n-elementowego zbioru na r rozłącznyc
To może dokończę:
Zbiorów o liczebności \(\displaystyle{ t_{1}}\) jest \(\displaystyle{ s_{1}}\)
Zbiorów o liczebności \(\displaystyle{ t_{2}}\) jest \(\displaystyle{ s_{2}}\)
....................................................................................
Zbiorów o liczebności \(\displaystyle{ t_{r}}\) jest \(\displaystyle{ s_{r}}\)
Ilość takich podziałów jest:
\(\displaystyle{ \frac{n!}{\left( t_{1}!\right)^{s_{1}} \cdot ... \cdot \left( t_{r}!\right) ^{s_{r}} \cdot s_{1}! \cdot ... \cdot s_{r}! }}\)
Jest to bardzo podobny wzór na podziały na cykle o zadanej długości z tą różnicą, że przy \(\displaystyle{ t_{i}}\) nie występuje silnia...
Zbiorów o liczebności \(\displaystyle{ t_{1}}\) jest \(\displaystyle{ s_{1}}\)
Zbiorów o liczebności \(\displaystyle{ t_{2}}\) jest \(\displaystyle{ s_{2}}\)
....................................................................................
Zbiorów o liczebności \(\displaystyle{ t_{r}}\) jest \(\displaystyle{ s_{r}}\)
Ilość takich podziałów jest:
\(\displaystyle{ \frac{n!}{\left( t_{1}!\right)^{s_{1}} \cdot ... \cdot \left( t_{r}!\right) ^{s_{r}} \cdot s_{1}! \cdot ... \cdot s_{r}! }}\)
Jest to bardzo podobny wzór na podziały na cykle o zadanej długości z tą różnicą, że przy \(\displaystyle{ t_{i}}\) nie występuje silnia...