Kombinatoryka rozkład kulek do szufladek

Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Polo11121
Witam na forum
Witam na forum
Posty: 1
Rejestracja: 21 maja 2020, 10:00

Kombinatoryka rozkład kulek do szufladek

Post autor: Polo11121 » 21 maja 2020, 10:08

Wyznaczyc liczbe rozkladow 25 identycznych kul do siedmiu rozroznialnych szufladek,jezli
pierwsze dwie szufladki moga zawierac co najwyzej po osiem kul,a pozostale nie moga byc puste.

Sciurius
Rozkręcam się
Rozkręcam się
Posty: 48
Rejestracja: 05 maja 2020, 16:38
Podziękowania: 4 razy
Otrzymane podziękowania: 8 razy
Płeć:

Re: Kombinatoryka rozkład kulek do szufladek

Post autor: Sciurius » 21 maja 2020, 11:54

jako że kule są identyczne możesz to rozpatrywać jako liczbę możliwości wyboru takich liczb całkowitych nieujemnych \(a_1 - \color{red}{a_8}\) że:
\(a_1 +a_2 +...+\color{red}{a_8} =25\)
\(a_1 ,a_2 \le 8\)
\(a_3 , a_4 , ... , \color{red}{a_8} > 0\)

[edited by Jerry] szuflad miało być siedem
Pozdrawiam

Sciurius

Awatar użytkownika
Jerry
Stały bywalec
Stały bywalec
Posty: 254
Rejestracja: 18 maja 2009, 09:23
Podziękowania: 1 raz
Otrzymane podziękowania: 124 razy

Re: Kombinatoryka rozkład kulek do szufladek

Post autor: Jerry » 21 maja 2020, 12:31

Sciurius pisze:
21 maja 2020, 11:54
jako że kule są identyczne możesz to rozpatrywać jako liczbę możliwości wyboru takich liczb całkowitych nieujemnych \(a_1, \cdots, a_8\) że:
\(a_1 +a_2 +...+a_8 =25\)
\(a_3 , a_4 , ... , a_8 > 0\)
Liczba rozwiązań, w liczbach całkowitych nieujemnych, równania
\(x_1+x_2+x_3+\cdots+x_7=20\),
gdzie
\(a_1=x_1;\ a_2=x_2;\ a_3=x_3+1;\cdots;\ a_7=x_7+1\)
jest równa
\({21+6-1\choose6}\)
i to nie jest problem. Problemem jest
Sciurius pisze:
21 maja 2020, 11:54
\(a_1 ,a_2 \le 8\)
i tu coś zaproponuj... Reguła w/w ?

Pozdrawiam

[edited] poprawka, zasugerowałeś mnie, szuflad miało być siedem!!!

Sciurius
Rozkręcam się
Rozkręcam się
Posty: 48
Rejestracja: 05 maja 2020, 16:38
Podziękowania: 4 razy
Otrzymane podziękowania: 8 razy
Płeć:

Re: Kombinatoryka rozkład kulek do szufladek

Post autor: Sciurius » 21 maja 2020, 17:56

Policzyłbym ile jest rozwiązań tego równania dla \(a_1 > 8 lub a_2 > 8\) będzie to żmudne wypisywanie przypadków w stylu:
\(x_1 = k \to x_2 + x_3 +x_4 + x_5 + x_6 + x_7 = 20 - k\) oczywiście \(k >8 \) i \(k \in \zz\)
liczba rozwiązań powyższego równania w calkowityc jest równa \( {6+20-k-1 \choose 5} \) zatem liczba wszystkich rozwiązań równania które nas nie interesują dlatego że \(a_1 > 8\) jest równa
\( \sum_{i=9}^{20} {25-i \choose 5} \)
Przypadek dla \(a_2 > 8\) jest analogiczny i też odpada nam
\( \sum_{i=9}^{20} {25-i \choose 5} \)
Należy zauważyć że przypadki gdy \(a_1 > 8\) i \(a_2 > 8\) liczymy podwójnie w ten sposób więc wypadałoby jeden spowrotem dodać
Więc robimy analogicznie dla sumy \(x_1 + x_2 = l\) oczywiście \(l >17 \) i \(l \in \zz\)
równanie \(x_3 + x_4 +x_5 + x_6 +x_7 = 20-l\) ma \( {5+20-l-1 \choose 4} \) rozwiązań
z tym że niektóre sumy można złożyć na kilka sposobów:
\(x_1 + x_2 = 18 \) 1 sposób para (9,9)
\(x_1 + x_2 = 19 \) 2 sposób pary (10,9),(9,10)
\(x_1 + x_2 = 20 \) 3 sposób pary (11,9),(10,10),(9,11)

Zatem dla \(a_1 > 8\) i \(a_2 > 8\) mamy:

\( \sum_{i=18}^{20} (i-17){24-l \choose 4} \) sposobów na rozwiązanie równania ostatecznie wychodzi więc:

\({26 \choose 6} -2* \sum_{i=9}^{20} {25-i \choose 5} \) +\( \sum_{i=18}^{20} (i-17){24-i \choose 4} = 230230-2*12376+28=205506 \)

Mogłem się gdzieś pomylić więc czytajcie uważnie ale wydaje mi się że metoda jest ok

PS napisałem programik który przechodzi przez 7 pętli i to sprawdza i też wyszło 205 506 więc chyba jest dobrze

PS2 sorry za 8 szuflad nie wiem jak to przeczytałem :/
Pozdrawiam

Sciurius

kerajs
Fachowiec
Fachowiec
Posty: 1869
Rejestracja: 14 lis 2016, 15:38
Podziękowania: 9 razy
Otrzymane podziękowania: 798 razy
Płeć:

Re: Kombinatoryka rozkład kulek do szufladek

Post autor: kerajs » 22 maja 2020, 00:34

Sciurius pisze:
21 maja 2020, 17:56

\({26 \choose 6} -2* \sum_{i=9}^{20} {25-i \choose 5} \) +\( \sum_{i=18}^{20} (i-17){24-i \choose 4} = 230230-2*12376+28=205506 \)
A może:
\({25-1 \choose 7-1} -2 \sum_{i=9}^{19} {25-i -1\choose 6-1} + \sum_{i=1}^{3} i{7-i \choose 5-1} = \)

Sciurius
Rozkręcam się
Rozkręcam się
Posty: 48
Rejestracja: 05 maja 2020, 16:38
Podziękowania: 4 razy
Otrzymane podziękowania: 8 razy
Płeć:

Re: Kombinatoryka rozkład kulek do szufladek

Post autor: Sciurius » 22 maja 2020, 12:56

Wychodzi około dwa razy mniej może tak jest ale nie rozumiem jak do tego doszedłeś
Pozdrawiam

Sciurius

kerajs
Fachowiec
Fachowiec
Posty: 1869
Rejestracja: 14 lis 2016, 15:38
Podziękowania: 9 razy
Otrzymane podziękowania: 798 razy
Płeć:

Re: Kombinatoryka rozkład kulek do szufladek

Post autor: kerajs » 22 maja 2020, 18:12

(Wszystkie dodatnie całkowitoliczbowe rozwiązania równania \(x_1+x_2+x_3+x_4+x_5+x_6+x_7=25\))
-(rozwiązania w których \(x_1\) lub \(x_2 \)przyjmują wartości większe od 8 ) +
(rozwiązania w których \(x_1\) i \(x_2 \)przyjmują wartości większe od 8 )