[kombinatoryka] Suma cyfr wynosi...

[Waylays]

Dobry,
z góry przepraszam za obszerny tekst, starałem się go tak sformatować, by był w miarę czytelny. Na dyskretnej dostaliśmy takie zadanie: Ile jest liczb całkowitych od \(\displaystyle{ 1}\) do miliona, których suma cyfr wynosi \(\displaystyle{ 8}\). Opisałem sobie zbiór \(\displaystyle{ A}\) takich liczb, czyli

\(\displaystyle{ A=\{\overline{x_1x_2...x_6}: x_1+x_2+...+x_6=8, \ x_i \in \{0, 1, 2, ..., 8\},i\in I\}}\)

Teraz zadanie sprowadza się do znalezienia liczby rozwiązań równania

\(\displaystyle{ x_1+x_2+x_3+x_4+x_5+x_6=8}\) dla \(\displaystyle{ x_i \in \{0, 1, 2, 3, 4, 5, 6, 7, 8\}}\).

Jeszcze za czasów liceum rozwiązywałem sobie podobne zadania i gdzieś tam naskrobałem sobie wzór, tylko już nie pamiętam o co mi tam rok temu chodziło, bo normalnie na wikipedii jest

\(\displaystyle{ \overline{C}^k_n={{k+n-1}\choose{k}}={{k+n-1}\choose{n-1}}}\).

Teraz o ile nie można utworzyć kombinacji bez powtórzeń np. \(\displaystyle{ 6}\)-elementowych ze zbioru \(\displaystyle{ 5}\)-elementowego, to takie kombinacje
z powtórzeniami można utworzyć. Zapisane mam, że równanie

\(\displaystyle{ x_1+x_2+ ... +x_k=n}\) dla \(\displaystyle{ x_i \in \{0, 1, 2, ..., n\}}\)

ma tyle rozwiązań, ile jest kombinacji z powtórzeniami \(\displaystyle{ n}\)-elementowych ze zbioru \(\displaystyle{ k}\)-elementowego, czyli

\(\displaystyle{ \overline{C}^n_k={{n+k-1}\choose{k-1}}={{n+k-1}\choose{n}}}\).

U nas na dyskretnej ten wzór pojawiał się, tylko bez symbolu, przy rozmieszczaniu nierozróżnialnych elementów w rozróżnialnych pudełkach, itp. Mniej więcej wiem skąd ten z wikipedii się bierze i ten drugi też, bo czytałem w liceum dowód z ciągami zer
i jedynek i jak się zapisuje zbiór, w którym elementy się powtarzają. Napisałem sobie program, który mi liczy te liczby i faktycznie tutaj poprawny jest tylko ten drugi wzór, bo wychodzi tyle, ile powinno, czyli \(\displaystyle{ 1287}\), tylko nie za bardzo widzę z czego ta zamiana \(\displaystyle{ n}\) i \(\displaystyle{ k}\) wynika. Problem mam z podobnym zadaniem, bo tutaj suma ma wynosić \(\displaystyle{ 8}\), a elementy \(\displaystyle{ x_i}\) dobieramy z cyfr od \(\displaystyle{ 0}\) do też \(\displaystyle{ 8}\), więc \(\displaystyle{ n}\) jest tutaj i tutaj. Natomiast mam też policzyć ile jest liczb całkowitych od \(\displaystyle{ 1}\) do miliona, gdzie suma cyfr wynosi \(\displaystyle{ 14}\). Czyli teraz

\(\displaystyle{ B=\{\overline{x_1...x_6}: x_1+...+x_6=14, \ x_i \in \{0, ..., 9\}, \ i\in I\}}\).

W brudnopisie mam naskrobane coś takiego: jeżeli mamy to samo równanie, czyli

\(\displaystyle{ x_1+x_2+ ... +x_k=n}\) ale już dla \(\displaystyle{ x_i \in \{1, 2, ..., n-k+1\}}\),

to możemy zrobić tak:

\(\displaystyle{ x_i-1 \in \{0, 1, 2, ..., n-k\}}\) oraz \(\displaystyle{ x_i-1=y_i}\).

Wtedy mamy \(\displaystyle{ (x_1-1)+(x_2-1)+...+(x_k-1)=n-k}\), czyli \(\displaystyle{ y_1+y_2+...+y_k=n-k}\)

i mamy analogiczną sytuację, bo \(\displaystyle{ y_i}\) zaczyna przebiegać od \(\displaystyle{ 0}\) i kończy na \(\displaystyle{ n-k}\), a po prawej stronie równania też jest \(\displaystyle{ n-k}\), więc liczba takich rozwiązań to

\(\displaystyle{ \overline{C}^{n-k}_k={{n-k+k-1}\choose{n-k}}={{n-1}\choose{n-k}}={{n-1}\choose{k-1}}}\).

