Ile jest podziałów n-elementowego zbioru na r rozłącznych

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Bambuko
Użytkownik
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

Post autor: Bambuko »

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?
Awatar użytkownika
Peter Zof
Użytkownik
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

Post autor: Peter Zof »

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}\).
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

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}\)
Awatar użytkownika
Peter Zof
Użytkownik
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

Post autor: Peter Zof »

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\})}\).
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

Tak ale w tym zadaniu kolejność nie ma znaczenia...
Awatar użytkownika
Peter Zof
Użytkownik
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

Post autor: Peter Zof »

Tak więc zapewne trzeba ten wzór który napisałem znormalizować przez dopisanie czynnika \(\displaystyle{ \frac{1}{r!}}\).
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

czyli jakbyś to zapisał?
Awatar użytkownika
Peter Zof
Użytkownik
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

Post autor: Peter Zof »

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}}\).
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

\(\displaystyle{ n=3, r=2, t_{1}=1,t_{2}=2}\)

sprawdź
Awatar użytkownika
Peter Zof
Użytkownik
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

Post autor: Peter Zof »

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}}\).
Ostatnio zmieniony 1 gru 2018, o 18:59 przez Peter Zof, łącznie zmieniany 1 raz.
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

Ciepło ale pomyłka w zapisie...

zapisz wzór...
Awatar użytkownika
Peter Zof
Użytkownik
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

Post autor: Peter Zof »

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.
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

\(\displaystyle{ (2,5,3,5,5)}\)

\(\displaystyle{ (2)(3)(5,5)}\)

jest tu jakaś kolizja chyba...
Awatar użytkownika
Peter Zof
Użytkownik
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

Post autor: Peter Zof »

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ę.
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

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...
ODPOWIEDZ