Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI KOMBINATORIKA

Kombinatorika – broj rešenja jednačine

[inlmath]{n\choose k}=\frac{n!}{\left(n-k\right)!k!}[/inlmath]

Kombinatorika – broj rešenja jednačine

Postod jovica » Četvrtak, 05. Jun 2014, 09:22

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 :nene:
jovica  OFFLINE
 
Postovi: 126
Zahvalio se: 44 puta
Pohvaljen: 1 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+
  • +1

Re: Kombinatorika – broj rešenja jednačine

Postod Daniel » Četvrtak, 05. Jun 2014, 18:11

Pa što ne napisa celo rešenje? :P

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?
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 7939
Lokacija: Beograd
Zahvalio se: 4143 puta
Pohvaljen: 4221 puta

Re: Kombinatorika – broj rešenja jednačine

Postod jovica » Subota, 07. Jun 2014, 16:56

hm, mislio sam da je fora u tom prvom delu :D pa ne bas, ja te kombinacije vezem za skupove i onda mi nije bas jasno zasto bas [inlmath]n[/inlmath]-te klase?
jovica  OFFLINE
 
Postovi: 126
Zahvalio se: 44 puta
Pohvaljen: 1 puta

Re: Kombinatorika – broj rešenja jednačine

Postod Daniel » Subota, 07. Jun 2014, 17:43

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]. :)
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 7939
Lokacija: Beograd
Zahvalio se: 4143 puta
Pohvaljen: 4221 puta

Re: Kombinatorika – broj rešenja jednačine

Postod jovica » Sreda, 11. Jun 2014, 12:48

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
jovica  OFFLINE
 
Postovi: 126
Zahvalio se: 44 puta
Pohvaljen: 1 puta

Re: Kombinatorika – broj rešenja jednačine

Postod Daniel » Sreda, 11. Jun 2014, 12:57

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.
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 7939
Lokacija: Beograd
Zahvalio se: 4143 puta
Pohvaljen: 4221 puta

Re: Kombinatorika – broj rešenja jednačine

Postod jovica » Sreda, 11. Jun 2014, 13:02

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 :D
jovica  OFFLINE
 
Postovi: 126
Zahvalio se: 44 puta
Pohvaljen: 1 puta

Re: Kombinatorika – broj rešenja jednačine

Postod Daniel » Sreda, 11. Jun 2014, 13:17

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

Da, to su kombinacije bez ponavljanja. Ali, u ovom zadatku, kao što sam naglasio, govorimo o kombinacijama s ponavljanjem.
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 7939
Lokacija: Beograd
Zahvalio se: 4143 puta
Pohvaljen: 4221 puta

Re: Kombinatorika – broj rešenja jednačine

Postod jovica » Sreda, 11. Jun 2014, 17:32

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 ? :D
jovica  OFFLINE
 
Postovi: 126
Zahvalio se: 44 puta
Pohvaljen: 1 puta

Re: Kombinatorika – broj rešenja jednačine

Postod Daniel » Sreda, 11. Jun 2014, 22:29

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.
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 7939
Lokacija: Beograd
Zahvalio se: 4143 puta
Pohvaljen: 4221 puta

Sledeća

Povratak na KOMBINATORIKA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 15 gostiju

cron

Index stranicaTimObriši sve kolačiće boarda
Danas je Nedelja, 05. April 2020, 21:25 • Sva vremena su u UTC + 1 sat [ DST ]
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs