Zliczanie podziałów liczb
-
- 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
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 ?
\(\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 ?
- kropka+
- 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
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.
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.
-
- 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
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.
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.
-
- 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
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}\).