MATEMANIJA

Slučajno sam naišao na ovaj zadatak na jednom papiru, ne znam ni izvor a ni rešenje.
Koliko ima petocifrenih brojeva čiji je zbir cifara [inlmath]5[/inlmath]?
Moj postupak:
Da bi zbir cifara u petocifrenom broju iznosio [inlmath]5[/inlmath] on mora biti sastavljen od sledećih kombinacija
[dispmath]\{1,1,1,1,1\},\{1,1,1,2,0\},\{1,2,2,0,0\},\{1,1,3,0,0\},\{1,4,0,0,0\},\{2,3,0,0,0\},\{5,0,0,0,0\}[/dispmath]
[inlmath]\{1,1,1,1,1\}[/inlmath] - [inlmath]1[/inlmath] petocifreni
[inlmath]\{1,1,1,2,0\}[/inlmath] - [inlmath]2\cdot\frac{4!}{2}[/inlmath] - [inlmath]24[/inlmath] petocifrenih
[inlmath]\{1,2,2,0,0\}[/inlmath] - [inlmath]2\cdot\frac{4!}{4}[/inlmath] - [inlmath]12[/inlmath] petocifrenih
[inlmath]\{1,1,3,0,0\}[/inlmath] - [inlmath]2\cdot\frac{4!}{3}[/inlmath] - [inlmath]16[/inlmath] petocifrenih
[inlmath]\{1,4,0,0,0\}[/inlmath] - [inlmath]8[/inlmath] petocifrenih
[inlmath]\{2,3,0,0,0\}[/inlmath] - [inlmath]8[/inlmath] petocifrenih
[inlmath]\{5,0,0,0,0\}[/inlmath] - [inlmath]1[/inlmath] petocifreni
[dispmath]1+16+12+24+8+8+1=70[/dispmath]
Zanima me da li je postupak ispravan.

Krajnji rezultat ti je tačan, ali je slučajno ispao tačan.

Tačne međurezultate obeležio sam ti zeleno, a netačne crveno:

Herien Wolf je napisao:[inlmath]\{1,1,1,1,1\}[/inlmath] - [inlmath]1[/inlmath] petocifreni
[inlmath]\{1,1,1,2,0\}[/inlmath] - [inlmath]2\cdot\frac{4!}{2}[/inlmath] - [inlmath]24[/inlmath] petocifrenih
[inlmath]\{1,2,2,0,0\}[/inlmath] - [inlmath]2\cdot\frac{4!}{4}[/inlmath] - [inlmath]12[/inlmath] petocifrenih
[inlmath]\{1,1,3,0,0\}[/inlmath] - [inlmath]2\cdot\frac{4!}{3}[/inlmath] - [inlmath]16[/inlmath] petocifrenih
[inlmath]\{1,4,0,0,0\}[/inlmath] - [inlmath]8[/inlmath] petocifrenih
[inlmath]\{2,3,0,0,0\}[/inlmath] - [inlmath]8[/inlmath] petocifrenih
[inlmath]\{5,0,0,0,0\}[/inlmath] - [inlmath]1[/inlmath] petocifreni

Pogledaj, recimo, strukture [inlmath]\left\{1,2,2,0,0\right\}[/inlmath] i [inlmath]\left\{1,1,3,0,0\right\}[/inlmath]. U obe ove strukture nula se pojavljuje dvaput, neka druga cifra se pojavljuje takođe dvaput, a treća cifra se pojavljuje „solo“. Nije li onda logično da te dve strukture moraju imati podjednak broj mogućnosti?

Da, ima logike
Sad moje sledeće pitanje glasi
[inlmath]\{1,1,1,2,0\}[/inlmath] kako iz ove strukture da odredimo broj kombinacija.
Broj [inlmath]21110[/inlmath] ili [inlmath]20111[/inlmath] predstavljaju po jednu kombinaciju bez obzira koja je jedinica na kom mestu. Mene zanima kako da eliminišem te ponovljene članove unutar ove strukture. Cenim da je postupak isti za ostale dve strukture.

Permutacije s ponavljanjem (imaš formulu ovde).

