MATEMANIJA

koliko resenja ima jednačina [inlmath]x_1+x_2+\cdots +x_k=n[/inlmath] u skupu [inlmath]\mathbb{Z}^+\cup\{0\}[/inlmath]. resenja pocinje sa [inlmath]n-1\choose k-1[/inlmath], jel mozete da mi objasnite zasto se tako resava, posto meni tu nista nije jasno

Pa što ne napisa celo rešenje?

Ovo su ti kombinacije s ponavljanjem. Znaš li kako se one računaju? Formula za broj kombinacija s ponavljanjem od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase glasi [inlmath]n+k-1\choose k[/inlmath].

Broj rešenja jednačine [inlmath]x_1+x_2+\cdots +x_k=n[/inlmath] jednak je broju kombinacija s ponavljanjem od [inlmath]k[/inlmath] elemenata [inlmath]n[/inlmath]-te klase (uoči da su ovde [inlmath]n[/inlmath] i [inlmath]k[/inlmath] zamenili mesta u odnosu na originalni slučaj), pa se računa po formuli [inlmath]n+k-1\choose n[/inlmath].

Da li možeš da uočiš vezu između broja rešenja ove jednačine i kombinacija s ponavljanjem?

hm, mislio sam da je fora u tom prvom delu pa ne bas, ja te kombinacije vezem za skupove i onda mi nije bas jasno zasto bas [inlmath]n[/inlmath]-te klase?

Prvo malo uopšteno o kombinacijama s ponavljanjem. Kombinacije od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase s ponavljenjem predstavljaju načine na koje iz skupa od [inlmath]n[/inlmath] elemenata, [inlmath]\left\{a_1,a_2,\ldots ,a_n\right\}[/inlmath], možemo vršiti odabir [inlmath]k[/inlmath] puta, pri čemu svaki od elemenata skupa možemo odabirati i više od jednom. Npr. iz vreće s [inlmath]n[/inlmath] kuglica numerisanih od [inlmath]1[/inlmath] do [inlmath]n[/inlmath] biramo po jednu kuglicu, zapišemo koju smo izabrali, zatim je vratimo i tako ponavljamo do [inlmath]k[/inlmath]-tog izvlačenja. Tada formula za broj kombinacija s ponaljvanjem glasi
[dispmath]\overline{C_n^k}={n+k-1\choose k}[/dispmath]
Naravno, pošto ukupno ima [inlmath]k[/inlmath] izvlačenja, jasno je da je [inlmath]x_1+x_2+\cdots +x_n=k[/inlmath], gde [inlmath]x_i[/inlmath] predstavlja broj koliko smo puta izvukli kuglicu [inlmath]a_i[/inlmath].

E sad, ovaj tvoj slučaj možemo svesti na kombinacije od [inlmath]k[/inlmath] elemenata [inlmath]n[/inlmath]-te klase s ponavljanjem. Znači, obrati pažnju na to da ovde sada [inlmath]k[/inlmath] označava broj elemenata, a [inlmath]n[/inlmath] označava klasu – obrnuto od onog kako smo navikli, ali u principu je isto, to su samo oznake. Dakle, ako u celom prethodnom pasusu [inlmath]n[/inlmath] zameniš sa [inlmath]k[/inlmath], a [inlmath]k[/inlmath] zameniš sa [inlmath]n[/inlmath], tačno ćeš doći dotle da je iz vreće s [inlmath]k[/inlmath] kuglica moguće izvršiti [inlmath]n[/inlmath] izvlačenja s ponavljanjem na tačno onoliko načina koliki je broj celobrojnih nenegativnih rešenja jednačine [inlmath]x_1+x_2+\cdots +x_k=n[/inlmath]. Znači, kuglicu [inlmath]a_1[/inlmath] smo izvukli [inlmath]x_1[/inlmath] puta, kuglicu [inlmath]a_2[/inlmath] smo izvukli [inlmath]x_2[/inlmath] puta, ... kuglicu [inlmath]a_k[/inlmath] smo izvukli [inlmath]x_k[/inlmath] puta, a ukupno smo imali [inlmath]n[/inlmath] izvlačenja. Prema tome, u pitanju su kombinacije od [inlmath]k[/inlmath] elemenata [inlmath]n[/inlmath]-te klase s ponavljanjem:
[dispmath]\overline{C_k^n}={n+k-1\choose n}[/dispmath]
Daj, napiši to celo njihovo rešenje, baš me zanima da vidim na koji način su oni radili kad im rešenje počinje sa [inlmath]n-1\choose k-1[/inlmath].

ahm, jasnije mi je sada, samo ja nisam znao da [inlmath]k[/inlmath] predstavlja broj na koliko nacina mozemo vrsiti odabir, vec da je [inlmath]k[/inlmath] samo broj elemenata u svakom podskupu od [inlmath]n[/inlmath] elemenata :d

Ne znam da l' smo se dobro razumeli... Nigde nisam napisao da je [inlmath]k[/inlmath] broj načina na koje možemo vršiti odabir. Koliki je broj načina na koji možemo vršiti odabir, to nam upravo govori formula za broj kombinacija s ponavljanjem.

Drugi deo rečenice, onaj s brojem elemenata podskupa, nisam razumeo.

