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 2862 korisnika na forumu :: 78 registrovanih, 11 sakrivenih i 2773 gosta   ::   [ Administrator ] [ Supermoderator ] [ Moderator ] :: Detaljnije

Najviše korisnika na forumu ikad bilo je 5623 - dana 13 Dec 2025 19:56

Korisnici koji su trenutno na forumu:
Korisnici trenutno na forumu: 4. Ozrenska, 8u47, alex71, amonsrb, ArmFPGA, Bobrock1, Bojan198527, bokicacar, Boris BM, Bubimir, CraniumWhite, crnitrn, cyprus, darkkran, dearg, debeli, desmeki, Despot Đurađ, Dimitrise93, Dorcolac, Dukelander, ElvisP, eulereix, fijufijukrozkapiju55, Gaga_89, GeoM, hyla, ILGromovnik, iznurenitragalac, Jager715510, jarovitt, Joint Chief, Kajzer Soze, Kamov, kovacicbozo, ladro, laki_bb, Lieutenant, Ljusa, lord sir giga, Manjane, Mercury, Milan Miscevic, Milo97, mjovan, mmelezovic, Moldovan, Mrav Obrad, Mzee, nerislav2025, nobutado, OtacMakarije, Paklenica, Pantelejmon, Panter, pein, Perudin_92, Prečanin30, radoznao, RajkoB, raketaš, RileHerc, rovac, sap, skylab1111, stingD, stokssone, suton, VBoss, Velizar Laro, vensla, vidra1, Visionary, Vojkan Petrovic, Wepp, Zoran1959, zzapNDjuric99, Đurđevdan