kombinatorika...

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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)