I tutaj pojawia się w zadaniu problem. Bo moje początkowe \(\displaystyle{ n}\) wynosi \(\displaystyle{ 14}\), a \(\displaystyle{ k}\) wynosi \(\displaystyle{ 6}\). Teraz moje \(\displaystyle{ x_i \in \{0, ..., 9\}}\) więc nie muszę z tym nić robić wtedy mając \(\displaystyle{ n}\) i \(\displaystyle{ k}\) jak wyżej, \(\displaystyle{ x_i}\) kończy się na \(\displaystyle{ n-k+1\ (9)}\), ale skoro nie musiałem nic robić ze zmiennymi, to nie odjąłem \(\displaystyle{ k\ (6)}\) od obu stron równania, tak więc po prawej stronie równania dalej mam \(\displaystyle{ n\ (14)}\), a nie \(\displaystyle{ n-k+1}\) i tu wszystko się sypie. Nie za bardzo wiem jak to ruszyć i czy dobrze to robię / rozumuję i czy w ogóle da się to zadanie ugryźć tym sposobem. Informacje, które tu zawarłem mogą odbiegać od prawdy, bo z niczym tego nie porównałem, bazuję tylko na wynikach. Dodam tylko, że to drugie zadanie Pan prof. rozwiązywał z jakimś studentem na tablicy i napisali, że takich liczb jest

\(\displaystyle{ {{14+6-1}\choose{6-1}}-6\cdot {{4+6-1}\choose{6-1}}}\)

i wynik jest dobry, a przynajmniej zgadza się z tym co mój program mi wypisał, czyli \(\displaystyle{ 10872}\), tylko nie za bardzo pamiętam czemu pojawia się

\(\displaystyle{ -6\cdot {{4+6-1}\choose{6-1}}}\)

bo trochę zajęty byłem rozkminianiem i nie za bardzo skupiałem się jak prof. to tłumaczył, to jakby ktoś mógł przy okazji wytłumaczyć, to w ogóle byłoby świetnie i będę niezmiernie wdzięczny.

[norwimaj]

Ile jest liczb całkowitych od \(\displaystyle{ 1}\) do miliona, których suma cyfr wynosi \(\displaystyle{ 8}\).

Każdą taką liczbę można utożsamić z ciągiem ośmiu jedynek i pięciu przegródek, na przykład liczbę \(\displaystyle{ 42011}\) utożsamimy z \(\displaystyle{ |1111|11||1|1.}\)

Natomiast mam też policzyć ile jest liczb całkowitych od \(\displaystyle{ 1}\) do miliona, gdzie suma cyfr wynosi \(\displaystyle{ 14}\).

Tak jak poprzednio, ale od wyniku trzeba odjąć te przypadki, w których jedna z sześciu cyfr jest większa od \(\displaystyle{ 9.}\)

[Waylays]

Natomiast mam też policzyć ile jest liczb całkowitych od \(\displaystyle{ 1}\) do miliona, gdzie suma cyfr wynosi \(\displaystyle{ 14}\).

Tak jak poprzednio, ale od wyniku trzeba odjąć te przypadki, w których jedna z sześciu cyfr jest większa od \(\displaystyle{ 9}\).

Rozumiem, z większością niepewności się uporałem, tylko nie za bardzo wiem dlaczego w tym przypadku to jest akurat \(\displaystyle{ -6\cdot {{4+6-1}\choose{6-1}}}\) ? I jakby było w przypadku, gdy suma miałaby wynosić np. \(\displaystyle{ 24}\), bo próbowałem analogicznie i do \(\displaystyle{ 19}\) jest okay, a wyżej już klapa, bo wraz ze wzrostem sumy wyniki wychodzą coraz mniejsze niż powinny wyjść.

[norwimaj]

Rozumiem, z większością niepewności się uporałem, tylko nie za bardzo wiem dlaczego w tym przypadku to jest akurat \(\displaystyle{ -6\cdot {{4+6-1}\choose{6-1}}}\) ?

Liczba \(\displaystyle{ 6}\) odpowiada za wybór pojemnika, w którym ma być ponad \(\displaystyle{ 9}\) kulek. Do tego pojemnika wkładamy od razu \(\displaystyle{ 10}\) kulek, a pozostałe \(\displaystyle{ 4}\) kulki rozmieszczamy dowolnie w pojemnikach.

I jakby było w przypadku, gdy suma miałaby wynosić np. \(\displaystyle{ 24}\), bo próbowałem analogicznie i do \(\displaystyle{ 19}\) jest okay, a wyżej już klapa, bo wraz ze wzrostem sumy wyniki wychodzą coraz mniejsze niż powinny wyjść.

Tu powinieneś użyć jeszcze kolejnych wyrazów we wzorze włączeń i wyłączeń, bo jest możliwe, że w dwóch pojemnikach będzie nadmiar.