Daniel-Prvo malo uopšteno o kombinacijama s ponavljanjem. Kombinacije od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase s ponavljenjem predstavljaju načine na koje iz skupa od [inlmath]n[/inlmath] elemenata, [inlmath]\left\{a_1,a_2,\ldots ,a_n\right\}[/inlmath], možemo vršiti odabir [inlmath]k[/inlmath] puta, pri čemu svaki od elemenata skupa možemo odabirati i više od jednom. Npr. iz vreće s [inlmath]n[/inlmath] kuglica numerisanih od [inlmath]1[/inlmath] do [inlmath]n[/inlmath] biramo po jednu kuglicu, zapišemo koju smo izabrali, zatim je vratimo i tako ponavljamo do [inlmath]k[/inlmath]-tog izvlačenja.
To, da mozemo vršiti odabir [inlmath]k[/inlmath] puta .
ja sam mislio na to da imamo prvo skup od [inlmath]n[/inlmath] elemenata i onda od tog skupa pravimo podskupove sa [inlmath]k[/inlmath] elemenata, i da kombinacije govore koliko postoji takvih podskupova

jovica je napisao:Daniel-Prvo malo uopšteno o kombinacijama s ponavljanjem. Kombinacije od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase s ponavljenjem predstavljaju načine na koje iz skupa od [inlmath]n[/inlmath] elemenata, [inlmath]\left\{a_1,a_2,\ldots ,a_n\right\}[/inlmath], možemo vršiti odabir [inlmath]k[/inlmath] puta, pri čemu svaki od elemenata skupa možemo odabirati i više od jednom. Npr. iz vreće s [inlmath]n[/inlmath] kuglica numerisanih od [inlmath]1[/inlmath] do [inlmath]n[/inlmath] biramo po jednu kuglicu, zapišemo koju smo izabrali, zatim je vratimo i tako ponavljamo do [inlmath]k[/inlmath]-tog izvlačenja.
To, da mozemo vršiti odabir [inlmath]k[/inlmath] puta .

Pazi, broj eksperimenata, tj. broj koliko puta vršimo odabir, nije isto što i broj načina na koji možemo dobiti rezultate tih eksperimata, tj. broj načina na koji možemo izvršiti odabire. Primer – bacanje kockice. Kockicu bacamo, recimo, [inlmath]5[/inlmath] puta, ali to [inlmath]5[/inlmath] nije i broj načina na koji možemo dobiti brojeve. Načina ima [inlmath]6+5-1\choose 5[/inlmath] (broj kombinacija od [inlmath]6[/inlmath] elemenata [inlmath]5.[/inlmath] klase s ponavljanjem). To jest, [inlmath]11111,\;11112,\;11113,\;11114,\;11115,\;11116,\;11122,\;11123,\ldots[/inlmath] da sad ne nabrajam...
Znači, nemoj mešati te dve stvari.

jovica je napisao:ja sam mislio na to da imamo prvo skup od [inlmath]n[/inlmath] elemenata i onda od tog skupa pravimo podskupove sa [inlmath]k[/inlmath] elemenata, i da kombinacije govore koliko postoji takvih podskupova

Da, to su kombinacije bez ponavljanja. Ali, u ovom zadatku, kao što sam naglasio, govorimo o kombinacijama s ponavljanjem.

zaboravio sam da dodam posto su kombinacije sa ponavljanjem, da bi to znacilo da se elementi mogu ponavljati unutar tog podskupa od [inlmath]k[/inlmath] elemenata, tj da ne moraju svi elementi podskupa biti razliciti jedan od drugog.
a da li to onda znaci da je broj eksperimenata i broj članova podskupa isti ?

Bilo bi pogrešno tako govoriti, jer se u teoriji skupova broj elemenata nekog skupa definiše kao broj njegovih različitih elemenata, pri čemu se svaki od tih elemenata može ponavljati proizvoljno mnogo puta, ali broj njegovog ponavljanja nema uticaja na broj elemenata skupa. Znači, skup [inlmath]\left\{1,1,1,2,4,4,7,7\right\}[/inlmath] jednak je skupu [inlmath]\left\{1,2,4,7\right\}[/inlmath] i njegov broj elemenata je [inlmath]4[/inlmath]. Imaš o tome u Ubavic-evom tutorijalu o skupovima.

Što se tiče kombinacija s ponavljanjem, uzmi lepo ove primere koje sam dao u prethodnim postovima.

dobro, dakle kombinacije sa ponavljanjem od skupa sa [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase je uredjena [inlmath]k[/inlmath]-torka, jel tako? ne vidim koja je veza onda izmedju uredjene [inlmath]k[/inlmath]-torke i broja eksperimenata ?

Definitivno nije uređena [inlmath]k[/inlmath]-torka, jer je kod uređene [inlmath]k[/inlmath]-torke bitan redosled njenih komponenata, a kod kombinacija redosled nije bitan. Znači, ako ishode [inlmath]5[/inlmath] bacanja kockica posmatramo kao kombinacije s ponavljanjem, tada ishode [inlmath]42461[/inlmath] i [inlmath]12446[/inlmath] tretiramo kao jedan isti ishod.

To bi bile uređene [inlmath]k[/inlmath]-torke, tj. bio bi bitan redosled, ako bismo posmatrali varijacije s ponavljanjem.

e jbga prepisao sam iz knjige ;D
[inlmath]k[/inlmath] dakle predstavlja broj eksperimenata, a da li nam [inlmath]k[/inlmath] jos nesto govori? skapirao sam najzad ono sa pocetka

Da, [inlmath]k[/inlmath] je broj eksperimenata, a takođe [inlmath]k[/inlmath] predstavlja i zbir broja izvlačenja svake od kuglica.
Govorim, naravno, o onom „uobičajenom“ slučaju u kojem je sa [inlmath]n[/inlmath] obeležen broj elemenata (broj kuglica u vreći), a sa [inlmath]k[/inlmath] broj izvlačenja s vraćanjem. U zadatku koji si postovao, kao što rekoh, te dve oznake su zamenile mesta.