Npr. za stukturu [inlmath]\left\{1,1,1,2,0\right\}[/inlmath] izračunaš broj permutacija s ponavljanjem za slučaj kad je na prvom mestu jedinica, a zatim broj permutacija s ponavljanjem kad je na prvom mestu dvojka – i zatim ta dva broja sabereš.

Alternativno, možeš da odrediš broj svih permutacija s ponavljanjem, ne vodeći računa o tome koja se cifra nalazi na prvom mestu, a zatim od tog broja oduzmeš broj onih permutacija s ponavljanjem kod kojih je nula na prvom mestu.

---

Ipak, ja bih preporučio drugačiji način rešavanja ovog zadatka, u kojem nije potrebno za svaku strukturu posebno tražiti broj mogućnosti.
Predstavimo svaku cifru odgovarajućim brojem kuglica: cifru [inlmath]1[/inlmath] jednom kuglicom, cifru [inlmath]2[/inlmath] s dve kuglice... i cifru [inlmath]5[/inlmath] s pet kuglica.
Pošto zbir cifara treba da iznosi [inlmath]5[/inlmath], znači da ukupno imamo na raspolaganju [inlmath]5[/inlmath] kuglica.
Time naš problem svodimo na problem kako tih [inlmath]5[/inlmath] kuglica raspodeliti u [inlmath]5[/inlmath] kutija, pri čemu kutije, logično, predstavljaju odgovarajuće pozicije za svaku od cifara unutar petocifrenog broja.
Imamo i jedan uslov – prva kutija ne sme biti prazna, što je analogno tome da prva cifra ne sme biti nula (kako bi broj zaista bio petocifren).
To jest, u prvoj kutiji se mora nalaziti najmanje jedna kuglica.
Prema tome, od [inlmath]5[/inlmath] kuglica koliko ih imamo na raspolaganju, jednu odmah mećemo u prvu kutiju, i na nju zaboravimo.
Preostaju nam [inlmath]4[/inlmath] kuglice, koje treba rasporediti u [inlmath]5[/inlmath] kutija.
E sad pogledati ovaj tutorijal, u kojem sam, unutar poslednjeg poglavlja, „Kombinacije s ponavljanjem“, pokazao primer raspoređivanja [inlmath]k[/inlmath] kuglica u [inlmath]n[/inlmath] kutija.
U našem primeru je, dakle, [inlmath]k=4[/inlmath] i [inlmath]n=5[/inlmath], te se kao rešenje dobije [inlmath]{8\choose4}[/inlmath], što je jednako [inlmath]70[/inlmath].

Jasno
Sad da dovršim zadatak
[inlmath]\{1,1,1,1,1\}\,\Rightarrow\,1[/inlmath] petocifreni
[inlmath]\{1,1,1,2,0\}[/inlmath] - Prvi slučaj imamo kada je [inlmath]1[/inlmath] na prvom mestu, i tada imamo [inlmath]\frac{4!}{2!}=12[/inlmath], a drugi kada je [inlmath]2[/inlmath] na prvom mestu, i tada imamo [inlmath]\frac{4!}{3!}=4\,\Rightarrow\,16[/inlmath] petocifrenih
[inlmath]\{1,2,2,0,0\}[/inlmath] - Prvi slučaj imamo kada je [inlmath]1[/inlmath] na prvom mestu, i tada imamo [inlmath]\frac{4!}{2!\cdot2!}=6[/inlmath], a drugi kada je [inlmath]2[/inlmath] na prvom mestu, i tada imamo [inlmath]\frac{4!}{2!}=12\,\Rightarrow\,18[/inlmath] petocifrenih
[inlmath]\{1,1,3,0,0\}\,\Rightarrow\,18[/inlmath] petocifrenih
[inlmath]\{1,4,0,0,0\}\,\Rightarrow\,8[/inlmath] petocifrenih
[inlmath]\{2,3,0,0,0\}\,\Rightarrow\,8[/inlmath] petocifrenih
[inlmath]\{5,0,0,0,0\}\,\Rightarrow\,1[/inlmath] petocifreni

Ukupan broj [inlmath]1+16+18+18+8+8+1=70[/inlmath]