kombinatorika...

kombinatorika...

offline
  • bxdx 
  • Novi MyCity građanin
  • Pridružio: 19 Nov 2011
  • Poruke: 3

koliko ima resenja (a1,a2,...,ak), ai ∈ N U {0}, jednacine a1+a2+...+ak=n gdje je n dati prirodi broj.
hvala



Registruj se da bi učestvovao u diskusiji. Registrovanim korisnicima se NE prikazuju reklame unutar poruka.
offline
  • Pridružio: 15 Feb 2011
  • Poruke: 157
  • Gde živiš: Kovin

Prvo posmatrajmo isti zadatak samo neka ai bude iz skupa N. dakle
moramo naci sve uredjene k-torke (a1,a2,...ak) tako da je njiova suma n.
Radimo na sledeci nacin:
broj n razlozimo na zbir n jedinica, samo sto znak plus necemo pisati izmedju:
11111...1 (n jedinica) sada se zadatak svodi na ukupan broj nacina stavljanja k-1 pregradica izmedju jedinica.
(Primer:
neka je n=7 i neka treba da ga razbijemo na zbir cetiri broja:
dakle :1111111
ako stavimo pregrade na sledeci nacin:
11|111|1|1
dobijamo jedno "razbijanje": (2,3,1,1)
)

sada lako resavamo taj problem na sledeci nacin:
imamo n-1 mesta gde mozemo staviti pregradice, a imamo k-1 pregradica.
Na koliko nacina mozemo postaviti pregradice?
to se naravno moze uciniti na (n-1 nad k-1) nacina. (ovo n-1 nad k-1 je binomni koeficijent)
E sada tvoj zadatak svedimo na ovaj, dakle u tvom zadatku je dopusteno da ai bude nula i to je problem koji se lako resava uvodjenjem smene bi = ai+1, sada je bi prirodan broj, kada zamenimo
dobija se:
b1+b2+...+bk+k=n
tj. b1+...+bk=n-k i po prethodnom jasno je da je resenje zadatka (n-k-1 nad k-1)



Ko je trenutno na forumu
 

Ukupno su 809 korisnika na forumu :: 36 registrovanih, 7 sakrivenih i 766 gosta   ::   [ Administrator ] [ Supermoderator ] [ Moderator ] :: Detaljnije

Najviše korisnika na forumu ikad bilo je 3466 - dana 01 Jun 2021 17:07

Korisnici koji su trenutno na forumu:
Korisnici trenutno na forumu: 357magnum, A.R.Chafee.Jr., aramis s, bojanM84, DH, dragonserbia, Duh sa sekirom, Filip Marinković, goxin, HrcAk47, hyla, Ilija Cvorovic, ivan1973, kovinacc, krkalon, Marko Marković, MB120mm, MegaVLAdaR, Mercury, milimoj, Misirac, Mixelotti, mladen.zovko, mustangkg, randja26, repac, S2M, sabros, sevenino, skvara, Snorks, Srki94, vathra, VJ, vlvl, xJeremijAx