Zliczanie podziałów liczb

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Zliczanie podziałów liczb

Post autor: matinf »

Witam,
\(\displaystyle{ N(n,k,a,b)}\)
Rozmieszczenia \(\displaystyle{ n}\) nierozróżnialnych kul w \(\displaystyle{ k}\) rozróżnialnych pudełkach, w każdym minimalnie \(\displaystyle{ a}\), a maksymalnie \(\displaystyle{ b}\).

Mamy sprawdzić, która z liczb jest większa.
\(\displaystyle{ N(28,19,1,2)\ \ \ \ czy\ \ N(30,10,2,7)}\)

I moje podejście jest takie:
TO są uporządkowane podziały liczb z dodatkowymi warunkami. Pierwsze co zrobię, to pozbędę się warunku na minimum, tzn rozdam do każdego pudełka odpowiednią ilość kul.

Teraz wymienię nasze liczby na:
\(\displaystyle{ (1) N(9, 19, 1)}\)
\(\displaystyle{ (2) N(10, 10, 5)}\)
I teraz na ile sposobów można rozdzielić w pierwszym przypadku ? Mamy \(\displaystyle{ 9}\) kul, oraz \(\displaystyle{ 19}\) pudełek. Można do każdego pudełka po jednej kuli. Czyi trzeba wybrać \(\displaystyle{ {19 \choose 9} = 92378}\)
W drugim przypadku jest trudniej. \(\displaystyle{ 10}\) kul, \(\displaystyle{ 10}\) pudełek. Do każdego maksymalnie \(\displaystyle{ 5}\) wejdzie kul.

Jak chcę to zliczyć ? Policzę wszystkie uporządkowane podziały, tzn:
\(\displaystyle{ x_1 + ... x_{10} = 10\ \ \ \ x_i \ge 0}\)
Następnie odejmę od tego przypadki, gdy:
jedna z liczb jest szóstką, siódemką, ósemką, dziewiątką, dziesiątką.
\(\displaystyle{ x_1 + ... + x_9 = 4}\)
\(\displaystyle{ x_1 + ... + x_9 = 3}\)
\(\displaystyle{ x_1 + ... + x_9 = 2}\)
\(\displaystyle{ x_1 + ... + x_9 = 1}\)
\(\displaystyle{ x_1 + ... + x_9 = 0}\)
Z sumuję te ilości uporządkowanych rozwiązań i dopiszę zero na końcu otrzymanej sumy - i to odejmę od wszystkich nieujemnych uporządkowanych rozwiązań \(\displaystyle{ x_1 + ... x_{10} = 10\ \ \ \ x_i \ge 0}\).

Tędy droga ? Myślę dobrze ?
Awatar użytkownika
kropka+
Użytkownik
Użytkownik
Posty: 4389
Rejestracja: 16 wrz 2010, o 14:54
Płeć: Kobieta
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 787 razy

Zliczanie podziałów liczb

Post autor: kropka+ »

Trochę szybciej będzie jak po prostu policzysz sumę czterech przypadków: gdy pięć kul znajduje się w 2,3,4 i 5-ciu pudełkach.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Zliczanie podziałów liczb

Post autor: matinf »

(1) Ale czy moje rozwiązanie jest poprawne ?
(2) Nie rozumiem co masz na myśli. Możesz powiedzieć więcej ?
Awatar użytkownika
kropka+
Użytkownik
Użytkownik
Posty: 4389
Rejestracja: 16 wrz 2010, o 14:54
Płeć: Kobieta
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 787 razy

Zliczanie podziałów liczb

Post autor: kropka+ »

1. Nie wiem o co chodzi z tym zerem, które chcesz dopisać na końcu ? Ponadto rozumiem, że \(\displaystyle{ x _{1}+...+x _{9}}\) oznacza sumę dodatkowych kul w dowolnych dziewięciu pudełkach.
2. Źle spojrzałam - jest 10 a nie 5 pudełek, więc 10 kul można rozmieścić w dwóch do dziesięciu pudełek:
w dwóch pudełkach można rozmieścić na \(\displaystyle{ {10 \choose 2}}\) sposobów (rozmieszczenie kul 55)
w trzech pudełkach na \(\displaystyle{ {10 \choose 3} \cdot 3!}\) sposobów (rozmieszczenie 145)
...
w dziesięciu pudełkach na 1 sposób.
Na końcu wszystko dodajemy.
Ostatnio zmieniony 2 wrz 2014, o 10:27 przez kropka+, łącznie zmieniany 1 raz.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Zliczanie podziałów liczb

