forum.zadania.info

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.

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

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!!!

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 :/

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} = \)

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

(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 )