Post autor: matinf »

Hmm, chcę zrozumieć co robisz.

Rozmieszczanie do dwóch pudełek - na jeden sposób (bo po równe pięć kul). Jedyne co musisz zrobić to wybrać parę pudełek.

Do trzech pudełek. Tutaj nie rozumiem. Wybierasz wszystkie możliwe trójki pudełek - zgoda. rozstawiasz je między sobą.
Ale dalej musisz zapewnić każde możliwe rozdanie kul po pudełkach. Tzn np.:

\(\displaystyle{ 3, 2 ,5 \\
4,4,2\\
...}\)
.
Samo przemnożenie przez \(\displaystyle{ 3!}\) nic nie da, Te kule trzeba jeszcze porozdawać po pudełkach. Chyba, że ja coś źle rozumiem.
Awatar użytkownika
kropka+
Użytkownik
Użytkownik
Posty: 4389
Rejestracja: 16 wrz 2010, o 14:54
Płeć: Kobieta
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 787 razy

Zliczanie podziałów liczb

Post autor: kropka+ »

Dobrze rozumiesz.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Zliczanie podziałów liczb

Post autor: matinf »

No czyli w końcu popełniłaś błąd czy jak ?
Awatar użytkownika
kropka+
Użytkownik
Użytkownik
Posty: 4389
Rejestracja: 16 wrz 2010, o 14:54
Płeć: Kobieta
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 787 razy

Zliczanie podziałów liczb

Post autor: kropka+ »

Ja po prostu chciałam liczyć po kolei wszystkie rozłożenia (po jednym).
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Zliczanie podziałów liczb

Post autor: matinf »

A rozumiem, ale to nie będzie szybsze
Awatar użytkownika
kropka+
Użytkownik
Użytkownik
Posty: 4389
Rejestracja: 16 wrz 2010, o 14:54
Płeć: Kobieta
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 787 razy

Zliczanie podziałów liczb

Post autor: kropka+ »

A w jaki sposób Ty liczysz taki przypadek?
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Zliczanie podziałów liczb

Post autor: matinf »

matinf pisze:Jak chcę to zliczyć ? Policzę wszystkie uporządkowane podziały, tzn:
\(\displaystyle{ x_1 + ... x_{10} = 10\ \ \ \ x_i \ge 0}\)
Następnie odejmę od tego przypadki, gdy:
jedna z liczb jest szóstką, siódemką, ósemką, dziewiątką, dziesiątką.
\(\displaystyle{ x_1 + ... + x_9 = 4\\
x_1 + ... + x_9 = 3\\
x_1 + ... + x_9 = 2\\
x_1 + ... + x_9 = 1\\
x_1 + ... + x_9 = 0\\}\)

Z sumuję te ilości uporządkowanych rozwiązań i dopiszę zero na końcu otrzymanej sumy - i to odejmę od wszystkich nieujemnych uporządkowanych rozwiązań \(\displaystyle{ x_1 + ... x_{10} = 10\ \ \ \ x_i \ge 0}\).
Awatar użytkownika
kropka+
Użytkownik
Użytkownik
Posty: 4389
Rejestracja: 16 wrz 2010, o 14:54
Płeć: Kobieta
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 787 razy

Zliczanie podziałów liczb

Post autor: kropka+ »

No to jak liczysz wszystkie uporządkowane podziały?
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Zliczanie podziałów liczb

Post autor: matinf »

ze wzoru:
\(\displaystyle{ x_1 + x_2 + ...+ x_k = n}\)
Gdzie iksy mogą być zerami:
\(\displaystyle{ {n+k-1\choose k-1 }}\)
Awatar użytkownika
kropka+
Użytkownik
Użytkownik
Posty: 4389
Rejestracja: 16 wrz 2010, o 14:54
Płeć: Kobieta
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 787 razy

Zliczanie podziałów liczb

Post autor: kropka+ »

Tak, masz rację. Twój sposób jest dobry i znacznie szybszy od mojego.
ODPOWIEDZ